计算无符号整数中位转换次数的最快方法

Question

我正在寻找计算unsigned int中位跃迁数量的最快方法。

如果整型包含：0b00000000000000000000000000001010

转换次数为:4

如果整型包含：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

Answer 2

最快取决于您的场景:由于您将数据类型指定为固定大小(无符号整数)，因此可以使用查找表。但是，如果只需要执行一次此操作，初始化该表的持续开销太大，而且通过int执行scanning+counting的速度要快得多。

我认为总体上最好的组合是:在表中查找字节或字(256或64k条目不是很多)，然后根据字节/字的最后/第一位组合字节/字。

Answer 3

在C/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;
}