bit counting in C

방법 1.

int count_bits( unsigned int data )
{
	int cnt = 0;

	while( data != 0 ) {
		data = data & (data − 1);
		cnt++;
	}

	return cnt;
}

방법 2.

방법1로 테이블을 만들어 사용.

static unsigned char byte_bit_count[256];	/∗ lookup table ∗/

void initialize_count_bits()
{
	int cnt, i, data;

	for ( i = 0; i < 256; i ++ ) {
		cnt = 0;
		data = i ;

		while( data != 0 ) {	/∗ method one ∗/
			data = data & (data − 1);
			cnt++;
		}

		byte_bit_count[i] = cnt;
	}
}

int count bits ( unsigned int data )
{
	const unsigned char∗ byte = (unsigned char ∗) & data;

	return byte_bit_count[byte[0]] + byte_bit_count[byte[1]] +
			byte_bit_count[byte[2]] + byte_bit_count[byte[3]];
}

방법3.

int count_bits(unsigned int x)
{
	static unsigned int mask[] = {	0x55555555,
									0x33333333,
									0x0F0F0F0F,
									0x00FF00FF,
									0x0000FFFF };
	int i;
	int shift;	/∗ number of positions to shift to right ∗/


	for (i =0, shift =1; i < 5; i ++, shift ∗= 2)
		x = (x & mask[i]) + ((x >> shift) & mask[i]);

	return x;
}

PC Assembly Language에서 인용. http://www.drpaulcarter.com/