What's the fastest method to return the position of the least significant bit set in an integer in Python 3?

Question

I'm curious to find what the fastest algorithm is for returning the position of the least significant bit set in an integer in Python 3.

Are there algorithms faster than this one in Python 3? Any enhancements one could use to speed things up?

def lsb(n):
    temp = n & -n
    pos = -1
    while temp:
        temp >>= 1
        pos += 1
    return(pos)

http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set <- relevent — R Nar, Dec 08 '15 at 21:49
Possible duplicate: http://stackoverflow.com/questions/5520655/return-index-of-least-significant-bit-in-python — Robᵩ, Dec 08 '15 at 21:50
Likely to depend on the python implementation you are using. For CPython I'd just write a tiny extension module if I needed it to be super fast — John La Rooy, Dec 08 '15 at 22:02
Alternatively, for a purely integer-based solution try `(n & -n).bit_length() - 1`. — Mark Dickinson, Dec 08 '15 at 22:06
FYI, thus far in my perf testing of the three algorithms here, Mark Dickinson's is the fastest on my machine. — coffee-converter, Dec 08 '15 at 22:16

score 3 · Answer 1 · edited May 23 '17 at 12:23

summarizing, since this is for python3 and so not an exact duplicate of return index of least significant bit in Python (although there are other applicable answers there, some perhaps better):

jcomeau@aspire:/tmp$ cat lsb.py 
#!/usr/bin/python3
import math, sys
def lsb0(n):
    temp = n & -n
    pos = -1
    while temp:
        temp >>= 1
        pos += 1
    return(pos)
def lsb1(n):
    return int(math.log2(n & -n))
def lsb2(n):
    return (n & -n).bit_length() - 1
if __name__ == '__main__':
    algorithm = sys.argv[1]
    lsb = eval('lsb{n}'.format(n = algorithm))
    for n in range(1, 1000000):
        #print(lsb(n))
        lsb(n)

and as aaron_world_traveler observed, Mark Dickinson's answer is the fastest.

jcomeau@aspire:/tmp$ time lsb.py 0

real    0m2.506s
user    0m2.472s
sys 0m0.024s
jcomeau@aspire:/tmp$ time lsb.py 1

real    0m3.336s
user    0m3.284s
sys 0m0.040s
jcomeau@aspire:/tmp$ time lsb.py 2

real    0m1.646s
user    0m1.636s
sys 0m0.008s

What's the fastest method to return the position of the least significant bit set in an integer in Python 3?

1 Answers1

Linked