是否有一种优雅且快速的方法来测试整数中的 1 位是否在连续区域中？

Question

我需要测试位值为 1 的位置（对于 32 位整数从 0 到 31）是否形成连续区域。例如：

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

我希望这个测试，即一些功能has_contiguous_one_bits(int)，是可移植的。

一个明显的方法是遍历位置以找到第一个设置位，然后是第一个未设置位并检查是否有更多设置位。

我想知道是否存在更快的方法？如果有找到最高和最低设置位的快速方法（但从这个问题看来没有任何可移植的），那么可能的实现是

bool has_contiguous_one_bits(int val)
{
    auto h = highest_set_bit(val);
    auto l = lowest_set_bit(val);
    return val == (((1 << (h-l+1))-1)<<l);
}

只是为了好玩，这里是前 100 个具有连续位的整数：

0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 255 256 384 448 480 496 504 508 510 511 512 768 896 960 992 1008 1016 1020 1022 1023 1024 1536 1792 1920 1984 2016 2032 2040 2044 2046 2047 2048 3072 3584 3840 3968 4032 4064 4080 4088 4092 4094 4095 4096 6144 7168 7680 7936 8064 8128 8160 8176 8184 8188 8190 8191 8192 12288 14336 15360 15872 16128 16256 16320

它们（当然）是(1<<m)*(1<<n-1)带有非负m和的形式n。

Answer 1

解决方案：

static _Bool IsCompact(unsigned x)
{
    return (x & x + (x & -x)) == 0;
}

简要地：

x & -x给出设置的最低位x（如果为零，x则为零）。

x + (x & -x) 将连续 1 的最低字符串转换为更高的单个 1（或换行为零）。

x & x + (x & -x) 清除那些 1 位。

(x & x + (x & -x)) == 0 测试是否还有其他 1 位。

更长：

-x等于~x+1（对于int问题中的 ，我们假设二进制补码，但unsigned更可取）。在位被翻转后~x，加 1 进位，以便它翻转回低 1 位~x和第一个 0 位，然后停止。因此，-x直到并包括其第一个 1 的低位与 的低位相同x，但所有高位都被翻转。（例如：~10011100给出01100011，加 1 给出01100100，所以低100是相同的，但高10011被翻转到01100。）然后x & -x给我们两个中唯一为 1 的位，即最低的 1 位 ( 00000100)。（如果x为零，x & -x则为零。）

添加它会x导致所有连续的 1 进位，将它们更改为 0。它将在下一个较高的 0 位留下 1（或通过高端，留下包装的总数为零）（10100000。）

当它与 进行 AND 运算时x，在 1 变为 0 的地方（以及进位从 0 变为 1 的地方）有 0。因此，只有再高 1 位时，结果才不为零。

Answer 2

实际上没有必要使用任何内在函数。

首先在第一个 1 之前翻转所有 0。然后测试新值是否是梅森数。在这个算法中，零被映射为真。

bool has_compact_bits( unsigned const x )
{
    // fill up the low order zeroes
    unsigned const y = x | ( x - 1 );
    // test if the 1's is one solid block
    return not ( y & ( y + 1 ) );
}

当然，如果你想使用内在函数，这里是 popcount 方法：

bool has_compact_bits( unsigned const x )
{
    size_t const num_bits = CHAR_BIT * sizeof(unsigned);
    size_t const sum = __builtin_ctz(x) + __builtin_popcount(x) + __builtin_clz(z);
    return sum == num_bits;
}

Answer 3

实际上，您不需要计算前导零。正如 pmg 在评论中所建议的那样，利用您正在寻找的数字是序列OEIS A023758 的数字这一事实，即2^i - 2^j 形式的数字与 i >= j，您可以只计算尾随零（即j - 1），切换原始值中的那些位（相当于添加2^j - 1），然后检查该值是否为2^i - 1形式。使用 GCC/clang 内在函数，

