題目

從兩個數字中找出最大的一個而不使用判斷描述。
There are two int variables: a and b, don’t use “if”, “? :”, “switch” or other judgement statements, find out the biggest one of the two numbers.

說明

max(a, b)… 正解，這題題目限制不能用 if、switch 或 ? : 的語法，但沒說不能用 math 的 max。不過這樣就太簡單了，所以我們假定不能用內建函式，而是自己實作這個 max()。

由於不能用判斷式，所以我們依照以下步驟來解：

  1. 用利用減法，大減小為正，小減大為負的特性來判斷大小。
  2. 至於如何判斷正負，我們看最左邊的 bit 是否為 1，利用上面的 shift 方式得到 sign_bit 為 0 則為正，1 為負。
  3. 接著我們利用陣列的索引來代替判斷式，0 為正，表示 a 大，所以 0 的位置放 a；反之 1 為負，b 大，1 的位置放 b。

解法

1
2
3
4
5
6
7
int max(int a, int b)
{
    int diff = a - b;
    int sign_bit = unsigned(diff) >> (sizeof(int) * 8 - 1);
    int array[] = {a, b};
    return array[sign_bit];
}

延伸思考

如果現在放寬允許可以使用 abs() 函式取絕對值，那此題還可以怎麼解？

解法

1
2
3
4
int max(int a, int b)
{
    return ((a + b) + abs((a - b))) / 2;
}

說明

這個解法可以用這樣的思考方式，假想兩條線段如下：

長: |=====|
短: |===|

如果能讓短的變得跟長的線段一樣長，那總和除以 2 就是我們要的答案；所以我們想辦法補齊短少的部分，而那部份就是 ( 長 - 短 )，因為程式中 a 不一定比 b 大，所以還要配合 abs 使用。

延伸閱讀

面試常見程式考題