>我需要测试位值为 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
它们(当然)是具有非负m和n(1<<m)*(1<<n-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 进位，使其在~x和前 0 位中翻转低 1 位，但随后停止。因此，-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(以及进位将 0 更改为 1)。因此，只有当还有 1 位更高时，结果才不为零。
实际上不需要使用任何内联函数。
首先在第一个 1 之前翻转所有 0。然后测试新值是否为梅森数。在这个算法中，零映射到 true。
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;
}
实际上你不需要计算前导零。正如 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 版本没有发出弹出计数指令。尝试在我的 PC 上用-march=westmere编译它们，我已经测量了以下时间，进行了 10 亿次迭代，具有std::mt19937的相同序列：
- 您的版本： 5.7 秒
- 卡米尔库克的第二个版本：4.7 秒
- 我的版本： 4.7 秒
- Eric Postpischil的第一个版本：4.3秒
- 尤里·费尔德曼的版本(明确使用
__builtin_popcount)：4.1 秒
所以，至少在我的架构上，最快的似乎是带有popcount的那个。
编辑 2：
我已经用新的Eric Postpischil的版本更新了我的基准测试。根据评论中的要求，可以在此处找到我的测试代码。我添加了一个无操作循环来估计 PRNG 所需的时间。我还添加了KevinZ的两个版本。代码已经在 clang 上编译了-O3 -msse4 -mbmi以获得popcnt和blsi指令(感谢 Peter Cordes)。
结果：至少在我的架构上，Eric Postpischil的版本与Yuri Feldman的版本一样快，至少比迄今为止提出的任何其他版本快两倍。
不确定是否快，但可以通过验证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 个连续位组的输入)，逻辑 AND 且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()或 C++20 通过std::popcount方便地公开 popcount。 C 仍然没有一种可移植的方法，可以在可用的目标上可靠地编译为 popcnt 或类似指令。
CPU有专门的指令，非常快。在PC上它们是BSR/BSF(1985年在80386中引入)，在ARM上它们是CLZ/CTZ
使用一个来查找最低有效设置位的索引，将整数向右移动该量。使用另一个来查找最高有效设置位的索引，将您的整数与 (1u<<(bsr+1))-1 进行比较。
不幸的是，35 年不足以更新C++语言以匹配硬件。要使用C++中的这些指令，您需要内部函数，这些内部函数不可移植，并且返回的结果格式略有不同。使用预处理器、#ifdef等来检测编译器，然后使用适当的内部函数。在MSVC中，它们是_BitScanForward、_BitScanForward64、_BitScanReverse、_BitScanReverse64。在海湾合作委员会和叮当中，它们是__builtin_clz和__builtin_ctz.
与零而不是 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;
}
在神螺栓上测试。
您可以改写要求：
- 将 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时中止for循环0这意味着不存在值为 1 的更重要的位)。
您可以执行以下计算序列(假设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长度的"紧凑"位掩码。只需将其与val进行比较，看看val是否"紧凑"。
我们可以利用 gcc 内置指令来检查是否：
设置位数的计数
int __builtin_popcount (unsigned int x)
返回 x 中的 1 位位数。
等于 (a - b)：
a：最高设置位 (32 - CTZ) 的索引(32，因为无符号整数中有 32 位)。
int __builtin_clz(无符号 int x)
返回 x 中前导 0 位的数，从最高有效位位置开始。如果 x 为 0，则结果未定义。
b：最低设置位 (CLZ) 的索引：
int __builtin_clz(无符号 int x)
返回 x 中前导 0 位的数，从最高有效位位置开始。如果 x 为 0，则结果未定义。
例如，如果 n = 0b0001100110;我们将获得 popcount 的 4，但索引差 (a - b) 将返回 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
但它可能更容易理解。
好的，这是一个循环位的版本
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;
}
前两个环路找到了第一个紧凑区域。最后一个循环检查该区域之外是否有任何其他设置位。