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

What language?

I would loop 64 times and then bit shift your number to inspect of the bits, then store the previous bit and compare it to the current one. If it's different, incremember your count.

Answer 2

Ok, with transitions you mean if you walk through the string of 0-s and 1-s, you count each occurance that a 0 follows a 1 or a 1 follows a 0.

This is easy by shifting bits out and counting the changes:

transitions(n)
  result = 0
  prev = n mod 2
  n = n div 2
  while n<>0 
    if n mod 2 <> prev then
      result++
      prev = n mod 2
    fi
    n = n div 2
  elihw
  return result

you can replace the mod and div with shifts.

Answer 3

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.

Answer 4

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 5

In C/C++ I would do the following:

unsigned int Transitions(unsigned int value)
{
    unsigned int result = 0;

    for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
    {
        if (markers & 0x01) result++;
    }

    return result;
}

Answer 6

Here's the code using arithmetic shift + xor and Kernighan's method for bit counting:

int count_transitions(int x)
{
    assert((-1 >> 1) < 0); // check for arithmetic shift
    int count = 0;
    for(x ^= (x >> 1); x; x &= x - 1)
     ++count;
    return count;
}