时间戳

首页 > 解决方案 > 在任何位位置查找数字的二进制表示

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

问题描述

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

例如：

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 000 1 1111有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00 11 111 0 有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0 111 11 00 有效

0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1 000 0000 0000 0000 0000 0000 有效

0000 0000 00 11 111 0 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00 11 111 0 有效等...

还：

0000 0000 0000 1100 0000 0100 0000 0000 1100 1100 0000 0000 0100 0000 000 1 1111有效

1110 0000 0000 0100 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 00 11 111 0 有效

0000 0000 1000 0010 0000 0010 0000 0000 0000 0000 0010 0000 0000 0000 0 111 11 00 有效

0000 0010 0000 0110 0000 0000 0000 0000 0000 1111 1 000 0000 0000 0100 0110 0000 有效

0000 0000 00 11 111 0 0000 0000 0011 0000 0000 1000 0000 0000 0000 0000 00 11 111 0 有效等...

但：

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

你有道理...

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

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

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

大小

标签： optimizationbinarybit-manipulation

解决方案

执行

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

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

从这个公式中，以下解决方案可以解释自己。它是用 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

推荐阅读