Another of my favorite tricks - reducing the number of bits in a number by 1

One of the classic (and thus no longer asked) Microsoft interview questions is "How quickly can you count the bits in a 16 (or 32) bit integer?".

You get a varied number of responses to this one, from brute force to lookup tables.

One of my favorite tricks for this is:

   x = x & (x - 1)

This reduces the number of bits in a number by one.  I'm not sure exactly why it works, and it only works for 2s complement numbers, but it DOES work.

So using this trick, the bitcount question is:

{
   bitcount = 0;
   while (value != 0)
   {
     bitcount += 1;
     value = value & (value - 1);
   }
   return bitcount;
}

It's a silly trick, but clever.

Btw, being geeks, a number of people over here came up with the fastest known version (in software).  It involves adding the bits in parallel - you can count the bits in 32bit integer in a constant 34 cycles on a 386 machine.

To do that, you first split the number into odd and even bits thus creating 32 1 bit numbers.

Next, you shift the even bits right one bit and add the values together to get a collection of 16 2 bit numbers.

Now split the number into groups of 2 bits by again masking by 0b0011001100110011 and 0b1100110011001100, shift the second value right by two bits and add the values to get a collection of 8 4 bit numbers.

Now split the number into groups of 4 bits by again masking by 0b0000111100001111 and 0b1111000011110000, shift the second value right by four bits and add the values to get a collection of 4 8 bit numbers.

Now split the number into groups of 8 bits by again masking by 0b0000000011111111 and 0b1111111100000000, shift the second value right by eight bits and add the values to get a collection of 2 16 bit numbers.

Finally, split the number into groups of 16 bits by taking the low sixteen bits and adding them to the high 16 bits, you now have one 32 bit integer that contains the number of bits that were on in the original value.