在任意位位置查找数字的二进制表示形式

Question

在过去的一周里，我一直在努力解决这个问题，似乎我最终无法解决它。给定任意64位无符号整数，如果它在任何位位置、任何位设置下包含31（0b11111）的二进制模式，则该数字有效，否则无效。

例如：

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 1111 1000 0000 0000有效

0000 0000 0011110 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 0011 1110有效

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

0000 0010 0000 0110 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 0100 0000 0011 0000 0000 0011 1100无效

0000 0000 1000 0010 0000 0010 0000 0000 0000 0010 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无效等...

你说到了重点...

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

我能得到的最接近的是一个修改版本的比特扭曲黑客“确定一个词是否有一个零字节”（https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord）来检查五个零比特块（否定了11111）。但是它仍然有能力只检查固定的比特块（比特0到4，比特5到9，等等...）而不是在任何比特位置（如上面的例子）。

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

Sz

Answer 1

让我用稍微不同的表述重申一下你的目标：

我想检查一个整数是否包含5个连续的高比特。

根据这个公式，下面的解决方案可以解释它自己。它是用C写的。

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

这种方法也适用于任何其他模式。例如，如果你想检查010，你可以使用~i

为了在您的示例中测试这一点，我使用了以下程序。testcase[]中的文字是通过通过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