Counting Bits

The counting number of bits which is set to 1 in the given binary number is a known problem. This problem has been asked in interviews many times. The C Programming Language by K&R explains the solution to this problem. The answer is very simple. It counts the number of bits by subtracting the number by one during each iteration of loop. The complexity of this solution is where n is total number of bits in the given number. So, for a 32 bits number, it will take maximum 32 subtractions.

Lets move on to the next solution for the same problem. Here, we will use table method.

Create a table for x bits number with stored information for number of 1’s bits in it. So, for a number having larger bits than x, divide it into blocks of x bits. Now, for each x bits blocks, find out bit count of 1’s using table and than sum it up. The complexity of this solution is . So, for a 8-bit table and a 32-bit number, it takes 4 addition to find the counts and for 64 bits number it will take 8 addition. I think this is the same solution used on UNIX systems.

Now, lets examine another solution using binary tree.

Imagine each bit as a leaf of binary tree and each non-left node as sum of its children bit count. Than the root node contains the total number of bits which set to 1 for the given number. Am I right? What would be the complexity? How many summation requires? If we do summation for each non-leaf node than the complexity is equal to total number of non-leaf node which is of order n. However, if we can do summation level by level and each level costs us only one summation than the complexity of the problem is . We can achieve this using bitwise operations. Below is the sample pseudo code for this solution for 16-bit numbers.

tbl[] = {0x5555, 0x3333, 0x0f0f, 0x00ff}

bitcnt16(n):
repeat for i=0 to i=3
n = (n & tbl[i]) + ((n >> (i+1)) & tbl[i])

We can see that we have created a table of constants for each level. So the size of table is also . Using the above method, number of 1’s for 32 bits number is calculated using maximum 5 addition.

Do you have any other answer to this problem? Can we improve it more?