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

通常、int max(int a, int b) は以下のように実装される(非テンプレートの場合)。

int max(int a, int b)
{
    return a > b ? a : b;
}
int max(int a, int b)
{
    if( a > b )
        return a;
    else
        return b;
}

これを if文, ?: を使わずに書くにはどうしたらいいだろうか?

実はビット演算を使うとそれが出来てしまうのだ。

答えは以下のとおり(int は 32bit 符号付き整数と仮定)。

int max(int a, int b)
{
    int t = (a - b) >> 31;  // a>=b ならば0, a<b ならば 0xffffffff
    return (a & ~t) | (b & t);
}

符号付き整数を右シフトすると、最上位の符号ビットが維持されたままになる性質を利用している。
ご理解いただけたであろうか?

if文を使わずこんなことをしていったい何の意味があるのかと懐疑的な読者もいることだろう。
実は最近のCPUはパイプライン+分岐予測を行っているので、条件分岐があり、分岐予測に失敗すると、パイプラインをクリアする必要があり、処理が遅くなることがあるのだ。
条件分岐を使わず論理演算だけで済ますと、そういうことがなく処理が高速になることがある。

また、ある種の並列マシンでは、データは並列CPUでアクセスできるのだが、プログラムカウンタが共通、という仕様のものがあるのだそうだ。そういうマシンでは各データごとで異なる条件分岐を行うことができないので、このようなテクニックを使わざるをえないのだそうじゃ。

追記(2014/12/03):

別解も書きましたよ

ニコ生でM氏に、オーバーフローする場合があるというご指摘をいただいだ。
たしかに、a, b の差が0x7fffffff を越えていると、結果が正しくならないようだ。