在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的解决方案:计算快速日志库2天花板

然而,它似乎有点难看,我不确定如何将其转换为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

Answer 2

当心！接受的答案返回floor(log(n, 2))，而不是ceil(log(n, 2))像问题标题所暗示的那样！

如果您来这里是为了 clog2 实现，请执行以下操作：

def clog2(x):
    """Ceiling of log2"""
    if x <= 0:
        raise ValueError("domain error")
    return (x-1).bit_length()

为了完整性：

def flog2(x):
    """Floor of log2"""
    if x <= 0:
        raise ValueError("domain error")
    return x.bit_length() - 1

Answer 3

您在注释中指定您的 x 是一个整数，但是对于来到这里的任何人，如果他们的 x 已经是 float ，那么math.frexp()在提取以 2 为底的对数时会非常快：

log2_slow = int(floor(log(x, 2)))
log2_fast = frexp(x)[1]-1

frexp() 调用的 C 函数只是获取并调整指数。更多的“说明”：

• 下标[1]是因为 frexp() 返回一个元组（有效数字，指数）。
• 减法-1考虑了 [0.5,1.0) 范围内的有效数。例如 2 ⁵⁰存储为 0.5x2 ⁵¹。
• Floor() 是因为您指定了2^p <= x，所以p == floor(log(x,2))。

（源自另一个答案。）