在Python中返回最低有效位的索引

Question

C++有一组函数，叫做ffsl()、ffsl()和ffsl()，它们可以找到一个二进制整数中最末尾的那一位是1的位。

我在想，Python里有没有类似的函数。我没有看到bitarray里有这样的描述，但可能还有其他的选择。我希望能避免通过循环检查所有可能的位掩码来计算答案，当然这也是最后的办法；ffsl()只返回一个整数，我想知道在Python中有没有类似的东西。

Answer 1

你可以使用 ctypes 模块从共享库中加载函数（对于Windows用户来说就是DLL）。我在Ubuntu 10.10上成功加载了C标准库中的 ffs() 函数，这个函数在 libc.so.6 文件里：

>>> import ctypes
>>> libc = ctypes.cdll.LoadLibrary('libc.so.6')
>>> libc.ffs(136)
4

（注意，这里是从1开始计数的）。显然，这样做在不同平台上并不兼容；你需要根据你使用的系统来更改库的文件名（可以通过 sys.platform 或类似的方法来检测）。我甚至不能保证在不同的Linux发行版上它会是一样的。

另外，做一些真正的性能测试也是值得的，看看这样做是否真的有意义。如果这个函数被频繁调用，那可能是有价值的，但如果只是偶尔用一下，那么相比于Python实现，它的性能提升可能微乎其微，而维护它在不同平台上正常工作的麻烦就可能更大。

另一种选择是自己用C语言实现这个函数，并为它写一个Python的封装。这样你就需要为每个平台编译一次，但你可以避免寻找正确库名称的麻烦，同时又能保持速度上的优势。

Answer 2

仅在Python 2.7和3.1及以上版本中适用：

def ffs(x):
    """Returns the index, counting from 0, of the
    least significant set bit in `x`.
    """
    return (x&-x).bit_length()-1

示例：

>>> ffs(136)
3

Answer 3

这个功能可以在gmpy这个工具包中找到，它是为GNU多精度库提供的一个封装。在我的电脑上，它的速度大约比ctypes的解决方案快4倍。

>>> import gmpy
>>> gmpy.scan1(136)
3
>>> bin(136)
'0b10001000'