I'm Brett Slatkin and this is where I write about programming and related topics. Check out my favorite posts if you're new to this site. You can also 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-2016 Brett Slatkin