在二进制数中找到第一个置位

Question

我需要从右到左查找二进制数中的第一个置位；我想出了这个解决方案：

int cnt=0;
while (number& 1 ==0)
{
    cnt++;
    number>>=1;
}

有更好的方法吗？一些聪明的位操纵技术？

Answer 1

处理器可能有指令直接找到：

视窗/MSVC：

• _BitScanForward()
• _BitScanReverse()

海湾合作委员会：

• __builtin_ffs()
• __builtin_ctz()
• __builtin_clz()

这些通常直接映射到本机硬件指令。所以它不会比这些更快。

但是由于它们没有 C/C++ 功能，因此只能通过编译器内部函数访问它们。

您可以通过这种方式手动完成：

n & (n - 1) 是一种删除最右边的设置位的技术。

所以，n - (n & n - 1)将返回一个只有最右边的设置位的数字。

然后结果的“log2”给出了解决方案：此链接可能会有所帮助

您也可以使用开关盒，所有这些1 << k都会为您提供解决方案

switch (n - (n & n - 1)) {
    case 0: ...
    case 1 << 0: return 0;
    case 1 << 1: return 1;
    ...
}

Answer 2

如果您希望速度更快，则可以选择位扫描指令（bsf、bsr）或位旋转黑客。

编辑：使用 switch-case 表来提高性能的想法只不过是不成熟的。

Answer 3

Bit Twiddling Hacks提供了一系列优秀的，呃，bit twiddling hacks，并附有性能/优化讨论。对于您的问题（来自该站点），您可以使用乘法查找策略：

unsigned int c = number;  // your input number
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((c & -c) * 0x077CB531U)) >> 27];