One Big Fluke

Cool list of bit twiddling hacks. The one I needed was counting the number of 1 bits in an integer.

His solution for 32-bit integers:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Compare that to the algorithm from K&R C:

long count_bits(long n) {     
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set
  return c;
}

K&R's solution makes sense to me. The other one is insane. Will try both in Go and see which wins.