return index of least significant bit in Python
Only in Pythons 2.7 and 3.1 and up:
def ffs(x):
"""Returns the index, counting from 0, of the
least significant set bit in `x`.
"""
return (x&-x).bit_length()-1
Example:
>>> ffs(136)
3
It is available in the gmpy wrapper for the GNU Multi-Precision library. On my system, it is about 4x faster than the ctypes solution.
>>> import gmpy
>>> gmpy.scan1(136)
3
>>> bin(136)
'0b10001000'
It is possible to load functions from shared libraries (DLLs for Windows users) using the ctypes module. I was able to load the ffs()
function from the C standard library, contained in libc.so.6
on Ubuntu 10.10:
>>> import ctypes
>>> libc = ctypes.cdll.LoadLibrary('libc.so.6')
>>> libc.ffs(136)
4
(Note that this uses 1-based indexing). Obviously, this is not cross-platform compatible as-is; you'll need to change the filename of the library to load based on which system you're operating under (detected from sys.platform
or similar). I wouldn't even be 100% sure it'd be the same on different Linux distributions.
It'd also be worth doing some proper benchmarking to see if its really worth it. If its called frequently it could be, but if its only used occasionally, the performance benefit over a Python implementation would probably be negligible compared to the maintenance to ensure it keeps working on different platforms.
An alternative would be to write your own implementation of the function in C and come up with a Python wrapper. You'd then have to compile it for each platform you want, but you lose the hassle of finding the correct library name while retaining the speed benefits.