python - 在 python 中计算快速对数基数 2 上限

Question

给定x < 10^15 , 快速准确判断最大整数p这样 2^p <= x

以下是我尝试过的一些方法:

首先我尝试了这个，但它对大数字来说并不准确:

>>> from math import log
>>> x = 2**3
>>> x
8
>>> p = int(log(x, 2))
>>> 2**p == x
True
>>> x = 2**50
>>> p = int(log(x, 2))
>>> 2**p == x #not accurate for large numbers?
False

我可以尝试这样的事情:

p = 1
i = 1
while True:
    if i * 2 > n:
        break
    i *= 2
    p += 1
    not_p = n - p

如果 p 为 50，最多需要 50 次操作

我可以预先计算 2 的所有幂直到 2^50，然后使用二进制搜索找到 p。这将需要大约 log(50) 次操作，但似乎有点过度和丑陋？

我为基于 C 的解决方案找到了这个线程:Compute fast log base 2 ceiling

但是它看起来有点难看，我不确定如何将它转换为 python。

Answer 1

在 Python >= 2.7 中，可以使用整数的 .bit_length() 方法:

def brute(x):
    # determine max p such that 2^p <= x
    p = 0
    while 2**p <= x:
        p += 1
    return p-1

def easy(x):
    return x.bit_length() - 1

给出

>>> brute(0), brute(2**3-1), brute(2**3)
(-1, 2, 3)
>>> easy(0), easy(2**3-1), easy(2**3)
(-1, 2, 3)
>>> brute(2**50-1), brute(2**50), brute(2**50+1)
(49, 50, 50)
>>> easy(2**50-1), easy(2**50), easy(2**50+1)
(49, 50, 50)
>>> 
>>> all(brute(n) == easy(n) for n in range(10**6))
True
>>> nums = (max(2**x+d, 0) for x in range(200) for d in range(-50, 50))
>>> all(brute(n) == easy(n) for n in nums)
True