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

我需要测试位值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

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

最佳答案

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

简要地:x & -x给出x中设置的最低位(如果x为零，则为零)。x + (x & -x)将连续的1的最低字符串转换为单个1(或换为0)。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位(00000100)。 (如果x为零，则x & -x为零。)
将其添加到x会导致进位所有连续的1，并将其更改为0。它将在下一个较高的0位留下1(或通过高端传送，将换行的总数保留为零)(10100000)。
与x进行AND运算时，将1更改为0的位置(以及进位将0更改为1的位置)为0。因此，仅当再高1位时结果也不为零。

关于c++ - 有没有一种优雅而快速的方法来测试整数中的1位是否在连续区域中？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/62710316/