bool has_compact_bits(int val) {
    if (val == 0) return true; // __builtin_ctz undefined if argument is zero
    int j = __builtin_ctz(val) + 1;
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

这个版本比你的和 KamilCuk 提出的和 Yuri Feldman 提出的只有 popcount 的版本要快一些。

如果您使用的是 C++20，您可以通过替换__builtin_ctz为std::countr_zero：

#include <bit>

bool has_compact_bits(int val) {
    int j = std::countr_zero(static_cast<unsigned>(val)) + 1; // ugly cast
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

强制转换很丑陋，但它警告您在操作位时最好使用无符号类型。C++20 之前的替代方案是boost::multiprecision::lsb.

编辑：

删除线链接的基准测试受到以下事实的限制：Yuri Feldman 版本没有发出 popcount 指令。尝试在我的 PC 上使用 编译它们-march=westmere，我测量了以下 10 亿次迭代的时间，其中具有相同的序列std::mt19937：

• 您的版本：5.7 秒
• KamilCuk 的第二个版本：4.7 秒
• 我的版本：4.7 秒
• Eric Postpischil 的第一个版本：4.3 秒
• Yuri Feldman 的版本（显式使用__builtin_popcount）：4.1 s

所以，至少在我的架构上，最快的似乎是带有 popcount 的架构。

编辑2：

我已经使用新的 Eric Postpischil 版本更新了我的基准测试。根据评论中的要求，我的测试代码可以在这里找到。我添加了一个无操作循环来估计 PRNG 所需的时间。我还添加了 KevinZ 的两个版本。代码编译铛上用-O3 -msse4 -mbmi得到popcnt和blsi指令（感谢彼得·科德斯）。

结果：至少在我的架构上，Eric Postpischil 的版本与 Yuri Feldman 的版本完全一样快，并且至少比迄今为止提出的任何其他版本快两倍。

Answer 4

不确定是否快，但可以通过验证val^(val>>1)最多有 2 位来做一个单行。

这仅适用于无符号类型：需要0在顶部移动 a （逻辑移位），而不是在符号位的副本中移位的算术右移。

#include <bitset>
bool has_compact_bits(unsigned val)
{
    return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2;
}

要拒绝0（即只接受恰好具有 1 个连续位组的输入），逻辑与val非零。关于这个问题的其他答案被0认为是紧凑的。

bool has_compact_bits(unsigned val)
{
    return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2 and val;
}

C++ 通过 可移植地公开 popcount std::bitset::count()，或在 C++20 中通过std::popcount. C 仍然没有一种可移植的方式来可靠地编译为 popcnt 或可用目标上的类似指令。

Answer 5

CPU 有专门的指令，速度非常快。在 PC 上它们是 BSR/BSF（1985 年在 80386 中引入），在 ARM 上它们是 CLZ/CTZ

使用 1 找到最低有效设置位的索引，将整数右移该数量。使用另一个找到最高有效设置位的索引，将您的整数与 (1u<<(bsr+1))-1 进行比较。

不幸的是，35 年不足以更新 C++ 语言以匹配硬件。要使用 C++ 中的这些指令，您将需要内部函数，它们不可移植，并以稍微不同的格式返回结果。使用预处理器#ifdef等来检测编译器，然后使用适当的内在函数。在 MSVC 中，它们是_BitScanForward、_BitScanForward64、_BitScanReverse、_BitScanReverse64。在 GCC 和 clang 中，它们是__builtin_clz和__builtin_ctz。

Answer 6

用 0 而不是 1 进行比较将节省一些操作：

bool has_compact_bits2(int val) {
    if (val == 0) return true;
    int h = __builtin_clz(val);
    // Clear bits to the left
    val = (unsigned)val << h;
    int l = __builtin_ctz(val);
    // Invert
    // >>l - Clear bits to the right
    return (~(unsigned)val)>>l == 0;
}

下面的结果比上面的少一个指令 gcc10 -O3x86_64，并在符号扩展上使用：

bool has_compact_bits3(int val) {
    if (val == 0) return true;
    int h = __builtin_clz(val);
    val <<= h;
    int l = __builtin_ctz(val);
    return ~(val>>l) == 0;
}

在Godbolt 上测试。

Answer 7

您可以重新表述要求：

• 设置 N 与前一个不同的位数（通过遍历位）
• 如果 N=2 并且第一位或最后一位为 0，则答案为是
• 如果 N=1 那么答案是肯定的（因为所有的 1 都在一侧）
• 如果 N=0 那么任何位为 0 那么你就没有 1，取决于你是否认为答案是是或否
• 其他任何事情：答案是否定的

遍历所有位可能如下所示：

unsigned int count_bit_changes (uint32_t value) {
  unsigned int bit;
  unsigned int changes = 0;
  uint32_t last_bit = value & 1;
  for (bit = 1; bit < 32; bit++) {
    value = value >> 1;
    if (value & 1 != last_bit  {
      changes++;
      last_bit = value & 1;
    }
  }
  return changes;
}

但这肯定可以优化（例如，通过for在value达到循环时中止循环，0这意味着不再存在值为 1 的有效位）。