intデータの1のビット個数をカウント

さっき面白い話題を見つけたので、ここでも紹介。


Java の Integer クラスに、int bitCount(int) という、intデータのうちビットが1の個数を数えるメソッドがある。

例えば、10 は2進数表現で 00…001010 と、１が２つあるので bitCount(10) の値は 2 になる。


１の個数を数えるだけだから、まずはじめに思いつく方法は、ビットを全部スキャンして2進数表現で１になってるとこをチェックする愚直なやり方。

この素朴な方法の計算量は、ビット長 n に対して O(n) 。


しかし、Integer.bitCount() はそんなことを一切しないで、O(log n) で動く以下のロジックが実装されている。（ここで int 型は32ビット）

    public static int bitCount(int i) {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

この処理はいったい何をしているのか？


はじめに見たときはこの６行の処理の意味が分からず、これがなんで１の個数を数えることになるのかと考え込んでしまった。

この黒魔術を相手に延々と悩んだ末、数10分もの時間をかけてようやくひらめいた。





以下、解答が書いてあるので、自分で考えたい人は読まないでください。












一度理解してしまえばなんのことはない。黒魔術と言うほどのものでもない。

さっきの６行の中に出てきた一見奇妙な16進数の定数は、2進数表現にすると以下のようになる。

0x55555555：01010101010101010101010101010101 
0x33333333：00110011001100110011001100110011 
0x0f0f0f0f：00001111000011110000111100001111 
0x3f　　　：00000000000000000000000000111111 

//int型は32ビット
    public static int bitCount(int i) {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

１行目の処理は、

00 → 00 - 00 = 00
01 → 01 - 00 = 01
10 → 10 - 01 = 01
11 → 11 - 01 = 10

という演算を、隣のビットとの組の16組で計算して、2ビット間隔で結果を記憶している。

つまり、2ビットのうち1になってる個数を2ビットの2進数表現で保存して、それを１６個並べている、という処理。


次は、隣りの2ビット組とで足し算をして、結果を4ビットずつ８個並べて記憶。

次は、隣りの4ビット組とで足し算をして、結果を8ビットずつ４個並べて記憶。

次は、隣りの8ビット組とで足し算をして、結果を16ビットずつ２個並べて記憶。

最後は、隣りの16ビット組とで足し算をして、32ビットの結果から余計な7ビット目以上を消して終わり。



マージソートアルゴリズムのイメージと全く同じ。



これでビットカウントが O(log n) 時間で実行できる。







これをひらめいたときは「なるほど！」と一瞬感動したが、こんな見たまんまのロジックに数10分間も気付かなかった自分が非常に残念に思えてきてしまった…。


この程度で時間かかってるばかりか、O(log n) 時間で数えるアルゴリズムを自分で思いつかないようじゃまだまだ…。