Hacker's Delight 5章にあるビットの数え方

(前回の続き)

1ビット

ビットが1つあるときにとりうるパターン(数値)は 0, 1 の2種類で、このとき立っているビットの数も 0個か 1個です

数値が 0 なら立っているビットの数も 0個
数値が 1 なら立っているビットの数も 1個

これは考えるまでもありませんね

2ビット

2ビットのときはどうでしょう
ビットが2つあるときにとりうるパターン(数値)は 00, 01, 10, 11 の4種類で、このとき立っているビットの数は、両方のビットが立っている(=2個)か、どちらか片方のビットだけが立っている(=1個)か、どちらのビットも立っていない(=0個)かの3種類です。2ビットなのですから立っているビットの数が 0個 〜 2個 なのは当たり前ですね
この2ビットの4種類のパターン(数値)からそのとき立っているビット数3種類を求めるには、上位ビットと下位ビットを揃えて単純に足せばいいだけだ。というところに Hacker's Delight は注目しています

数値が 00 のときに立っているビットの数は 0 + 0 = 0個
数値が 01 のときに立っているビットの数は 0 + 1 = 1個
数値が 10 のときに立っているビットの数は 1 + 0 = 1個
数値が 11 のときに立っているビットの数は 1 + 1 = 2個

これを C/C++ 的に書くと下記のようになります

数値が 00 のときに立っているビット数は ( 00 & 01 ) + (( 00 >> 1 ) & 01 ) = 00 + 00 = 0個
数値が 01 のときに立っているビット数は ( 01 & 01 ) + (( 01 >> 1 ) & 01 ) = 01 + 00 = 1個
数値が 10 のときに立っているビット数は ( 10 & 01 ) + (( 10 >> 1 ) & 01 ) = 00 + 01 = 1個
数値が 11 のときに立っているビット数は ( 11 & 01 ) + (( 11 >> 1 ) & 01 ) = 01 + 01 = 2個

これをまとめると下記のようになりますね

( value_2bit & 01 ) + (( value_2bit >> 1 ) & 01 )

このように2ビットで考えると、ループを使わなくても論理演算・算術演算だけで数値からそのとき立っているビット数を求めることができました
この2ビットのときの求め方がこの先の基礎になります

4ビット

2ビットができれば当然4ビットもできます
4ビットの場合は4ビットを上位の2ビットと下位の2ビットに分けると上記の方法でそれぞれの2ビットで立っているビットの数を得ることができます
このとき2つの2ビットで立っているビット数のとりうるパターンは 00 00, 00 01, 00 10, 01 00, 01 01, 01 10, 10 00, 10 01, 10 10 の9種類です
この9種類のパターンが表すビット数は下記のように 0個 〜 4個の5種類になります。4ビットなのですから立っているビット数が 0個 〜 4個なのは当たり前ですね

立っているビット数が 00 と 00 のときこれを合わせると ( 0000 & 0011 ) + (( 0000 >> 2 ) & 0011 ) = 0000 + 0000 = 0個
立っているビット数が 00 と 01 のときこれを合わせると ( 0001 & 0011 ) + (( 0001 >> 2 ) & 0011 ) = 0001 + 0000 = 1個
立っているビット数が 00 と 10 のときこれを合わせると ( 0010 & 0011 ) + (( 0010 >> 2 ) & 0011 ) = 0010 + 0000 = 2個
立っているビット数が 01 と 00 のときこれを合わせると ( 0100 & 0011 ) + (( 0100 >> 2 ) & 0011 ) = 0000 + 0001 = 1個
立っているビット数が 01 と 01 のときこれを合わせると ( 0101 & 0011 ) + (( 0101 >> 2 ) & 0011 ) = 0001 + 0001 = 2個
立っているビット数が 01 と 10 のときこれを合わせると ( 0110 & 0011 ) + (( 0110 >> 2 ) & 0011 ) = 0010 + 0001 = 3個
立っているビット数が 10 と 00 のときこれを合わせると ( 1000 & 0011 ) + (( 1000 >> 2 ) & 0011 ) = 0000 + 0010 = 2個
立っているビット数が 10 と 01 のときこれを合わせると ( 1001 & 0011 ) + (( 1001 >> 2 ) & 0011 ) = 0001 + 0010 = 3個
立っているビット数が 10 と 10 のときこれを合わせると ( 1010 & 0011 ) + (( 1010 >> 2 ) & 0011 ) = 0010 + 0010 = 4個

