获得尾随1位的数量

Question

是否有任何有效的按位操作可以获得整数结束的设置位数？例如,11 ₁₀ = 1011 ₂将是两个尾随1位.8 ₁₀ = 1000 ₂将是0尾随1位.

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

编辑:汇编程序是不可能的,我对纯C++解决方案感兴趣.

Answer 1

计算~i & (i + 1)并将结果用作具有32个条目的表中的查找.1表示零1,2表示1表示,4表示2表示1,依此类推,除非0表示32 1表示.

Answer 2

该位操作黑客页面具有计数尾随零一些算法.其中任何一个都可以通过简单地反转您的数字进行调整,并且可能有巧妙的方法来改变算法,而不是这样做.在具有廉价浮点运算的现代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;

Answer 3

从Ignacio Vazquez-Abrams那里得到答案并用计数而不是表格来完成它:

b = ~i & (i+1);   // this gives a 1 to the left of the trailing 1's
b--;              // this gets us just the trailing 1's that need counting
b = (b & 0x55555555) + ((b>>1) & 0x55555555);  // 2 bit sums of 1 bit numbers
b = (b & 0x33333333) + ((b>>2) & 0x33333333);  // 4 bit sums of 2 bit numbers
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);  // 8 bit sums of 4 bit numbers
b = (b & 0x00ff00ff) + ((b>>8) & 0x00ff00ff);  // 16 bit sums of 8 bit numbers
b = (b & 0x0000ffff) + ((b>>16) & 0x0000ffff); // sum of 16 bit numbers

在结尾b将包含1的计数(掩码,添加和移位计数1).除非我当然是傻瓜.使用前测试.

Answer 4

GCC__builtin_ctz和其他编译器都有自己的内在函数。只需用一个保护它#ifdef：

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

在 x86 上，此内置指令将编译为一条非常快的指令。其他平台可能稍微慢一些，但大多数平台都有某种位计数功能，可以胜过您使用纯 C 运算符所做的事情。