Bit Twiddling

Larry Osterman's WebLog: "[Y]ou can count the [number of] bits in [a] 32bit integer in a constant 34 cycles on a 386 machine."

Neat algorithm. Wish I knew x86 assembly.

Update 1: Larry's algorithm in C, courtesy of John Lyon-Smith's blog:

int bitcount(unsigned long n) {

  n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
  return n % 0xFF;
}

Update 2: The above function takes 16 cycles on my iBook G4. Why use a 386 chip for a benchmark in the 21st century? Why not an Athlon or a Pentium IV?