如何有效地确定整数的二进制长度？

Question

我正在寻找一种使用 Python 确定二进制表示形式的整数长度的快速方法。在 C++ 中，可以考虑 uint64_t(log2(x) + 1.0).

让我们以下面的算法为例，该算法对 17 模 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

那些对底层数学问题感兴趣的人可能想看看这个MSE post。我想一步一步地进一步优化算法，我相信比特的计数绝对是一个可能的行动点。目前我正在使用 np.binary_repr(n) 然后通过 len(...).

测量它的长度

可能还有许多其他对性能至关重要的用例来确定整数的二进制长度。如果有任何加快速度的想法，我将不胜感激。也许有一些使用 log2 或类似技巧的方法？

Answer 1

in-built Python int 类型有一个方法 bit_length 这可能是最快的方法。

a = 3
print(a.bit_length())

Output: 2

如何有效地确定整数的二进制长度？

How to efficiently determine the binary length of an integer?

python

binary

performance