今日の井原

2chでおもしろいものを見つけた。

こんなものでビットが数えられるのかよ……と動かしてみると、なるほどばっちりではないですか。でもどうしてこんなコードが機能するんでしょう。とっても不思議です。こういうときには逆から辿ってみるのが定石。やってみよう。

先ず「return (i >> 16) + (i & 0x0000FFFF);」を見る。この行では上16bitと下16bitを整数型として足し合わせている。なので、この時点でビット数は上16bitと下16bitに分けてカウントされているということになる。

次に「i = ((i >> 8) & 0x00FF00FF) + (i & 0x00FF00FF);」を見る。んん。ここから分かりにくくなるのね。２バイト目と４バイト目をマスクして、片方は8bitシフトして足し合わせている。つまり、４バイトを４つのchar（8bitの整数型）と見なして、１つ目と２つ目を足したものを上16bitに、３つ目と４つ目を足したものを16bitに格納している。ああ、なるほど。なんとなく見えてきたような気がする。

「i = ((i >> 4) & 0x0F0F0F0F) + (i & 0x0F0F0F0F);」を見る。これも前の行と同じ考え方だ。４バイトを4bitの整数型×８個として、隣り合う２つずつをセットにして足し合わせている。なるほどね。これをやつは考えた頭良いなあ。

つまり、32bitあるのを1bitずつ順番にカウントする（fuckinBitCount）のではなく、最初のステップで2bitずつをカウントし、次のステップではその結果を足し合わせることで4bitずつカウントし……って繰り返していくことで、全体として少ない手数でビットをカウントできている（excellentBitCount）。分割統治ってやつだ。実際、この２つのビットカウントアルゴリズムの関係はバブルソートとクイックソートの関係そのままで、ある考え方を他の問題に応用することの偉大さみたいなものを感じてしまった（ちょっと大仰かもしれんけど）。こういうコードを考えつくやつを心から尊敬します。

You can ping this entry by using http://windy.ac/MT/mt-tb.cgi/363 .