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

（前回の続き）

１ビット

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

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

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

２ビット

２ビットのときはどうでしょう
ビットが２つあるときにとりうるパターン（数値）は 00, 01, 10, 11 の４種類で、このとき立っているビットの数は、両方のビットが立っている（＝２個）か、どちらか片方のビットだけが立っている（＝１個）か、どちらのビットも立っていない（＝０個）かの３種類です。２ビットなのですから立っているビットの数が 0個 〜 2個 なのは当たり前ですね
この２ビットの４種類のパターン（数値）からそのとき立っているビット数３種類を求めるには、上位ビットと下位ビットを揃えて単純に足せばいいだけだ。というところに 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 )

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

４ビット

２ビットができれば当然４ビットもできます
４ビットの場合は４ビットを上位の２ビットと下位の２ビットに分けると上記の方法でそれぞれの２ビットで立っているビットの数を得ることができます
このとき２つの２ビットで立っているビット数のとりうるパターンは 00 00, 00 01, 00 10, 01 00, 01 01, 01 10, 10 00, 10 01, 10 10 の９種類です
この９種類のパターンが表すビット数は下記のように 0個 〜 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 )

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

８ビット

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

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

１６ビット

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

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

３２ビット

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

 ( 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;
}

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

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