快速确定64位中最右边第n位的方法

Question

我尝试确定最右边的第n位集

if (value & (1 << 0)) { return 0; }
if (value & (1 << 1)) { return 1; }
if (value & (1 << 2)) { return 2; }
...
if (value & (1 << 63)) { return 63; }

如果比较需要做64次.有没有更快的方法？

Answer 1

这有一个小技巧:

value & -value

这使用负数的二进制补码整数表示.

编辑:这并不完全给出问题中给出的确切结果.其余的可以用一个小的查找表来完成.

Answer 2

如果您正在使用GCC,请使用__builtin_ctz或__builtin_ffs功能.(http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005fffs-2894)

如果您使用的是MSVC,请使用该_BitScanForward功能.请参阅如何使用MSVC内在函数来获得此GCC代码的等效代码？.

在POSIX中还有一个ffs功能.(http://linux.die.net/man/3/ffs)