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.

Hearse

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

Pop

using shift + xor was my first idea as well. – Renewal

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.

Peony

a 256-byte lookup table is pretty reasonable but a 64k one is sure to blow the L1 cache. – Pop

Answer 3

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;
}

Filippo

I think there is an error in your implementation: If I give it: 0x8000000b = 0b10000000000000000000000000001011 Which has 4 states your function counts 5! – Hearse

It is simply because the iteration is not limited to 32-bits (to reduce the number of operations), you could add an extra check I suppose but that would add operations which would slow it down a little. This implementation is basically a compact version of Crashworks solution. – Filippo

Answer 4

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;
}

Logue

Answer 5

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.

Overbold

Answer 6

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.

Bostick