Count number of bits in an integer.

This tip submitted by Anjani Kumar Mishra on 2012-04-04 07:14:45. It has been viewed 31052 times.
Rating of 5.2 with 150 votes

Here's a fast way to count the number of bits in an integer. It uses a 4 bit wide lookup table and interates through each nibble to add the number of bits set in it to the total number of bits set.

This code is a tradeoff between the two extreams: count each bit individually, or have a 232 large lookup table.

Code:

int bitcount(unsigned int num) {
     int count = 0;
     static int nibblebits[] =
          {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
     for(; num != 0; num >>= 4)
          count += nibblebits[num & 0x0f];
     return count;
}

A possibly faster, yet less portable function is one built into GCC:

int __builtin_popcount (unsigned int x);

This function tries to use CPU specific instructions, which will always be orders of magnitude faster than any algorithm you manage to come up with.

More tips

Help your fellow programmers! Add a tip!