可以确定 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-or运算，把这个值移动一位，然后统计结果中1的个数

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

另请注意，一个字节只能有 256 个配置，因此可以一次计算并放入非常小的 table 256 个字节。

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

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

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

Answer 2

对于制服的定义，数字必须采用 00011111 或 11110000 的形式。考虑前一个（零后跟一个）。

将值加一。如果它是统一的，它将恰好有一个 1 位，这意味着 2.

的幂

要测试一个值是否是 2 的幂，请使用 (x & (x - 1)) == 0。为了缩短代码，我们不需要在上一步中添加一个。相反，我们检查 (x & (x + 1)) == 0

通过 NOT-ing 初始值将其应用于另一种情况并重复上述过程。

#include <cstdio>
bool isuniform(unsigned char x) {
  unsigned char y = ~x;
  return (x & (x + 1)) == 0 || (y & (y + 1)) == 0;
}
int main() {
  printf("%d\n", isuniform(0));   // 00000000
  printf("%d\n", isuniform(1));   // 00000001
  printf("%d\n", isuniform(3));   // 00000011
  printf("%d\n", isuniform(7));   // 00000111
  printf("%d\n", isuniform(15));  // 00001111
  printf("%d\n", isuniform(31));  // 00011111
  printf("%d\n", isuniform(63));  // 00111111
  printf("%d\n", isuniform(127)); // 01111111
  printf("%d\n", isuniform(255)); // 11111111
  printf("%d\n", isuniform(254)); // 11111110
  printf("%d\n", isuniform(252)); // 11111100
  printf("%d\n", isuniform(248)); // 11111000
  printf("%d\n", isuniform(240)); // 11110000
  printf("%d\n", isuniform(224)); // 11100000
  printf("%d\n", isuniform(192)); // 11000000
  printf("%d\n", isuniform(128)); // 10000000
  //----------
  printf("%d\n", isuniform(2));
  printf("%d\n", isuniform(4));
  printf("%d\n", isuniform(50));
  printf("%d\n", isuniform(123));
  printf("%d\n", isuniform(129));
  printf("%d\n", isuniform(253));
  return 0;
}

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

Possible to determine number of bitwise transitions in an 8 bit integer?

integer

glsl

bit