if文(条件分岐)を使わず、max(a, b) を計算 別解(2)

前項がはてなブックマークされ、大量のアクセスが殺到してます。ありあとうございます。

xor と 比較演算子を使用する方法

で、新たな別解を @n_soda 氏に教えてもらった。
参照:Compute the minimum (min) or maximum (max) of two integers without branching

int max(int a, int b) {
    return a ^ ((a ^ b) & -(a < b));
}

a < b は 1 or 0 なので、符号反転し、0xffffffff or 0 となる。
後は xor の性質を使い、最大値を求めている。

a < b ならば a^((a^b)&0xffffffff) = a^(a^b) = b
a >= b ならば a^((a^b)&0) = a^0 = a

となる。
この方法ならば、オーバーフローの心配もなく、どんな値でも max を求めることが出来る。
素晴らしい。

気になるのは、a < b の部分は条件分岐を使わないのか?という点だ。

VS2013 で Release モードでビルドし、アセンブラコードを見て見ると、以下のようになっていた。

mov ecx,dword ptr [esp+4]   ; ecx := a
xor edx,edx                             ; edx := 0
mov eax,dword ptr [esp+8]   ; eax := b
cmp ecx,eax                           ; a – b を計算し、フラグを立てる
setl dl                                     ; a < b なら edx = 1, a >=b なら edx = 0

なんと、a < b も分岐命令を使わないのだ。setl というのもおいらは知らない命令だったが、条件が成立していたら1を設定するものらしい。3行前であらかじめ edx を 0に設定しているのがミソだ。

つまり、最近のCPU・コンパイラであれば 比較演算子を使っても条件分岐を行わないということみたいじゃ。

比較演算子とテーブルを使用する解

a < b を使っていいのなら、以下の様にテーブルを使う解も当然ありだ。

int max(int a, int b) {
    const int t[] = { a, b };
    return t[a<b];
}