Counting bits

Determining the number of bits set to 1 in a particular value is an interesting problem, commonly referred to as a population count, and often referred to in assembly language simply as pop. My favorite approach to this problem, and the way it is often implemented in cpu hardware is a recursive approach, and is almost like the reverse of a binary search in the way it accomplishes counting the bits set to 1 in a register value.

Suppose that our registers are n-bit registers. Divide the problem into two halves, and we now need to count the number of one bits in two n/2 bit values. We continue onto four n/4 bit values, eight n/8 bit values, etc. until the number of bits in each value we are counting is two, a trivially easy problem.

1
2
3
4
5
6
7
8
9
10
11
12
13

/* we start with 23 / 32 bits set in our register: 0xbc637eff */
1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1|
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
0 1|1 0|1 0|0 0|0 1|0 1|0 0|1 0|0 1|1 0|1 0|0 1|1 0|1 0|1 0|1 0|
       |       |       |       |       |       |       |       |
0 0 1 1|0 0 1 0|0 0 1 0|0 0 1 0|0 0 1 1|0 0 1 1|0 1 0 0|0 1 0 0|
               |               |               |               |
0 0 0 0 0 1 0 1|0 0 0 0 0 1 0 0|0 0 0 0 0 1 1 0|0 0 0 0 1 0 0 0|
                               |                               |
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1|0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0|
                                                               |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1| 
/* result is decimal 23 */

The value we started with is 0xbc637eff. It is used for this example because it has a rather average population count.

The code for this algorithm is much like the code for reversing bits in a register, and uses the same divide and conquer approach that we see in binary search.

1
2
3
4
5
6
7
8
9
10
11
12

int main(int argc, char **argv)
{
  unsigned int x = 0xbc637eff;

  /* note: the order of these assignment statements is irrelevant. */
  x = (x & 0x55555555 + ((x >> 1)  & 0x55555555);
  x = (x & 0x33333333 + ((x >> 2)  & 0x33333333);
  x = (x & 0x0f0f0f0f + ((x >> 4)  & 0x0f0f0f0f);
  x = (x & 0x00ff00ff + ((x >> 8)  & 0x00ff00ff);
  x = (x & 0x0000ffff + ((x >> 16) & 0x0000ffff);   
  return 0;
}

This algorithm is based on the following formula:

Let’s prove our equation in the case of a 4-bit register:

You can try extending this proof to the case of a 32-bit register, and you will get the same results.