计算unsigned int中位转换次数的最快方法

Question

我正在寻找计算一个位转换次数的最快方法unsigned int.

如果int包含: 0b00000000000000000000000000001010

转换次数为:4

如果int包含: 0b00000000000000000000000000001001

转换次数为:3

语言是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
}

有关CountBits的有效实现,请参阅http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel