CODEWITHSUNDEEP
python
barak manos
barak manos

Reputation: 30136

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

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:

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.

Upvotes: 7

Views: 8470

Answers (5)

o11c
o11c

Reputation: 16076

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.

Upvotes: 23

nigel222
nigel222

Reputation: 8212

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.

Upvotes: 0

L3viathan
L3viathan

Reputation: 27283

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)

Upvotes: 1

TigerhawkT3
TigerhawkT3

Reputation: 49318

You could use str.rstrip:

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

Upvotes: 13

FallAndLearn
FallAndLearn

Reputation: 4135

This might do.

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

Upvotes: 4

Related Questions