I'm Brett Slatkin and this is where I write about programming and related topics. You can contact me here or view my projects.

29 December 2013

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.
© 2009-2019 Brett Slatkin