-1

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?

2
  • The underlying principle of everyone have while(n): n>>=1 ig. Jan 23, 2022 at 15:29
  • Yes - thank you very much. This makes my question obsolete. I tried to delete my question, but got a warning, which makes me feeling reluctant to delete it. Jan 23, 2022 at 15:52

1 Answer 1

4

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.