2進数表示における1の個数 - 球面倶楽部零八式 mark II

では、ある自然数 $a$ の2進数表示における1の個数を求めるにはどうすれば良いかということになるが、

(1) $b$ の $2^0$ の桁が1かどうかの判定は「 $b$ を2で割った余りを求める」

b % 2

または、1とビット毎の AND をとる

b & 1

とすれば良い。

(2) $b$ の $2^1$ の桁が1かどうかの判定は「 $\displaystyle\lfloor \frac{b}{2}\rfloor$ を2で割った余りを求める」ことになるが、
$\displaystyle\lfloor \frac{b}{2}\rfloor$ は、ビットを右シフトすることで実現できることに注意すると

( b >> 1 ) % 2

となり、同様に

( b >> 1 ) & 1

とすれば良い。

(2) $b$ の $2^i$ の桁が1かどうかの判定は「 $\displaystyle\lfloor \frac{b}{2^i}\rfloor$ を2で割った余りを求める」ことになるが、
これは

( b >> i ) % 2

となり、同様に

( b >> i ) & 1

とすれば良い。

これを総合すると、

for( int i = 0 ; i < 32 ; i++) sum +=  ( a>>i ) & 1;

によって(2進数で32桁以下の場合の2進数表示の1の個数を計算することができる。ただ、この愚直なアルゴリズムは遅いので、

bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
bits = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);

が用いられている(32桁以下の2進数の場合)。このアルゴリズムのアイディアは、

2桁の2進数の1の個数は、

( a & 1 ) + ( a >> 1 & 1 )

で計算できる。4桁の2進数の1の個数は、

( a & 1 ) + ( a >> 1 & 1 ) + ( a >> 2 & 1 ) + ( a >> 3 & 1 )

となるが、これを入れ子にして、

( a & 1 ) + ( a >> 1 & 1 ) 
              + ( ( a >> 2 ) & 1 ) + ( ( a >> 2 ) >> 1 & 1 )

とすると、最初の2項は、下2桁の1の個数、最後の2項は上2桁の1の個数を数えていることになる。
これは

( a & 1 ) + ( a >> 1 & 1 ) 
              + ( a & 0b100 ) >> 2 + ( a >> 1 & 0b100 ) >> 2

と変形でき、項を組替えて

( a & 1 ) + ( a & 0b100 ) >> 2 
              +( a >> 1 & 1 ) + ( a >> 1 & 0b100 ) >> 2

となる。よって

( a & 1 ) + ( a & 0b100 ) >> 2

を

( ( a & 1 ) + ( a & 0b100 ) ) & 1 + ( ( ( a & 1 ) + ( a & 0b100 ) )  >> 2 ) & 1

つまり

( a & 0b101 )  & 1 + ( a & 0b101 )  >> 2 ) & 1

のように変形できるというものである。実際、

0x55555555=0b01010101010101010101010101010101

0x33333333=0b00110011001100110011001100110011

0x0f0f0f0f=0b00001111000011110000111100001111

0x00ff00ff=0b00000000111111110000000011111111

0x0000ffff=0b00000000000000001111111111111111

であることから、上から順番に1桁交互、2桁交互、4桁交互、8桁交互、16桁交互で桁を分けていることになっている。

例えば、16桁の2進数 11 01 11 11 10 00 01 11 の1の個数を数えてみる。ビット毎の AND で 0 の相手は無視されるので、それを結果0ではなく x と表現すると1行目の演算は

x1 x1 x1 x1 x0 x0 x1 x1+1 x0 x1 x1 x1 x0 x0 x1 =10 01 10 10 01 00 01 10

となる。これは右から2桁ずつ区切ったときの1の個数を表わしている。2行目の演算は

xx 01 xx 10 xx 00 xx 10 + 10 xx 10 xx 01 xx 01 = 0011 0100 0001 0011

となる。これは右から4桁ずつ区切ったときの1の個数を表わしている。3行目の演算は

xxxx 0100 xxxx 0011 + 0011 xxxx 0001 = 00000111 00000100

となる。これは右から8桁ずつ区切ったときの1の個数を表わしている。4行目の演算は

00000111 + 00000100 = 0000000000001011

となり、これを10進数に直すと11となり、もとの2進数の1の個数が数えられたことになる。

うーん、うまく説明できないなぁ。