Count bits in the number.

Question

Duplicate:

Best algorithm to count the number of set bits in a 32-bit integer?

---

Suppose you have a number. Is there any way to count the bits which equals to 1 in binary representation of that number, not using iteration? I mean, is there any way to do it in constant time using some bitwise operators and masks. I need solution which will work well for both architectures 32 bit and 64 bit. Ah almost forgot, I need it for C language or assembler is also good.

Answer 1

There is a bit counting algorithm without a loop at http://graphics.stanford.edu/~seander/bithacks.html. Lots of bit counting algorithms at http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Answer 2

Yes, you can do that by using a look up table.

Answer 3

Well, of course there is, but you're not going to like it.

You could, of course, build a lookup table with all the correct values in it:

table[1] = 1, table[2] = 1, table[3] = 2, etc.

So, this would give you a really fast answer, but it's a completely useless solution by itself, since the table would have to be very, very large.

You could optimize this a bit, but it requires just a little iteration. Simply create an 8-bit version of the table solution, a mere 256-entry table, then iterate over each BYTE in the value to be checked, summing the results of the table lookup. Something like:

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

Hmm, seems this is well known (and here I was doing this off the top of my head): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive