获取二进制数中末尾1的个数

Question

获取二进制数中末尾1的个数

c++algorithmoptimizationbit-manipulation

18

有没有高效的位运算方法可以得到一个整数末尾具有的设置位数？例如，11₁₀ = 1011₂ 将是两个尾随的1位。8₁₀ = 1000₂ 将是0个尾随的1位。

是否有比线性搜索更好的算法？我正在实现一个随机跳表，并使用随机数确定插入元素时的最大级别。我在 C++ 中处理32位整数。

编辑：汇编语言不行，请提供纯C++解决方案。

- IVlad

12个回答

8

Bit Twiddling Hacks页面提供了许多用于计算末尾零的算法。只需首先对您的数字取反，即可适应其中任何一种算法。还有可能有巧妙的方法可以在不这样做的情况下改变算法。在具有廉价浮点运算的现代CPU上，最好的算法可能是：

unsigned int v=~input;            // find the number of trailing ones in input
int r;                     // the result goes here
float f = (float)(v & -v); // cast the least significant bit in v to a float
r = (*(uint32_t *)&f >> 23) - 0x7f;
if(r==-127) r=32;

- Sparr

8

从Ignacio Vazquez-Abrams的答案中获取并完成计数而不是表格：

b = ~i & (i+1);   // 这给出了一个1，位于末尾的1的左边
b--;              // 这使我们只得到需要计数的末尾1
b = (b & 0x55555555) + ((b>>1) & 0x55555555);  // 1位数字的2位和
b = (b & 0x33333333) + ((b>>2) & 0x33333333);  // 2位数字的4位和
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);  // 4位数字的8位和
b = (b & 0x00ff00ff) + ((b>>8) & 0x00ff00ff);  // 8位数字的16位和
b = (b & 0x0000ffff) + ((b>>16) & 0x0000ffff); // 16位数字的和

最终，b将包含1的计数（掩码、添加和移位计算1）。除非我犯了错误。使用前请测试。

- phkahler

非常好，完全没有查找表。谢谢！ - IVlad

1

然而，这个方案比其他解决方案更好吗？除了使用更少的内存外，我认为256个整数查找表解决方案执行的操作更少。由于它们都非常快，很难进行测试，但在非常慢的计算机上，你认为哪个会更胜一筹？ - IVlad

3

更快的速度非常依赖于平台。我宁愿选择带有条件执行的ARM。对于初学者来说，几乎每个ARM操作都可以是有条件的。相比于拥有16个分支命令（==0，<0，>=0，<=，<，>，>=等），你只需要将指令字的4位专门用于给所有条件赋值即可。因此只有一个分支操作，你可以使用修饰符将其变成“如果小于或等于则跳转”分支，但是同样的修饰符也可以将加法运算符变成“如果小于或等于则加”，而不需要任何处理开销。 - Sparr

你也可以放弃一些掩码，因为你知道某些加法不会溢出。例如，最后两行只是将b中的字节相加，其中没有一个字节的值超过8。再次测试 ;-) - phkahler

@Sparr：有趣。我当然可以看出避免分支会加快速度。 - Steven Sudit

显示剩余2条评论

7

GCC有__builtin_ctz，其他编译器也有自己的内部函数。只需用#ifdef来保护它：

#ifdef __GNUC__
int trailingones( uint32_t in ) {
    return ~ in == 0? 32 : __builtin_ctz( ~ in );
}
#else
// portable implementation
#endif

在x86架构上，这个内建函数将编译为一条非常快速的指令。其他平台可能会稍微慢一些，但大多数都有某种位计数功能，可以胜过你使用纯C运算符所能实现的功能。

- Potatoswatter

2

实现Steven Sudit的想法...

uint32_t n; // input value
uint8_t o;  // number of trailing one bits in n

uint8_t trailing_ones[256] = {
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 8};

uint8_t t;
do {
  t=trailing_ones[n&255];
  o+=t;
} while(t==8 && (n>>=8))

1（最佳）到4（最差）（平均1.004）倍（1次查找+1次比较+3次算术运算）减去一次算术运算。

- Sparr

这是一个相当快的实现，适用于任何大小的int模板。我原本想到的那个可能会更慢，因为它基于byte*和计数，这样做可以增加灵活性但代价也更高。如果输入类型固定，循环可以展开以获得更快的速度。 - Steven Sudit

