Fastest way to count number of bit transitions in an unsigned int

Question

I'm looking for the fastest way of counting the number of bit transitions in an unsigned int.

If the int contains: 0b00000000000000000000000000001010

The number of transitions are: 4

If the int contains: 0b00000000000000000000000000001001

The number of transitions are: 3

Language is C.

Answer 1

int numTransitions(int a)
{
  int b = a >> 1; // sign-extending shift properly counts bits at the ends
  int c = a ^ b;  // xor marks bits that are not the same as their neighbors on the left
  return CountBits(c); // count number of set bits in c
}

For an efficient implementation of CountBits see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Fastest depends on your scenario: As you specified your datatype as constant sized (unsigned int), it is possible with lookup table. But when you need this operation only once the constant overhead to init the table is too big, and scanning+counting through the int is far faster despite.

I guess the overall best would be a combination: Look up table for a byte or word (256 or 64k entries is not so much), and then combine the bytes/words by their last/first bit.