我需要测试位值为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和n。
static _Bool IsCompact(unsigned x)
{
return (x & x + (x & -x)) == 0;
}
简要地说:
X(&C -x给出x中设置的最低位（如果x为零，则为零）。
x+(x&-x)将最低的连续1字符串转换为单个1（或换行为零）。
X(&C x+(x&-x)清除这1位。
(x&x+(x&-x))==0测试是否剩余任何其他1位。
更长:
-x等于~x+1。 在~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进行and时，在将1更改为0的地方（以及进位将0更改为1的地方）会出现0。 因此，只有在向上再高出1位的情况下，结果才不是零。
实际上不需要使用任何intrinsic。
首先，在第一个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;
}
实际上你不需要计算前导零。 正如pmg在注释中所建议的，利用您要查找的数字是序列OEIS A023758中的数字，即i>=j的格式为2^i-2^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::countra_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;
}
cast很难看，但它在警告您，在操作位时最好使用无符号类型。 C++20之前的备选方案是Boost::MultiPrecision::LSB。
编辑:
删除线链接上的基准受到Yuri Feldman版本没有发出popcount指令这一事实的限制。 尝试在我的PC上用-march=westmere编译它们，我用std::MT19937的相同序列测量了10亿次迭代的以下时间:
__builtin_popcount):4.1s所以，至少在我的架构上，最快的似乎是有popcount的那个。
编辑2:
我已经用新的Eric Proposchil版本更新了我的基准测试。 正如注释中所要求的，我的测试的代码可以在这里找到。 我添加了一个无操作循环来估计PRNG所需的时间。 我还添加了Kevinz的两个版本。 代码已经用-o3-msse4-mbmi在clang上编译，以获得popcnt和blsi指令（感谢Peter Cordes）。
结果:至少在我的架构上，Eric Proposchil的版本和Yuri Feldman的版本一样快，而且比目前提出的任何其他版本都快至少两倍。
