| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Whenever you search in PBworks or on the Web, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, Slack, and browsed web pages. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.

View
 

CountBits

Page history last edited by Kenneth Finnegan 14 years, 6 months ago

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 2<pow>32</pow> 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;
}

Extensions:

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.

 


Sources:

http://c-faq.com/misc/bitcount.html

http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

Comments (0)

You don't have permission to comment on this page.