立っているビットの数を数える

　立っているビットの数を数える関数を作る。

//*********************************************************
// 値 uc を２進表記した場合に現れる 1 の数を返す。
//*********************************************************
int // 立っている ビットの数
bitcount
	(
		unsigned char uc
	)
{
	int bit;

	for( bit = 0; 0 != uc; uc = (unsigned char)(uc >> 1) )
	{
		if ( 0 != (uc & 0x01) )
		{
			++bit;
		}
	}
	return bit;
}//bitcount

//*********************************************************
// p から size バイトを２進表記した場合に現れる 1 の数を返す。
//*********************************************************
int // 立っている ビットの数
membitcount
	(
		void *p,
		int   size
	)
{
	int bit;
	unsigned char *uc = (unsigned char *)p;

	for( bit = 0; 0 < size; --size, ++uc )
	{
		bit += bitcount( *uc );
	}

	return bit;
}//membitcount

高速版

//*********************************************************
// [ 8 bits 最適化]
// 8 bits 値 b8 を２進表記した場合に現れる 1 の数を返す。
//*********************************************************
int // 立っている ビットの数
bitcount8
	(
		unsigned char b8 // 8 bits 値
	)
{
	// 8 bits 限定アルゴリズムを利用している
	c_assert( 8 == (CHAR_BIT * sizeof( b8 )) );

	b8 = (unsigned char)( ((b8 & 0xAA) >> 1) + (b8 & 0x55) );
	b8 = (unsigned char)( ((b8 & 0xCC) >> 2) + (b8 & 0x33) );
	b8 = (unsigned char)( ((b8 & 0xF0) >> 4) + (b8 & 0x0F) );

	return b8;
}//bitcount8

//*********************************************************
// [ 16 bits 最適化]
// 16 bits 値 w16 を２進表記した場合に現れる 1 の数を返す。
//*********************************************************
int // 立っている ビットの数
bitcount16
	(
		unsigned short w16 // 16 bits 値
	)
{
	// 16 bits 限定アルゴリズムを利用している
	c_assert( 16 == (CHAR_BIT * sizeof( w16 )) );

	w16 = (unsigned short)( ((w16 & 0xAAAA) >> 1) + (w16 & 0x5555) );
	w16 = (unsigned short)( ((w16 & 0xCCCC) >> 2) + (w16 & 0x3333) );
	w16 = (unsigned short)( ((w16 & 0xF0F0) >> 4) + (w16 & 0x0F0F) );
	w16 = (unsigned short)( ((w16 & 0xFF00) >> 8) + (w16 & 0x00FF) );

	return w16;
}//bitcount16

//*********************************************************
// [ 32 bits 最適化]
// 32 bits 値 dw32 を２進表記した場合に現れる 1 の数を返す。
//*********************************************************
int // 立っている ビットの数
bitcount32
	(
		unsigned long dw32 // 32 bits 値
	)
{
	// 32 bits 限定アルゴリズムを利用している
	c_assert( 32 == (CHAR_BIT * sizeof( dw32 )) );

	dw32 = ((dw32 & 0xAAAAAAAA) >>  1) + (dw32 & 0x55555555);
	dw32 = ((dw32 & 0xCCCCCCCC) >>  2) + (dw32 & 0x33333333);
	dw32 = ((dw32 & 0xF0F0F0F0) >>  4) + (dw32 & 0x0F0F0F0F);
	dw32 = ((dw32 & 0xFF00FF00) >>  8) + (dw32 & 0x00FF00FF);
	dw32 = ((dw32 & 0xFFFF0000) >> 16) + (dw32 & 0x0000FFFF);

	return dw32;
}//bitcount32

使用例

// 関数 bitcount(), membitcount() の使用例です。
// 出力された配列 bits[] の n 番目の要素 bits[n] は
// 8 bits 値 n (0 〜 255) を２進表記した場合に現れる 1 の数を示しています。
// つまり bits[n] == bitcount8( n ) です。
int main( void )
{
	unsigned char uc[ UCHAR_MAX ];
	char separator = '{';

	puts( "int bits[] = " );
	{for( int i = 0; i <= UCHAR_MAX; ++i )
	{
		uc[ i ] = (unsigned char)( i );
		printf( "%c %s%d", separator, (0 == (i & 0x0F) ? "\n\t" : ""), bitcount( uc[ i ] ) );
		separator = ',';
	}}
	puts( "\n};" );
	
	printf( "\nsum of bits[] = %d;\n", membitcount( uc, sizeof(uc) ) );

	return 0;
}//main

実行結果

int bits[] =
{
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

sum of bits[] = 1016;