• 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.



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.



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.





Comments (0)

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