Counting Bits in C

Presenting a nice way of counting the ‘1’ bits of a given integer in C, sacrificing some memory for speed. Comparison with the simple bit-shifting bit by bit method provided.

I would like to quickly share a nice algorithm that I saw which counts the number of ‘1’ bits that a given integer has. So simply a function so that the program below would print “Number of ON bits of 8895 is 9”.

int main()
{
	int num = 8895;
	printf("Number of ON bits of %d is %d\n",num,countBits(num));
	return 0;
}

The simple way to accomplish this would be to go through each bit of the integer and check if it is zero or one. Something like below.

//A simple way to count the '1' bits of an integer
int countBits_simple(int num)
{
	int result = 0;
	//as long as the number is not zero
	while(num != 0)
	{
		//if this bit is 1 increase the counter
		if(num&0x1)		
			result++;
		num=num>>1;//and always keep shifting right
	}
	return result;
}

This algorithm has O(n) complexity as far as comparisons are concerned with n being the number of bits that the integer has. If we are prepared to sacrifice some memory, this can happen a lot faster. We can maintain a precomputed array of the ‘1’ bits count of some numbers. For simplicity’s sake let’s say that we will keep an array of 4-bit numbers count. So we will have something like below:

//the array of precomputed counts of '1' bits for the numbers 0 to 15
static char precomputed[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 
//using a precomputed array to count the '1' bits of an integer
int countBits(int num)
{
	int result=0;
	//as long as the number is not zero
	while(num != 0)
	{//check every 4 bits
		result+=precomputed[num&0xF];
		num=num>>4;//and move right by 4 bits
	}
	return result;
}

In the above we have an array with precomputed counts of ‘1’ bits for numbers zero to fifteen(4 bit numbers). This is used in order to calculate how many ‘1’ bits every 4 bits of the number contain. This way we can read through the integer 4 times as fast, since we simply read every 4 bits. So in the end the complexity of the algorithm is O(n/4) where n is the number of bits of the given integer.

This method can of course be taken a step further by simply keeping a bigger precomputed array. If for example we had an array with size 255 we could hold the count of ‘1’ bits for all possible numbers a byte can hold. This way we could go through the given integer byte by byte and end up with an algorithm of complexity O(n/8).

So there it is. A kind of smarter way to count the ‘1’ bits of a given integer as long as you are prepared to do some memory/speed tradeoffs.

If the post caught your interest and you love C programming in general why not check my work in the Refu Library? It currently needs more contributors and people who are able and willing to provide feedback! You could be one of them 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.