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

  • Buried in cloud files? We can help with Spring cleaning!

    Whether you use Dropbox, Drive, G-Suite, OneDrive, Gmail, Slack, Notion, or all of the above, Dokkio will organize your files for you. Try Dokkio (from the makers of PBworks) for free today.

  • Dokkio (from the makers of PBworks) was #2 on Product Hunt! Check out what people are saying by clicking here.

View
 

CountBits

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