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

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.

Answer 2

You could use str.rstrip:

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

Answer 3

This might do.

def trailing_zeros(n):
    s = str(n)
    return len(s)-len(s.rstrip('0'))

Answer 4

I'm not sure if this is the fastest solution, but it look like the most logical to me:

def trailing_zeros(n):
    for i in range(20):
        if n % (2<<i) != 0:
            return i

Since you asked for a single-line statement, here's one, but I don't think it's very legible (and its efficiency is worse than the other one):

max(i+1 for i in range(20) if n%(2<<i) == 0)

Answer 5

Definitely use bit-pushing operations, if you are concerned specifically with the underlying binary representation of the number. Divide and modulo-divide are the most costly operations, and relate to arithmetic not hardware bits. So (untested code)

def fnzb( n):
    " return position of first non-zero bit in n"
    if n==0:
        # edge case, there ARE no nonzero bits
        return None
    for po2 in range(0, 128) # or whatever larger upper limit is desired
        if a & ( 1 << po2) != 0: return po2
    # edge case, n too large
    raise ValueError,  "'impossibly' large integer argument encountered"

If these integers might often be extremely large with very many trailing zeros (for cryptographical values of "large") it might make an important difference to efficiency to initialize test=1 and right-shift it one place every trip around the loop, rather than starting with 1 and shifting it po2 places.