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

Question

我正在寻找一种使用Python快速确定二进制表示中整数长度的方法。在C++中，可以考虑CCD_ 1。

让我们以下面的算法为例，该算法对余数为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的这篇文章。我想一步一步地进一步优化算法，我相信比特的计数绝对是一个可能的行动点。目前我使用np.binary_repr(n)，然后通过len(...)测量其长度。

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

Answer 1

内置的Python int类型有一个方法bit_length，这可能是最快的方法。

a = 3
print(a.bit_length())
Output: 2