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

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

Answer 2

最快取决于您的情况：当您将数据类型指定为常量大小（无符号整数）时，可以使用查找表。但是，当您仅在初始化表的恒定开销太大时才需要此操作时，尽管通过 int 进行扫描+计数要快得多。

我想总体上最好的组合是：查找表以查找一个字节或一个字（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;
}

Answer 4

这是使用算术移位 + 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;
}

Answer 5

什么语言？

我会循环 64 次，然后对您的数字进行位移以检查这些位，然后存储前一个位并将其与当前位进行比较。如果它不同，请增加您的计数。

Answer 6

好的，对于转换，您的意思是，如果您遍历 0-s 和 1-s 的字符串，您会计算 0 跟随 1 或 1 跟随 0 的每次出现。

这很容易通过移出位并计算变化：

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

您可以用班次替换 mod 和 div。