return index of least significant bit in Python

Question

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 function already available in Python. I don't see one described for bitarray, but perhaps there's another. I am hoping to avoid calculating the answer by looping through all possible bit masks, though of course that's an option of last resort; ffs() simply returns a single integer and I'd like to know of something comparable in Python.

Answer 1

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

Answer 2

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.

Answer 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'

Answer 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.

Answer 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...

>>> def ffs(num):
...     # Check there is at least one bit set.
...     if num == 0:
...         return None
...     # 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) is None
True

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

Answer 6

I know there's a selected answer already, but had a crack at the problem myself, because I could. The solution is based around the idea that if the value is a power of two you can take the log base two to find its position. The rest of the implementation revolves around transforming the value so that we can simply take the log.

I haven't benchmarked it, but the transformation is O(1) where n is the number of bits (and this view somewhat unfairly ignores the complexity introduced by the log(), though maybe it's around O(log(n))? 1). The implementation is loosely based on the 'decrement and compare' power-of-two method from 2:

import math

def ffs(value):
    """Find the first set bit in an integer, returning its index (from zero)"""
    if 0 > value:
        raise ValueError("No negative values!")
    if 0 == value:
        # No bits are set in value
        return None
    if (value & (value - 1)) != 0:
        # Multiple bits are set in value. Transform value such that only the
        # lowest bit remains set.
        value &= ~ (value - 1)
    # Only one bit is set in value, find its index from zero
    return int(math.log(value, 2))

Answer 7

You can implement any of the algorithms identified here: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

I'm not aware of any native method to do so. (You could also write an extension to export the C function to Python, but that would probably not be worth the trouble :-)

Answer 8

It's a little silly to try and aggressively optimize Python code, so a simple for loop with counter and right-shift should be fine. If you wanted to go faster (which would make more sense in C, Java, or Assembly) you could binary-search for the right-most 1-bit and even use lookup tables to help you.

Suppose x is 64-bits and you want the LSB. Mask off the lower 32-bits. Assume x is nonzero:

if x & 0xffffffff == 0:
  if x & 0xffff00000000 == 0:
    # the LSB is in the highest two bytes
  else:
    # the LSB is in the 5th or 6th byte
else:
  if x & 0xffff0000:
    # the LSB is in the 3rd or 4th byte
  else:
    # the LSB is in the 1st or 2nd byte

How you handle the commented section above depends on how aggressive you want to be: you could do further binary searching analogous to what we have, or you could use a lookup table. As it stands, we have 16-bits of uncertainty, so our table would be 65,536 entries. I have actually made tables like this for extremely performance-sensitive code, but that was a C program that played Chess (the 64-bit string there was a binary representation of the board).

Answer 9

from math import log2
def bit_pos(n):
    """Returns the index, counting from 0, of the
    least significant set bit in `n`. If no bit is set, returns None.
    """   
    return int(log2(n^(n&(n-1)))) if n else None

bit_pos(32)
# returns 5