ループを使わずに配列を逆順にする

巷ではこんな話題が流行っているらしいのだが、何か違和感を感じた。ようは再帰で書けという事なのだろうが、末尾再帰はループに展開できるはず。ただこの問題をといても面白くないので、もう一つの方の問題を解いてみる。この問題は2chにのどこかに書かれていた問題で、そのスレ内の正答者はいなかったように思う。

白黒2色の画像を考える。この画像の横方向の画素は整数の各ビットに対応する。すなわち0x12であれば「黒白白黒白」に対応する。この画像を左右反転させるためのコードを書け。

ハッカーのたのしみに載っている解答はこれ。

int reverse(int x) {
	x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
	x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
	x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
	x = ((x & 0x00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF);
	x = ((x & 0x0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF);
	return x;
}

FFTにも使われているので有名なルーチンなのだと思う。gccならビルトイン関数があったりするんじゃなかろうか。