Java 整數平均值無溢出算法：位運算與數學等價變換

問題：計算 `(a + b) / 2` 當 `a,b` 為 `Integer.MAX_VALUE` 時溢出（結果為負數）。

經典無溢出公式

int avg = (a & b) + ((a ^ b) >> 1);

原理推導

對任意兩整數：

• `a & b` 保留**同為 1** 的位（即進位部分）。
• `a ^ b` 保留**不同** 的位（無進位加法）。
• `(a ^ b) >> 1` 即無進位加法的結果除以 2（算術右移保留符號位）。
• 兩者相加 = `(a + b) / 2` 的數學等價，且中間過程無溢出。

另一種寫法（更易讀）

int avg = a / 2 + b / 2 + ((a % 2 + b % 2) / 2);

• 先各自除 2 再相加，避免相加溢出。
• 餘數部分 `(a%2 + b%2)/2` 處理奇數相加產生的 0.5 進位（整數除法自動截斷）。
• 適用於所有符號組合（正正、正負、負負）。

基準測試 (JMH)

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class AvgBenchmark {
    @Benchmark public int bitwise() { return (a & b) + ((a ^ b) >> 1); }
    @Benchmark public int math() { return a/2 + b/2 + (a%2 + b%2)/2; }
    @Benchmark public int cast() { return (int)((a + b) >>> 1); } // 無符號右移需 long 中轉
}

結果：位運算版與數學版性能接近，均優於 `long` 中轉版（無額外類型轉換開銷）。

適用場景

• 二分查找 `mid = (low + high) / 2` → 改為 `low + ((high - low) >> 1)` 或上述公式。
• 圖像處理像素平均、音頻采樣混合、協議校驗和計算。
• 任何涉及大整數平均的高性能計算路徑。