在任何位位置查找数字的二进制表示

Question

在过去的一周里，我一直在为这个问题苦苦挣扎，看来我最终无法解决。给定一个任意的 64 位 unsigned int 数，如果它在任意位位置、任意位设置包含 31 (0b11111) 的二进制模式，则该数有效，否则无效。

例如：

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 1110 有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0111 1100 有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1000 0000 0000 0000 0000 0000 有效

0000 0000 0011 1110 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 1110 有效等...

还有：

0000 0000 0000 1100 0000 0100 0000 0000 1100 1100 0000 0000 0100 0000 0001 1111 有效

1110 0000 0000 0100 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0011 1110 有效

0000 0000 1000 0010 0000 0010 0000 0000 0000 0000 0010 0000 0000 0000 0111 1100 有效

0000 0010 0000 0110 0000 0000 0000 0000 0000 1111 1000 0000 0000 0100 0110 0000 有效

0000 0000 0011 1110 0000 0000 0011 0000 0000 1000 0000 0000 0000 0000 0011 1110 有效等...

但是：

0000 0000 0000 1100 0000 0100 0000 0000 1100 1100 0000 0000 0100 0000 0000 1111 无效

1110 0000 0000 0100 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0011 1100 无效

0000 0000 1000 0010 0000 0010 0000 0000 0000 0000 0010 0000 0000 0000 0101 1100 无效

0000 0010 0000 0110 0000 0000 0000 0000 0000 1111 0000 0000 0000 0100 0110 0000 无效

0000 0000 0011 1010 0000 0000 0011 0000 0000 1000 0000 0000 0000 0000 0001 1110 无效等...

你说对了...

但这只是问题的前半部分。第二个是，它需要在没有循环或分支（已经完成）的情况下实现以提高速度，仅使用一次算术检查 and/or 逻辑，位操作类型的代码。

我能得到的最接近的是 Bit Twiddling Hacks“确定一个字是否有零字节”(https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord) 的修改版本，以检查零的五个位块（取反 11111）。但它仍然具有仅检查固定位块（位 0 到 4、位 5 到 9 等）的能力的限制，而不是在任何位位置（如上例所示）。

任何帮助将不胜感激，因为我已经筋疲力尽了。

Sz

Answer 1

实施

让我用稍微不同的方式重申您的目标：

I want to check whether an integer contains 5 consecutive high bits.

根据这个公式，以下解决方案自行解释。它是用 C++ 编写的。

bool contains11111(uint64_t i) {
   return i & (i << 1) & (i << 2) & (i << 3) & (i << 4);
}

这种方法也适用于任何其他模式。例如，如果您想检查 010，您可以使用 ~i & (i<<1) & ~(i<<2)。在您的示例中，模式的长度是质数，但对于合数，尤其是 2 的幂，您可以进一步优化它。例如，在搜索 1111 1111 时，您可以使用 i&=i<<1; i&=i<<2; i&=i<<4; return i.

测试

为了在您的示例中对此进行测试，我使用了以下程序。 testcases[] 中的文字是由运行您的示例通过 bash 命令生成的...

{ echo 'ibase=2'; tr -dc '01\n' < fileWithYourExamples; } |
bc | sed 's/.*/UINT64_C(&),/'

#include <cinttypes>
#include <cstdio>

bool contains11111(uint64_t i) {
  return i & (i << 1) & (i << 2) & (i << 3) & (i << 4);
}

int main() {
  uint64_t testcases[] = {
      // valid
      UINT64_C(31),
      UINT64_C(62),
      UINT64_C(124),
      UINT64_C(260046848),
      UINT64_C(17451448556060734),
      UINT64_C(3382101189607455),
      UINT64_C(16142027170561130558),
      UINT64_C(36593945997738108),
      UINT64_C(145804038196167776),
      UINT64_C(17451654848708670),
      // invalid
      UINT64_C(3382101189607439),
      UINT64_C(16142027170561130556),
      UINT64_C(36593945997738076),
      UINT64_C(145804038187779168),
      UINT64_C(16325754941866014),
  };
  for (uint64_t i : testcases) {
    std::printf("%d <- %016" PRIx64 "\n", contains11111(i), i);
  }
}

这会打印

1 <- 000000000000001f
1 <- 000000000000003e
1 <- 000000000000007c
1 <- 000000000f800000
1 <- 003e00000000003e
1 <- 000c0400cc00401f
1 <- e00400300000003e
1 <- 008202000020007c
1 <- 020600000f800460
1 <- 003e00300800003e
0 <- 000c0400cc00400f
0 <- e00400300000003c
0 <- 008202000020005c
0 <- 020600000f000460
0 <- 003a00300800001e

在任何位位置查找数字的二进制表示

Finding binary representation of a number at any bit position

binary

optimization

bit-manipulation

实施

测试