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

  • Work with all your cloud files (Drive, Dropbox, and Slack and Gmail attachments) and documents (Google Docs, Sheets, and Notion) in one place. Try Dokkio (from the makers of PBworks) for free. Now available on the web, Mac, Windows, and as a Chrome extension!

View
 

CountBits

Page history last edited by Kenneth Finnegan 13 years, 1 month 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.