求平均值，防止溢出（隻針對整數）

       今天看到有人讨論C/C++中求平均數溢出的問題。于是我便仔細的思考并查找相關資料。我們很容易發現 (a +b) / 2, 溢出的來源是加法可能産生進位運算，那麼我們隻要想辦法避免進位運算就可以了。

       因為要避免進位我們很自然的就可以想到位運算。我們可以将a, b分為兩個部分(從二進制的角度來看)，一個是相等的公共部分，另一個則是不相等的部分。我們可以發現計算平均數的進位主要是來自相等部分的相加造成的，是以我們如果直接得到這個公共部分，那麼我們就可以避免這個進位。如果我們觀察不同的部分，我們可以發現要麼是1，要麼是0。如果我們将不同的部分相加除以2，那麼就完成了，對不同部分的取平均值。我們很容易發現這兩個部分相加，就是我們的平均值。是以我們就找到了一個不溢出的方法來計算平均數。接下來我們來幾個例子看一下：

10  二進制  1010
14  二進制  1110
    公共部分： 1010
不同部分的和： 0100
不同部分除以2：0010
平均數 = 1010(相同部分) + 0010(不同部分的平均數) = 1100
是以二者平均數為12
           

    以上的操作我們可以用位運算來替代：

公共部分 = a & b
不同部分的平均值 = (a ^ b) >> 1
平均值 = 公共部分 + 不同部分的平均值 = (a & b) + ((a ^ b) >> 1)
           

    由此，我們直接就可以避免整數加法造成的溢出。仔細觀察會發現，如果整數一個奇數一個偶數，我們的答案就向下取整了。是以如果有需要，我們可以根據 a 和 b 的奇偶情況，手動的添加0.5來修正答案。