C語言位運算技巧：不使用加法/除法求兩數平均值 (避免溢位)

問題

(a+b)/2 若 a,b 為大整數，a+b 可能溢位 (有號 UB，無號環繞)。

方法一：右移 1 位 (無號/正數適用)

int avg_shift(int a, int b) {
    return (a + b) >> 1; // 仍有溢位風險！
}
// 無號版安全:
unsigned int avg_unsigned(unsigned int a, unsigned int b) {
    return (a >> 1) + (b >> 1) + (a & 1 & b & 1); // 處理最低位進位
}

方法二：差值法 (標準安全寫法)

int avg_safe(int a, int b) {
    return a + (b - a) / 2; // 等價 (a+b)/2 但無溢位
    // 或 (a & b) + ((a ^ b) >> 1) 位運算版
}

推導：a + (b-a)/2 = (2a + b - a)/2 = (a+b)/2。b-a 不會溢位 (同號差值絕對值較小)。

方法三：位運算無分支版

int avg_bitwise(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
}
// 原理: a&b 保留同為1的位(進位), a^b 保留不同位(無進位和), 右移1位相加

浮點數版本

double avg_double(double a, double b) {
    return a + (b - a) * 0.5; // 同樣避免溢位 (雙精度範圍極大)
}

測試

int main() {
    int a = 2000000000, b = 2000000000;
    printf("%d\n", avg_safe(a,b)); // 2000000000
    printf("%d\n", avg_bitwise(a,b)); // 2000000000
    return 0;
}