可以确定8位整数中的按位转换次数吗？

Question

我似乎无法在此找到任何有点魔力,所以我希望这里的某人可能能够揭示这是否可能.

我试图在8位整数中找到按位转换的数量(整数实际上是32位整数,但我只使用前8位)来确定8位是否均匀(2个或更少的转换) ).

例如:

00100000 - two transitions - uniform
00100001 - three transitions - not uniform
10101010 - seven transitions - not uniform
00000000 - no transitions - uniform

是否有更快的方法来找到除了循环每个位之外的转换次数(循环通过每个位是目前唯一可以提出的解决方案)？

Answer 1

您可以将x或值的值移位一位,然后计算1结果中的数字.

unsigned v = (x ^ (x>>1)) & 0x7F;
unsigned count = 0;
while (v) {
    count++;
    v &= (v - 1);
}

另请注意,一个字节只能有256个配置,因此计算可以完成一次并放入一个256字节的非常小的表中.

如果您只想知道是否有2个或更少的更改,则可以展开循环:

unsigned v = (x ^ (x >> 1)) & 0x7F;
v &= v - 1;
v &= v - 1;
uniform = (v == 0);

请注意,此计算与数字的大小无关,您可以直接使用32位无符号数(唯一改变的是成为的掩码0x7FFFFFFF)