ビットをカウントするアルゴリズム

最近、1であるビットをカウントする面白い方法を知った。4つほど例を示す。

1. 普通に全ビットをトラバースする
2. non-zero LSBを消してい
3. 半分ずつに畳みこむ
4. gccの標準関数を使う

以下にそれぞれソースを示す。今回は、32ビット長intに対してビットをカウントすることにする。

まず、普通にstraightforwardな方法で1のビット数を数える方法。

view plainprint?

1. int popcount1(int x) {  
2.  int ret = 0;  
3.   
4.  for (int i = 0; i < 32; i++)  
5.      ret += x >> i & 1;  
6.   
7.  return ret;  
8. }  

int popcount1(int x) {
 int ret = 0;

 for (int i = 0; i < 32; i++)
     ret += x >> i & 1;

 return ret;
}

速度を求められない普通の処理なら上でもいいかもしれないです。次に、non-zero LSBを潰していく方法。これはかなり賢いやり方だと思います。

view plainprint?

1. int popcount2(int x) {  
2.  int ret = 0;  
3.   
4.  while (x) {  
5.      x &= x-1;  
6.      ++ret;  
7.  }  
8.   
9.  return ret;  
10. }  

int popcount2(int x) {
 int ret = 0;

 while (x) {
     x &= x-1;
     ++ret;
 }

 return ret;
}

次に畳みこみながらビットを一か所に寄せて行くやり方。最初みたとき意味不明でした。。これも賢い。。

view plainprint?

1. int popcount3(int x) {  
2.  x = (x & 0x55555555) + (x >> 1 & 0x55555555);  
3.  x = (x & 0x33333333) + (x >> 2 & 0x33333333);  
4.  x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);  
5.  x = (x & 0x00FF00FF) + (x >> 8 & 0x00FF00FF);  
6.  x = (x & 0x0000FFFF) + (x >> 16 & 0x0000FFFF);  
7.   
8.  return x;  
9. }  

int popcount3(int x) {
 x = (x & 0x55555555) + (x >> 1 & 0x55555555);
 x = (x & 0x33333333) + (x >> 2 & 0x33333333);
 x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);
 x = (x & 0x00FF00FF) + (x >> 8 & 0x00FF00FF);
 x = (x & 0x0000FFFF) + (x >> 16 & 0x0000FFFF);

 return x;
}

最後に、gccの標準関数。
　　unsigned int = __builtin_popcount(unsigned int);

はい、いろいろあります。じつは、1のstraightforwardなアルゴリズムは、32bit操作ではなく、毎回1右シフトさせて0になったらやめるというやり方をすれば、かなり速くなります。（私の環境では2.のアルゴリズムとほとんど変わりませんでした・・・・）

以下、10000000までの数値に対して、各関数をまわした場合の処理時間です。

Function Name		Elapsed Time[s]
popcount1		10.31
popcount2		0.65
popcount3		2.35
__builtin_popcount		0.84

popcount3は、ソース長いくせに余り速くないという悲しい結果になりました。いろいろな値が使用されているため、それをレジスタに登録するのに時間を食っているのではないかという考察をしました。