【ビット演算】2値の平均をオーバーフローなしで求める方法

はじめに

日本語の記事がパッと見つからなかったので、メモ代わりに書きます。
ビット長ギリギリの大きな値で二分探索する際などに欲しくなります。

結論

以下の通りです。

// ^  := 排他的論理和
// &  := 論理積
// >> := 算術シフト
((x ^ y) >> 1) + (x & y)

なぜ

ふんわりした説明を与えます。

整数値 $a, b$ の足し算を考えます。
$\land$ は値を２進表示した際の各桁の論理積、$\oplus$ は各桁の排他的論理和。
各ビットの繰り上がりについて注目すると、以下の等式が成り立ちます。

a + b = 2 * (a \land b) + a \oplus b 

両辺を $2$ で割ります。

(a + b) / 2 = (a \land b) + (a \oplus b) / 2 

$a \land b$ および $a \oplus b$ は各桁についての演算なので、オーバーフローしません。

注意

結果が 負の値 かつ ２で割り切れない 場合、以下の式２つは違う値を評価します。

(a + b) / 2

((a ^ b) >> 1) + (a & b)

上の式は絶対値の切り捨てを行うのに対して、下の式は切り上げを行います。
負数の補数表現のためにこのような結果になります。

C++ でのサンプル

#include <iostream>

using namespace std;

int naive_avg(int a, int b) {
    return (a + b) / 2;
}

int smart_avg(int a, int b) {
    return ((a ^ b) >> 1) + (a & b);
}

int main(void){
   
    int a = -3, b = -6;
    cout << naive_avg(a, b)<< endl;
    cout << smart_avg(a, b) << endl;

}

結果

-4
-5

注意２

C++ における負値の右シフトが論理シフトであるか、算術シフトであるかは処理系依存である、という有名な話があります。そんなバカな。
ポータブルな実装ではないよ、という注意書きでした。

この話題は別の記事にしようと思います。↓

参考