How to skip trailing zero bits in built-it int?

Question

Is there some fast way how to get number of trailing zeros in Python3 built-in integer?

For example if I want to check if there are 4 trailing zeroes I can do following:

>>> some_integer & 15

Or for 8 trailing zeros:

>>> some_integer & 255

If result is not 0, there are ones in the first 4 or 8 bits.

Is there way how to do this operation in general way? My goal is to skip any number of trailing zeroes via >> operator.

Answer 1

You could use bitwise arithmetic (for positive and negative values, but excluding 0, for which the behavior is not defined as there is no 1 to trail):

(x & -x).bit_length() - 1

or:

(x ^ -x).bit_lenght() - 2

or, possibly with a more interesting 0 behavior (thanks to @TomKarzes comment):

(x ^ (x - 1)).bit_length() - 1

To understand how they work, let us consider this last expression. When we do x - 1, if x is odd, only that bit is flipped and then when we do the xor ^ that is the only bit that survives the operation. Similarly, when x is not odd, every trailing zero gets flipped to 1 and the trailed1 gets flipped to 0, all the other bits are untouched, and then we do the xor all the bits up to the trailed 1 gets to be set. Then, int.bit_length() counts how many significant bits are found, and the -1 is just a constant offset we need to have to get "number of trailing zeros".

Why the first methods also work is due to the two-complement representation of negative numbers. The exact details are left as an exercise to the reader.

To show that they work:

for i in range(-15, 16): 
     print(
         f'{i:5b}',
         f'{i ^ -i:3d}',
         f'{(i & -i).bit_length() - 1:2d}',
         f'{(i ^ -i).bit_length() - 2:2d}',
         f'{(i ^ (i - 1)).bit_length() - 1:2d}') 

-1111  -2  0  0  0
-1110  -4  1  1  1
-1101  -2  0  0  0
-1100  -8  2  2  2
-1011  -2  0  0  0
-1010  -4  1  1  1
-1001  -2  0  0  0
-1000 -16  3  3  3
 -111  -2  0  0  0
 -110  -4  1  1  1
 -101  -2  0  0  0
 -100  -8  2  2  2
  -11  -2  0  0  0
  -10  -4  1  1  1
   -1  -2  0  0  0
    0   0 -1 -2  0
    1  -2  0  0  0
   10  -4  1  1  1
   11  -2  0  0  0
  100  -8  2  2  2
  101  -2  0  0  0
  110  -4  1  1  1
  111  -2  0  0  0
 1000 -16  3  3  3
 1001  -2  0  0  0
 1010  -4  1  1  1
 1011  -2  0  0  0
 1100  -8  2  2  2
 1101  -2  0  0  0
 1110  -4  1  1  1
 1111  -2  0  0  0

Note the different behavior of the two expressions for 0 input. Particularly, (x ^ (x - 1)).bit_length() - 1 may lead to simpler expressions if you want 0 input to produce 0 output.

---

Speed-wise this should be brutally faster than any loop-based solution, and on-par with look-up based solutions (but without size limitation and without using additional memory):

def trail_zero_loop(x):
    if x != 0:
        k = -1
        r = 0
        while not r:
            # x, r = divmod(x, 2)  # ~15% slower
            r = x % 2
            x = x // 2
            k += 1
        return k
    else:
        return -1

def trail_zero_and(x):
    return (x & -x).bit_length() - 1

def trail_zero_xor(x):
    if x != 0:
        # return (x ^ -x).bit_length() - 2  # ~1% slower
        return (x ^ (x - 1)).bit_length() - 1
    else:
        return -1

_LOOKUP =[ 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 ]


def trail_zero_lookup(x):
    if x != 0:
        return _LOOKUP[(x & -x) % 37]
    else:
        return -1

n = 2 ** 30
%timeit trail_zero_loop(n)
# 3.15 µs ± 25.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
%timeit trail_zero_and(n)
# 228 ns ± 9.87 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_xor(n)
# 253 ns ± 7.25 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_lookup(n)
# 294 ns ± 1.81 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

The eventual additional bit-shift operation takes only some nanoseconds so it should be irrelevant here.

Answer 2

n = 12 # 0b1100
while n % 2 == 0:
    n //= 2
# out: 3 i.e. 0b11

This divides the number by two until indivisibility and thus removes trailing zeroes.

EDIT: realised that the above code infinite-loops if n==0. Correctable:

n = 12 # 0b1100
if n != 0:
    while n % 2 == 0: n //= 2
# out: 3 i.e. 0b11

EDIT: Drew upon suggestions from @MisterMiyagi.

n = 10 # 0b1010
if n != 0:
  while n % 2 == 0: n, r = divmod(n, 2)
# n = 5 i.e. 0b101

Answer 3

For arbitrary long numbers

def remove_tailing_zeroes(n):
    return n >> get_number_of_trailing_zeroes(n)

def get_number_of_trailing_zeroes(n):
    c = 0
    while True:
        n, r = divmod(n, 2)
        if 0 != r:
            break
        c+=1
    return c

Fast and efficient solution without loops, for 32-bit numbers

LOOKUP =[ 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 ]

def remove_tailing_zeroes(n):
    return n >> LOOKUP[(n & -n) % 37]

def get_number_of_trailing_zeroes(n):
    return LOOKUP[(n & -n) % 37]

Adaptation from Bit Twiddling Hacks by Sean Eron Anderson

You can shift right by that number of trailing zeroes and get rid of them (denoted in shifted = n >> r).

Test

for n in range(1, 20):
    r = get_number_of_trailing_zeroes(n)
    shifted = n >> r
    print(f'n: {n} bin: {bin(n)} zeroes: {r} shifted: {bin(shifted)}')
    assert 0 == get_number_of_trailing_zeroes(shifted)

Output:

n: 1 bin: 0b1 zeroes: 0 shifted: 0b1
n: 2 bin: 0b10 zeroes: 1 shifted: 0b1
n: 3 bin: 0b11 zeroes: 0 shifted: 0b11
n: 4 bin: 0b100 zeroes: 2 shifted: 0b1
n: 5 bin: 0b101 zeroes: 0 shifted: 0b101
n: 6 bin: 0b110 zeroes: 1 shifted: 0b11
n: 7 bin: 0b111 zeroes: 0 shifted: 0b111
n: 8 bin: 0b1000 zeroes: 3 shifted: 0b1
n: 9 bin: 0b1001 zeroes: 0 shifted: 0b1001
n: 10 bin: 0b1010 zeroes: 1 shifted: 0b101
n: 11 bin: 0b1011 zeroes: 0 shifted: 0b1011
n: 12 bin: 0b1100 zeroes: 2 shifted: 0b11
n: 13 bin: 0b1101 zeroes: 0 shifted: 0b1101
n: 14 bin: 0b1110 zeroes: 1 shifted: 0b111
n: 15 bin: 0b1111 zeroes: 0 shifted: 0b1111
n: 16 bin: 0b10000 zeroes: 4 shifted: 0b1
n: 17 bin: 0b10001 zeroes: 0 shifted: 0b10001
n: 18 bin: 0b10010 zeroes: 1 shifted: 0b1001
n: 19 bin: 0b10011 zeroes: 0 shifted: 0b10011