此外，在所有情况下，最后的右移操作是不必要的。因此，通过将while循环移到循环内部（通过将其更改为if/break），可以稍微加快速度。展开循环会带来更大的收益。我想知道是否可以通过模板而不是手动展开循环... - Steven Sudit

1

移动了位移，短路计算应该可以解决它，并且现在当答案是8的倍数时，我可以节省一次循环迭代。 - Sparr

2

可能有更好的答案，特别是如果汇编语言不是问题的话，但一个可行的解决方案是使用查找表。它将有256个条目，每个条目返回连续尾随1位的数量。将其应用于最低字节。如果是8，则应用到下一个并计数。

- Steven Sudit

别的事情！你会查找最后一个字节，如果答案小于8，那就完成了。如果不是，就重复查找倒数第二个字节并保持总和。对于32位数字，最多进行4次查找，并在每次查找后进行简单测试以确定是否继续。 - Steven Sudit

1

这里的最坏情况是需要进行4次查找，而不是32次位运算。 - Sparr

嗯，从技术上讲，您不需要保留总数。您的索引将告诉您已扫描多少字节。将其乘以8并添加停止字节的查找即可。 - Steven Sudit

其他答案有些有趣，可能会稍微快一些或使用较小的表格。我唯一担心的是，乍一看，我不知道它们是否正确。 - Steven Sudit

@Robert：我的意思是n代表字节数。在这种情况下，n=k，所以它是O(1)。如果我们在任意长的字节序列上执行此操作，则O(n)更合理。 - Steven Sudit

显示剩余4条评论

0

采用@phkahler的答案，您可以定义以下预处理器语句：

#define trailing_ones(x) __builtin_ctz(~x & (x + 1))

当你得到一个比之前所有数字都大的数字时，你可以简单地计算末尾的零。

- borchero

0

这段代码计算末尾零位的数量，取自这里（也有一个依赖于IEEE 32位浮点表示的版本，但我不会相信它，而模数/除法方法看起来非常流畅 - 也值得一试）：

int CountTrailingZeroBits(unsigned int v) // 32 bit
{
    unsigned int c = 32; // c will be the number of zero bits on the right

    static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
    static const unsigned int S[] = {1, 2, 4, 8, 16}; // Our Magic Binary Numbers

    for (int i = 4; i >= 0; --i) // unroll for more speed
    {
        if (v & B[i])
        {
            v <<= S[i];
            c -= S[i];
        }
    }

    if (v)
    {
        c--;
    }

    return c;
}

然后计算末尾的1：

int CountTrailingOneBits(unsigned int v)
{
    return CountTrailingZeroBits(~v);
}

- plinth

0

基于Ignacio Vazquez-Abrams的答案实现

uint8_t trailing_ones(uint32_t i) {
 return log2(~i & (i + 1));
}

log2() 的实现留给读者作为练习 (请参见这里)

- Sparr

0

http://graphics.stanford.edu/~seander/bithacks.html 可能会给你一些启发。

- Patrick

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ignacio Vazquez-Abrams · Accepted Answer

11

计算~i & (i + 1)，并将结果用作具有32个条目的表的查找。 1表示零个1，2表示一个1，4表示两个1，依此类推，但0表示32个1。

- Ignacio Vazquez-Abrams

1

这是另一种解决方案，我不能一眼确定其正确性。请问您能否提供链接或包含可工作的代码？ - Steven Sudit

这对我有意义。基本上，通过补充i，我们得到了在末尾设置为1的1位序列后面的0位。通过将1添加到i，我们得到相同的位设置为1。通过and操作两者，我们得到2的幂次方，因为其他所有位都是0，对吗？然而，即使我保留lookup[i] = ~i & (i + 1)，这如何帮助我获得我感兴趣的实际计数？对于一个数字n？使用查找表只能得到2的幂次方，我仍然需要一种方法来获取它的对数，不是吗？所以我不确定这是否比其他解决方案更好。 - IVlad

我猜我也会实现这个... :) - Sparr

请务必注意：）我不确定您如何使用大小为32的查找表并轻松获取计数。像OP实现中的二进制搜索会降低性能。 - IVlad

我认为他的意思是在查找表中使用哈希/关联数组而不是普通数组。在PHP中，可以这样实现：array(1->0,2->1,4->2,8->3,等等)。 - Sparr

显示剩余4条评论