# [SOLVED] Python – Fastest way to strip the trailing zeros from the bit representation of a number

## Issue

This is the python version of the same C++ question.

Given a number, `num`, what is the fastest way to strip off the trailing zeros from its binary representation?

For example, let `num = 232`. We have `bin(num)` equal to `0b11101000` and we would like to strip the trailing zeros, which would produce `0b11101`. This can be done via string manipulation, but it’d probably be faster via bit manipulation. So far, I have thought of something using `num & -num`

Assuming `num != 0`, `num & -num` produces the binary `0b1<trailing zeros>`. For example,

``````num   0b11101000
-num  0b00011000
&         0b1000
``````

If we have a `dict` having powers of two as keys and the powers as values, we could use that to know by how much to right bit shift `num` in order to strip just the trailing zeros:

``````#        0b1     0b10     0b100     0b1000
POW2s = {  1: 0,    2: 1,     4: 2,      8: 3, ... }

def stripTrailingZeros(num):
pow2 = num & -num
pow_ = POW2s[pow2]  # equivalent to math.log2(pow2), but hopefully faster
return num >> pow_
``````

The use of dictionary `POW2s` trades space for speed – the alternative is to use `math.log2(pow2)`.

Is there a faster way?

Perhaps another useful tidbit is `num ^ (num - 1)` which produces `0b1!<trailing zeros>` where `!<trailing zeros>` means take the trailing zeros and flip them into ones. For example,

``````num    0b11101000
num-1  0b11100111
^          0b1111
``````

Yet another alternative is to use a while loop

``````def stripTrailingZeros_iterative(num):
while num & 0b1 == 0:  # equivalent to `num % 2 == 0`
num >>= 1
return num
``````

Ultimately, I need to execute this function on a big list of numbers. Once I do that, I want the maximum. So if I have `[64, 38, 22, 20]` to begin with, I would have `[1, 19, 11, 5]` after performing the stripping. Then I would want the maximum of that, which is `19`.

## Solution

You say you "Ultimately, [..] execute this function on a big list of numbers to get odd numbers and find the maximum of said odd numbers."

So why not simply:

``````from random import randint

numbers = [randint(0, 10000) for _ in range(5000)]

odd_numbers = [n for n in numbers if n & 1]
max_odd = max(odd_numbers)
print(max_odd)
``````

To do what you say you want to do ultimately, there seems to be little point in performing the "shift right until the result is odd" operation? Unless you want the maximum of the result of that operation performed on all elements, which is not what you stated?

I agree with @TimPeters answer, but if you put Python through its paces and actually generate some data sets and try the various solutions proposed, they maintain their spread for any number of integer size when using Python `int`s, so your best option is integer division for numbers up to 32-bits, after that see the chart below:

``````from pandas import DataFrame
from timeit import timeit
import math
from random import randint

def reduce0(ns):
return [n // (n & -n)
for n in ns]

def reduce1(ns, d):
return [n >> d[n & -n]
for n in ns]

def reduce2(ns):
return [n >> int(math.log2(n & -n))
for n in ns]

def reduce3(ns, t):
return [n >> t.index(n & -n)
for n in ns]

def reduce4(ns):
return [n if n & 1 else n >> ((n & -n).bit_length() - 1)
for n in ns]

def single5(n):
while (n & 0xffffffff) == 0:
n >>= 32
if (n & 0xffff) == 0:
n >>= 16
if (n & 0xff) == 0:
n >>= 8
if (n & 0xf) == 0:
n >>= 4
if (n & 0x3) == 0:
n >>= 2
if (n & 0x1) == 0:
n >>= 1
return n

def reduce5(ns):
return [single5(n)
for n in ns]

numbers = [randint(1, 2 ** 16 - 1) for _ in range(5000)]
d = {2 ** n: n for n in range(16)}
t = tuple(2 ** n for n in range(16))
assert(reduce0(numbers) == reduce1(numbers, d) == reduce2(numbers) == reduce3(numbers, t) == reduce4(numbers) == reduce5(numbers))

df = DataFrame([{}, {}, {}, {}, {}, {}])
for p in range(1, 16):
p = 2 ** p
numbers = [randint(1, 2 ** p - 1) for _ in range(4096)]

d = {2**n: n for n in range(p)}
t = tuple(2 ** n for n in range(p))

df[p] = [
timeit(lambda: reduce0(numbers), number=100),
timeit(lambda: reduce1(numbers, d), number=100),
timeit(lambda: reduce2(numbers), number=100),
timeit(lambda: reduce3(numbers, t), number=100),
timeit(lambda: reduce4(numbers), number=100),
timeit(lambda: reduce5(numbers), number=100)
]
print(f'Complete for {p} bit numbers.')

print(df)
df.to_csv('test_results.csv')
``````

Result (when plotted in Excel):

Note that the plot that was previously here was wrong! The code and data were not though. The code has been updated to include @MarkRansom’s solution, since it turns out to be the optimal solution for very large numbers (over 4k-bit numbers).