Pythonic way to count the number of trailing zeros in base 2

Question

I'm looking for a Pythonic way to count the number of trailing zeros in the binary representation of a positive integer n (which will indicate the highest power of 2 which divides n without remainder).

A simple solution:

def CountZeros(n):
    c = 0
    while (n % 2) == 0:
        n /= 2
        c += 1
    return c

But in order to do it in a more Pythonic manner, I think that I can make use of:

• bin(n)[2:], which gives the binary representation of n
• bin(n)[:1:-1], which gives the reversed binary representation of n

So my question can be reduced to counting the number of trailing zeros in a string.

Is there any single-statement way to do this?

My ultimate goal is a Pythonic way for computing the highest power of 2 which divides n without remainder, so any ways to do this not by counting the trailing zeros in a string are also appreciated.

Answer 1

You could use str.rstrip:

def trailing(s):
    return len(s) - len(s.rstrip('0'))

Answer 2

It's twice as fast to avoid converting to string with bin, instead using a modified bithack, since we already have an efficient log2 implementation.

def ctz(v):
    return (v & -v).bit_length() - 1

The above returns -1 if the input is 0.

Using C makes it twice as fast again:

from gmpy2 import bit_scan1 as ctz

This version returns None if input is zero.

---

As an example, consider the infinite binary expansion if the input is 20:

v    000...00010100
~v   111...11101011 (not used directly, all bits opposite)
-v   111...11101100 (-v == ~v + 1; this causes all low 1 bits to overflow and carry)
v&-v 000...00000100 (has a single 1 bit, from the carry)

When the are anded, all the leading zero and one bits are opposite, but the last 1 bit and all trailing zeros are the same both ways.

Then .bit_length() tells us the integers is using 3 bits total, so just subtract 1 to only consider the zeros.