c++ - 是否有一种优雅而快速的方法来测试整数中的 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。

标签： c++cbit-manipulation

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。）

当它与 进行与运算时x，在将 1 更改为 0 的位置（以及进位将 0 更改为 1 的位置）有 0。因此，仅当再高出 1 位时，结果才不是零。