# 利用 bitwise operation 實現取兩個有號整數中較大的值

### 程式碼

int32_t max(int32_t a, int32_t b) {
    int32_t diff = a - b;
    int32_t max = a - (diff & (diff >> 31));
        
    return max;
}

:::info
Reference
* [解讀計算機編碼-不需要分支的設計](https://hackmd.io/@sysprog/binary-representation#%E4%B8%8D%E9%9C%80%E8%A6%81%E5%88%86%E6%94%AF%E7%9A%84%E8%A8%AD%E8%A8%88)
:::

### 原理
`a` 和 `b` 兩數皆為 32 bits 的有號整數，執行此函式可分為兩種情況：
1. `a >= b`
此時 `diff` 為一個大於等於 0 的整數，MSB 為 `0`，所以 `(diff >> 31)` 為 `0`，`diff & (diff >> 31)` 也為 0，傳回的值即為 `a - 0 = a`
2. `a < b`
此時 `diff` 為一個小於 0 的整數，MSB 為 `1`，所以 `(diff >> 31)` 為 (11...111)~2~，`diff & (diff >> 31)` 即為 diff & (11...111)~2~ = diff，傳回的值則為 `a - diff`，又因 `diff = a - b`，所以 `a - diff = b`

### 改進
不過以上這段程式有個限制：`a - b` 不能夠有 overflow 發生，若有 overflow 發生那上述的兩個狀況會相反，而導致函式的返回值為兩數中的較小值。所以需要檢查是否有 overflow 的情況發生，而 overflow 發生時須滿足兩個條件：
* `a` 與 `-b` 為同號
* `a` 或 `-b` 與 diff 為異號

程式碼如下：

int32_t max(int32_t a, int32_t b) {
    int32_t diff = a - b;
    /*
     *      if overflow occurs flag is 100...00 in binary;
     *      else flag is 000...00 in binary.                
     */
    int32_t flag = (int32_t)__builtin_sub_overflow_p (a, b, (__typeof__ ((a) - (b))) 0) << 31; 
    int32_t max = a - (diff & ((diff ^ flag) >> 31));

    return max;
}

而在檢查 overflow 時我 `-b` 用的是一補數而不是二補數是因為若 b 的值為 32 bit 有號整數的最小值(-2147483648)，其二補數的 sign bit 依舊為 1。

:::warning
GCC 提供 [Built-in Functions to Perform Arithmetic with Overflow Checking](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)，可用來簡化上述實作
:notes: jserv
:::