色んなアルゴリズムでビット数をカウントしてみる
ビット数をカウントするアルゴリズムには色んな種類があるそうで、そのうち4つのアルゴリズムのC言語による実装とベンチマークです。
1. 普通に思いつく方法
gist80d8b366e9c1541871c570f3fc00b712
1ビットずつ右にシフトして、1でマスクすることでビット数を数えます。
多分最初に思いつくのはこの方法だと思います。
unsigendで0x00000000~0xffffffffまでのビット数を数えるのにかかった時間はこれくらい。コンパイラによる最適化は無効化しています。
real 7m38.640s user 7m32.387s sys 0m01.307s
2. ギリギリ思いつくかもしれない方法
gist339a827715dac7a31bd147d75ee1157c
n&=n-1;
でセットされた最下位のビットを0にすることができます。
頭の良い人なら思いつくらしいのですが、僕は頭が悪いので思いつけませんでした。
ベンチマークはこれくらい。
real 3m34.147s user 3m32.591s sys 0m00.429s
ただし、この方法は入力によって計算時間に偏りがあるので、ビットが疎な場合に限ると高速です。
3. あらかじめテーブルを持っておく方法
gistfb6975c5ac4067aab339a45de73bbb2d
0~255のとき、それぞれいくつのビットが立っているかを持っておくことで、そこそこ高速に求めることができます。これは思いつけるはず。
real 2m24.805s user 2m19.969s sys 0m00.714s
追記 : 要素数256の配列をいちいち確保して、初期化するのはオーバーヘッドが大きいので、テーブルを静的変数にしたらかなり速くなりました。
real 0m32.511s user 0m32.348s sys 0m0.056s
4. ループを使わない方法
gist0d00dd5f598995fb30d1c08c8b384ee8
この方法もそこそこ速いけど 3ビットごとに分割してカウントするので、32ビットのうち30ビットまでしかカウントすることができません。
real 0m38.656s user 0m38.535s sys 0m00.053s
5. 人類の到達点
giste7edf3bc9a7eaf0ee63aeb01079d3d21
1960年代に人類はこのアルゴリズムに到達したらしい。
現状では最も高速なアルゴリズムです。
ただし、実際に最速で計算できるよのは intel x86 が SSE 4.2 から導入した POPCNT というビット数を数えるCPU命令です。
とりあえず意味わからないと思うので、ちょっと解説。
n=1100 1010 0000 0110 1111 0001 1101 1011(2)
の場合を考えてみます。セットされたビットを数えてみると答えは17になるはずです。
まず1行目のn&0x55555555の部分は、
1100 1010 0000 0110 1111 0001 1101 1011
& ) 0101 0101 0101 0101 0101 0101 0101 0101
*1*0 *0*0 *0*0 *1*0 *1*1 *0*1 *1*1 *0*1 ...(a)
マスクされて0になったビットは隠しています。
次にn>>1&0x55555555は(n&0xaaaaaaaa)>>1と読み換えることができるので、
1100 1010 0000 0110 1111 0001 1101 1011
& ) 1010 1010 1010 1010 1010 1010 1010 1010
>>1) 1*0* 1*1* 0*0* 0*1* 1*1* 0*0* 1*0* 1*1*
?1*0 *1*1 *0*0 *0*1 *1*1 *0*0 *1*0 *1*1 ...(b)
C言語では論理シフトなのか、算術シフトなのかは処理系定義なので、「？」としています。どちらの処理系でも問題なく動くので、よく分からない人はスルーしてください。
そして、a+bをすれば一行目は終わりです。
*1*0 *0*0 *0*0 *1*0 *1*1 *0*1 *1*1 *0*1 ...(a)
+ ) ?1*0 *1*1 *0*0 *0*1 *1*1 *0*0 *1*0 *1*1 ...(b)
1000 0101 0000 0101 1010 0001 1001 0110 ...(c)
さて、ここでnとcを見比べてみましょう。
n = 1100 1010 0000 0110 1111 0001 1101 1011
c = 1000 0101 0000 0101 1010 0001 1001 0110
これを2ビットずつに区切ってcを10進数に変換してみると、あるパターンが見えてきます。
n = 11 00 10 10 00 00 01 10 11 11 00 01 11 01 10 11
c = 2 0 1 1 0 0 1 1 2 2 0 1 2 1 1 2
|
n |
00 |
01 |
10 |
11 |
|
c |
0 |
1 |
1 |
2 |
nとcにはこういう対応があり、
00のときは0、
01や10のときは1、
11のときに2なので、
2ビットごとのセットされたビット数を数えられていることが分かります。
次の行はn(さっき計算したc)&0x33333333から始まります。
1000 0101 0000 0101 1010 0001 1001 0110 ...(c)
& ) 0011 0011 0011 0011 0011 0011 0011 0011
**00 **01 **00 **01 **10 **01 **01 **10 ...(d)
n>>2&0x33333333を(n&0xcccccccc)>>2に置き換えて、
1000 0101 0000 0101 1010 0001 1001 0110 ...(c)
& ) 1100 1100 1100 1100 1100 1100 1100 1100
>>2) 10** 01** 00** 01** 10** 00** 10** 01**
??10 **01 **00 **01 **10 **00 **10 **01 ...(e)
d+eを求める。
**00 **01 **00 **01 **10 **01 **01 **10 ...(d)
+ ) ??10 **01 **00 **01 **10 **00 **10 **01 ...(e)
0010 0010 0000 0010 0100 0001 0011 0011 ...(f)
ここで、もう一度nとfを比較してみると、
n = 1100 1010 0000 0110 1111 0001 1101 1011
f = 2 2 0 2 4 1 3 3
0000 → 0
0001,0010,0100,1000 → 1
0011,0101,1001,0110,1010,1100 → 2
0111,1011,1101,1110 → 3
1111 → 4
となっているので、今度は4ビットごとのセットされたビット数を数えられています。
だんだん原理が分かってきましたね。
次の行も同様にして、
0010 0010 0000 0010 0100 0001 0011 0011 ...(f)
& ) 0000 1111 0000 1111 0000 1111 0000 1111
**** 0010 **** 0010 **** 0001 **** 0011 ...(g)
0010 0010 0000 0010 0100 0001 0011 0011 ...(f)
& ) 1111 0000 1111 0000 1111 0000 1111 0000
>>4) 0010 **** 0000 **** 0100 **** 0011 ****
0000 0010 **** 0000 **** 0100 **** 0011 ...(h)
**** 0010 **** 0010 **** 0001 **** 0011 ...(g)
+ ) 0000 0010 **** 0000 **** 0100 **** 0011 ...(h)
0000 0100 0000 0010 0000 0101 0000 0110 ...(i)
それではnとiを比較すると8ビットずつのセットされたビット数えられているのはもう分かりますね。
n = 11001010 00000110 11110001 11011011
i = 4 2 5 6
それでは4行目も行きましょう。
0000 0100 0000 0010 0000 0101 0000 0110 ...(i)
& ) 0000 0000 1111 1111 0000 0000 1111 1111
**** **** 0000 0010 **** **** 0000 0110 ...(j)
0000 0100 0000 0010 0000 0101 0000 0110 ...(i)
& ) 1111 1111 0000 0000 1111 1111 0000 0000
>>8) 0000 0100 **** **** 0000 0101 **** ****
0000 0000 0000 0100 **** **** 0000 0101 ...(k)
**** **** 0000 0010 **** **** 0000 0110 ...(j)
+ ) 0000 0000 0000 0100 **** **** 0000 0101 ...(k)
0000 0000 0000 0110 0000 0000 0000 1011 ...(l)
n = 1100101000000110 1111000111011011
i = 6 11
最後に5行目です。
0000 0000 0000 0110 0000 0000 0000 1011 ...(l)
& ) 0000 0000 0000 0000 1111 1111 1111 1111
**** **** **** **** 0000 0000 0000 0110 ...(m)
0000 0000 0000 0110 0000 0000 0000 1011 ...(l)
& ) 1111 1111 1111 1111 0000 0000 0000 0000
>>8) 0000 0000 0000 0110 **** **** **** ****
0000 0000 0000 0000 0000 0000 0000 0110 ...(o)
**** **** **** **** 0000 0000 0000 0110 ...(m)
+ ) 0000 0000 0000 0000 0000 0000 0000 0110 ...(o)
0000 0000 0000 0000 0000 0000 0000 1010...(p)
n = 11001010000001101111000111011011
p = 17
最終的に数えることができましたね。
というわけで、隣接するビットをマージすることで数える方法でした。
real 0m37.119s user 0m37.005s sys 0m00.057s
おまけ
卒倒しそうになるクレイジーなマクロ実装。内容は5と同じです。
giste7db420b865ac71e43db7ffff7ea5bb4
real 0m10.755s user 0m10.710s sys 0m00.018s
おまけ2
わざわざコピペしなくても、gccなら__builtin_popcount(unsigned int)で、お手軽に高速実装を使えます。
real 0m10.927s user 0m10.884s sys 0m00.017s
おまけ3
ベンチマークまとめ。
効率は1.のやり方を「1」とした、計算時間の比です。
|
|
1 |
2 |
3 |
4 |
5 |
おまけ1 |
おまけ2 |
|
real |
458.640 |
214.147 |
32.511 |
38.656 |
37.119 |
10.755 |
10.927 |
|
user |
450.387 |
212.591 |
32.348 |
38.535 |
37.005 |
10.710 |
10.884 |
|
sys |
1.307 |
0.429 |
0.056 |
0.053 |
0.057 |
0.018 |
0.017 |
|
効率 |
1 |
0.467 |
0.071 |
0.084 |
0.081 |
0.023 |
0.024 |
だいたい98%も高速化できたので、50倍くらい速くなりましたね。
