How to Count number of bits in an integer.

0 votes
28 views
asked Dec 19, 2013 in C++ by ram

1 Answer

0 votes
answered Dec 19, 2013 by Anjani Kumar

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.

...