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

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

5790 次浏览
小开

你可以重新措辞这个要求:

  • 设置 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的有效位存在)。

小开

中央处理器有专门的指令，非常快。在 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。

小开

这是一个循环比特的版本

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

前两个环找到了第一个紧致区域。最后一个循环检查该区域之外是否还有其他设置位。

小开

与0而不是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;
}

在 x86 _ 64上的 gcc10 -O3上，下面的指令比上面的少一条，用于符号扩展:

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测试。

小开

不能确定是否快，但是可以通过验证 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的逻辑 AND。关于这个问题的其他答案接受 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可移植地暴露弹出计数。C 仍然没有一种可移植的方法，可以可靠地编译成一个 popcnt 或类似的指令。

小开

实际上你不需要数前面的零。正如 pmg 在评论中建议的那样，利用你正在寻找的数字是序列 OEIS A023758的数字这一事实，即 形式2 ^ i-2 ^ j 的个数，i > = j，你可以只计算后面的零(即 J-1) ，在原始值中切换这些位(相当于加入 2 ^ j-1) ，然后检查这个值是否为 2 ^ i-1形式。利用海湾合作委员会/克朗的内在特性,

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，你可以用 std::countr_zero代替 __builtin_ctz得到一个可移植的函数:

#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 版本发出任何 popcount 指令，关于直通链接的基准受到了限制。试着用 -march=westmere在我的电脑上编译它们，我已经测量了10亿次从 std::mt19937获得相同序列的迭代的时间:

  • 你的版本是5.7秒
  • KamilCuk 的第二个版本: 4.7 s
  • 我的版本是4.7秒
  • Eric Postpischil 的第一个版本: 4.3 s
  • Yuri Feldman 的版本(显式使用 __builtin_popcount) : 4.1 s

所以，至少在我的架构中，最快的似乎是那个有爆米花的。

编辑2:

我已经更新了我的基准与新的埃里克邮差的版本。按照注释中的要求，我的测试代码可以找到 给你。我已经添加了一个无操作循环，以估计所需的时间由 PRNG。我还添加了 KevinZ 的两个版本。代码已经与 -O3 -msse4 -mbmi一起编译，以获得 popcnt和 blsi指令(感谢 Peter Cordes)。

结果: 至少在我的架构中，埃里克 · 波斯皮希尔的版本与尤里 · 费尔德曼的一样快，至少比目前提出的任何其他版本快两倍。

小开

您可以执行以下计算顺序(假设 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)之外，将所有的 y = val & -val去掉。
警告: 对于 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是否“紧凑”。

小开
最佳答案

解决方案:

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给出 ~x+10，所以低 ~x+11是相同的，但高 ~x+12被翻转到 ~x+13。)然后 ~x+14给出了两者中唯一的1位，也就是最低的1位(~x+15)。(如果 x为零，则 ~x+14为零。)

把这个数字加到 x中会导致所有连续的1进位，把它们改成0。它将在下一个更高的0位留下一个1(或者穿过高端，留下一个包装的总数为零)(10100000)

当与 x进行 AND 时，在将1改为0的地方(以及进位将0改为1的地方)有0。所以只有在高出1位的情况下，结果才不是零。

小开

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

先把前面的0翻过来。然后测试新值是否是梅森数。在这个算法中，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;
}
小开

我们可以利用 GCC 内置说明书检查:

设置位的计数

Int _ _ builtin _ popcount (无符号 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

但这可能更容易理解。


提交答案