How to find out the largest one of the two numbers without judgement statements.

max(a, b)...正解,這題題目限制不能用if, switch或? :的語法,但沒說不能用math的max。

不過這樣就太簡單了,所以我們假定不能用內建函式。

解法

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];
}

說明

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

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

延伸思考

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

解法

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

說明

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

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

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

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()