これをまとめると下記のようになります

( value_4bit & 0011 ) + (( value_4bit >> 2 ) & 0011 )

つまりこれは2ビットのときに上位ビットと下位ビットを揃えて足したのと同じで、上位2ビットと下位2ビットを揃えて足しているだけのことです
このように4ビットのときも立っているビットの数を数えるのにループを使う必要がなくなりました

8ビット

4ビットができれば8ビットもできます
8ビットではさらに上位4ビットと下位4ビットを揃えて足します

( value_8bit & 00001111 ) + (( value_8bit >> 4 ) & 00001111 )

16ビット

8ビットができれば16ビットもできます
16ビットではさらに上位8ビットと下位8ビットを揃えて足します

 ( value_16bit & 0000000011111111 ) + (( value_16bit >> 8 ) & 0000000011111111 )

32ビット

16ビットができれば32ビットもできます
32ビットではさらに上位16ビットと下位16ビットを揃えて足します

 ( value_32bit & 00000000000000001111111111111111 ) + (( value_32bit >> 16 ) & 00000000000000001111111111111111 )

それ以上

これを繰り返してしてゆけば何ビットであっても任意の数値で立っているビットの数をループすることなく数えることができます
おもしろいですね

実装例

inline uint8_t	bit_count_population8( uint8_t	b ) {
	b = ( uint8_t )(( b & 0x55 ) + (( b >> 1 ) & 0x55 ));	// 01010101
	b = ( uint8_t )(( b & 0x33 ) + (( b >> 2 ) & 0x33 ));	// 00110011
	b = ( uint8_t )(( b & 0x0f ) + (( b >> 4 ) & 0x0f ));	// 00001111
	return	b;
}
inline uint16_t	bit_count_population16( uint16_t	w ) {
	w = ( uint16_t )(( w & 0x5555 ) + (( w >> 1 ) & 0x5555 ));	// 0101010101010101
	w = ( uint16_t )(( w & 0x3333 ) + (( w >> 2 ) & 0x3333 ));	// 0011001100110011
	w = ( uint16_t )(( w & 0x0f0f ) + (( w >> 4 ) & 0x0f0f ));	// 0000111100001111
	w = ( uint16_t )(( w & 0x00ff ) + (( w >> 8 ) & 0x00ff ));	// 0000000011111111
	return	w;
}
inline uint32_t	bit_count_population32( uint32_t	dw ) {
	dw = ( uint32_t )(( dw & 0x55555555 ) + (( dw >>  1 ) & 0x55555555 ));	// 01010101010101010101010101010101
	dw = ( uint32_t )(( dw & 0x33333333 ) + (( dw >>  2 ) & 0x33333333 ));	// 00110011001100110011001100110011
	dw = ( uint32_t )(( dw & 0x0f0f0f0f ) + (( dw >>  4 ) & 0x0f0f0f0f ));	// 00001111000011110000111100001111
	dw = ( uint32_t )(( dw & 0x00ff00ff ) + (( dw >>  8 ) & 0x00ff00ff ));	// 00000000111111110000000011111111
	dw = ( uint32_t )(( dw & 0x0000ffff ) + (( dw >> 16 ) & 0x0000ffff ));	// 00000000000000001111111111111111
	return	dw;
}

本に載っているコードを仕事に使わない

何度も言っていますが、本に載っているコードでもウェブに出ているコードでも、外部のコードを勝手に仕事に使うようなことは絶対にやってはいけません
外部コードを使っていいかどうかの調査や、使用にあたっての手続きなどの決まりがあります
使いたいものがあるときは先輩や上長に相談するようにしてください