How to efficiently determine the binary length of an integer? [duplicate]
I am searching for a fast way to determine the length of an integer in its binary representation using Python. In C++ one may consider uint64_t(log2(x) + 1.0)
.
Let us take for example the following algorithm that counts numbers having a remainder 17 modulo 24:
def count17mod24(s:int, max_bin_len:int)->int:
x=0
q = queue.Queue()
q.put(s)
while not q.empty():
n = q.get()
if n%3 == 2:
q.put((2*n-1)//3)
if n % 24 == 17:
x += 1
if len(np.binary_repr(n)) < len(np.binary_repr(s))+max_bin_len-1:
q.put(4*n+1)
elif n%3 == 0:
if len(np.binary_repr(n)) < len(np.binary_repr(s))+max_bin_len-1:
q.put(4*n+1)
elif n%3 == 1:
if len(np.binary_repr(n)) < len(np.binary_repr(s))+max_bin_len and n>1:
q.put((4*n-1)//3)
if len(np.binary_repr(n)) < len(np.binary_repr(s))+max_bin_len-1:
q.put(4*n+1)
return x
Those interested in the underlying mathematical problem may want to take a look at this MSE post. I would like to further optimize the algorithm step by step and I believe that the counting of the bits is definitely a possible point of action. Currently I am using np.binary_repr(n)
and then measuring its length via len(...)
.
There are probably many other performance-critical use cases for determining an integers's binary length. I would be very grateful for any ideas to speed this up. Maybe there are some approaches using log2 or similar tricks?
The in-built Python int type has a method bit_length that’s probably the fastest way to do this.
a = 3
print(a.bit_length())
Output: 2