Return Index Of Least Significant Bit In Python

C++ has a set of functions, ffs(), ffsl(), and ffsll(), that return the least significant bit that is set in a given binary integer. I'm wondering if there is an equivalent functio

Solution 1:

Only in Pythons 2.7 and 3.1 and up:

defffs(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

Solution 2:

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'

Solution 3:

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.

Solution 4:

Really all these answers with external modules, defining functions, etc. for a... bitwise operation???

(1 + (x ^ (x-1))) >> 1

will return the least significant power of 2 in x.

For instance, with x=136, answer will be 2^3 = 8.

Trick is remembering that x-1 has the same digits as x except all least significant 1 and all following zeros; then performing a bitwise XOR bitwin X and X+1 extracts these digits.

Then, you can extract the index with the bit_length() method.

Solution 5:

To flesh out S.Lott's comment, if the LSB is set, the value will be odd and if it is clear, the value will be even. Hence we can just keep shifting the value right until it becomes odd, keeping track of how many shifts it takes for this to occur. Just remember to check that there is a bit set first, otherwise the loop will become endless when it is given the value 0...

>>>defffs(num):...# Check there is at least one bit set....if num == 0:...returnNone...# Right-shift until we have the first set bit in the LSB position....    i = 0...while (num % 2) == 0:...        i += 1...        num = num >> 1...return i...>>>num = 136>>>bin(num)
'0b10001000'
>>>ffs(num)
3
>>>ffs(0) isNone
True

Note that this treats the LSB as bit 0; simply initialise i to 1 if you'd rather have 1-based indexing.