C語言位運算技巧：不使用加法與除法計算兩數平均值

C語言位運算技巧：不使用加法與除法計算兩數平均值

經典面試題：計算 (a + b) / 2 但**不能使用 `+`、`/` 運算子**。解法利用**位運算**：無進位加法 (XOR) + 進位 (AND<<1) 迭代，或直接右移一位 (算術右移)。

方法一：右移一位 (最簡單，但隱含加法)

#include <stdio.h>

int average_shift(int a, int b) {
    // (a + b) >> 1 等價於 (a + b) / 2 (向零取整)
    // 注意：此處仍用了 +，若嚴格禁止 + 需用方法二
    return (a + b) >> 1;
}

int main() {
    int a = 6, b = 8;
    printf("平均值 = %d\n", average_shift(a, b));  // 7
    return 0;
}

方法二：純位運算實現加法 + 右移 (完全無 + /)

int add_bitwise(int a, int b) {
    while (b != 0) {
        int sum = a ^ b;        // 無進位加法
        int carry = (a & b) << 1; // 進位
        a = sum;
        b = carry;
    }
    return a;
}

int average_bitwise(int a, int b) {
    int sum = add_bitwise(a, b);
    return sum >> 1;  // 算術右移一位 = 除以 2
}

方法三：無溢出平均值公式 (工業級標準寫法)

ab(a+b)/2average_safe備註
6877正常
-53-1-1負數 (算術右移保留符號位)
INT_MAXINT_MAX溢出 UBINT_MAX**無溢出**
INT_MININT_MIN溢出 UBINT_MIN**無溢出**
INT_MAXINT_MIN-1/2=00正確


關鍵差異：算術右移 vs 邏輯右移

有號整數右移：C 標準為**實現定義**，絕大多數編譯器 (GCC, Clang, MSVC) 採用**算術右移** (複製符號位)，等同於向負無窮取整除以 2。
無號整數右移：標準保證**邏輯右移** (高位補 0)。
平均值向零取整：若需嚴格向零取整，需額外處理負奇數情況。


無符號數版本 (嚴格標準合規)
unsigned int average_unsigned(unsigned int a, unsigned int b) {
    return (a & b) + ((a ^ b) >> 1);  // 邏輯右移，標準保證
}

// 有號數轉換版
int average_safe_std(int a, int b) {
    unsigned int ua = a, ub = b;
    unsigned int avg = (ua & ub) + ((ua ^ ub) >> 1);
    return (int)avg;  // 依賴二進制補碼表示 (現代平台通用)
}

總結
**工業級推薦**：`(a & b) + ((a ^ b) >> 1)` —— 無溢出、無除法、O(1)、標準合規 (配合無號轉換)。面試若問「不使用 + - * /」，則需實現 `add_bitwise` 迭代。理解**無進位加法 (XOR) + 進位 (AND<<1)** 是位運算加法的核心，可推廣至乘法、除法等更複雜運算。