Geek Answers Handbook

The fastest way to count the number of bit transitions in unsigned int

I am looking for the fastest way to count the number of bit transitions in unsigned int.

If int contains: 0b00000000000000000000000000001010

Number of transitions: 4

If int contains: 0b00000000000000000000000000001001

Number of transitions: 3

Language is C.

+5
source share
6 answers
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

+15
source

: ( int), . , , + int , .

, : Look up table for byte word (256 64k ), / / .

+2

C/++ :

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

?

64 , , , . , .

+1

+ xor Kernighan :

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

Well, with the transitions that you have in mind, if you go through the lines 0-s and 1-s, you count every second when a 0 follows 1 or 1, follows 0.

This is easy by shifting bits and counting 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 mod and div with shifts.

0
source

More articles:


All Articles