计算unsigned int中位转换次数的最快方法
我正在寻找计算unsigned int中位转换次数的最快方法。
如果int包含： 0b00000000000000000000000000001010
转换次数为：4
如果int包含： 0b00000000000000000000000000001001
转换次数为：3
语言是C.
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
最快取决于您的场景：当您将数据类型指定为常量（unsigned int）时，可以使用查找表。 但是当你需要这个操作时，只有一次初始化初始化表太大，而扫描+通过int进行计数的速度要快得多。
我想总体上最好的是一个组合：查找表中的字节或字（256或64k条目不是那么多），然后将字节/字组合在它们的最后/第一位。
在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; }
什么语言？
我会循环64次，然后将数字移位以检查位，然后存储前一位并将其与当前位进行比较。 如果不同，请递增计数。
这是使用算术移位+ 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; }
好吧，对于转换，你的意思是，如果你遍历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
你可以用shift替换mod和div。