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.
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.
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
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