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

Question

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

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

我想要这个测试，即某些功能 has_contiguous_one_bits(int)，可以移植。

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

请问有没有更快的方法？如果有找到最高和最低设置位的快速方法（但从 this question 看来没有任何可移植的），那么可能的实现是

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

它们（当然）具有非负 m 和 n.

的形式 (1<<m)*(1<<n-1)

Answer 1

您可以重新表述要求：

设置 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;
}

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

Answer 2

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

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

进行比较

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

Answer 3

好的，这是一个循环位的版本

template<typename Integer>
inline constexpr bool has_compact_bits(Integer val) noexcept
{
    Integer test = 1;
    while(!(test & val) && test) test<<=1; // skip unset bits to find first set bit
    while( (test & val) && test) test<<=1; // skip set bits to find next unset bit
    while(!(test & val) && test) test<<=1; // skip unset bits to find an offending set bit
    return !test;
}

前两个循环找到了第一个紧凑区域。最后一个循环检查是否有超出该区域的任何其他设置位。

Answer 4

比较零而不是比较将节省一些操作：

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 -O3 和 x86_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 5

不确定快不快，但可以通过验证 val^(val>>1) 最多打开 2 位来做一行。

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

#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++ 通过 std::bitset::count() 或 in C++20 via std::popcount 可移植地公开 popcount。 C 仍然没有一种可移植的方法可以在可用的目标上可靠地编译为 popcnt 或类似指令。

Answer 6

实际上您不需要计算前导零。正如 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;
}

~~这个版本 is slightly faster 然后是你的版本，还有 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.

编辑：

删除线基准测试 link 受到 Yuri Feldman 版本没有发出 popcount 指令这一事实的限制。尝试使用 -march=westmere 在我的 PC 上编译它们，我用来自 std::mt19937:

的相同序列测量了以下 10 亿次迭代的时间

你的版本：5.7秒
KamilCuk 的第二个版本：4.7 秒
我的版本：4.7秒
Eric Postpischil 的第一个版本：4.3 秒
Yuri Feldman 的版本（明确使用 __builtin_popcount）：4.1 秒

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

编辑 2：

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

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

Answer 7

您可以执行以下计算序列（假设 val 作为输入）：

uint32_t x = val;
x |= x >>  1;
x |= x >>  2;
x |= x >>  4;
x |= x >>  8;
x |= x >> 16;

获取一个数字，其中最重要的部分以下的所有零都用 1 填充 1。

您还可以计算y = val & -val以去除除val中最低有效1位以外的所有位（例如，7 & -7 == 1和12 & -12 == 4）。
警告：这将在 val == INT_MIN 内失败，因此您必须单独处理这种情况，但这是即时的。

然后将 y 右移一个位置，使 val 的实际 LSB 稍低一点，并执行与 x 相同的例程：

uint32_t y = (val & -val) >> 1;
y |= y >>  1;
y |= y >>  2;
y |= y >>  4;
y |= y >>  8;
y |= y >> 16;

然后 x - y 或 x & ~y 或 x ^ y 生成跨越 val 整个长度的 'compact' 位掩码。只需将它与 val 进行比较，看看 val 是否为 'compact'.

Answer 8

解决方案：

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 进位，以便它翻转回 ~x 中的低 1 位和第一个 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。）

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

Answer 9

实际上不需要使用任何内部函数。

首先翻转第一个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 ) );
}

当然，如果你想使用intrinsics，这里是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 10

我们可以使用 gcc builtin instructions 来检查是否：

设置位数

int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.

等于(a - b):

a：最高设置位的索引（32 - CTZ）（32 因为无符号整数中有 32 位）。

int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

b：最低设置位（CLZ）的索引：

int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

例如，如果 n = 0b0001100110；我们将使用 popcount 获得 4，但索引差异 (a - b) 将 return 6.

bool has_contiguous_one_bits(unsigned n) {
    return (32 - __builtin_clz(n) - __builtin_ctz(n)) == __builtin_popcount(n);
}

也可以写成：

bool has_contiguous_one_bits(unsigned n) {
    return (__builtin_popcount(n) + __builtin_clz(n) + __builtin_ctz(n)) == 32;
}

我不认为它比当前投票最多的答案更优雅或更高效：

return (x & x + (x & -x)) == 0;

使用以下程序集：

mov     eax, edi
neg     eax
and     eax, edi
add     eax, edi
test    eax, edi
sete    al

不过可能更容易理解。

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

Is there an elegant and fast way to test for the 1-bits in an integer to be in a contiguous region?

c

c++

bit-manipulation

解决方案：

简述：

更长：