15

对于给定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。

4

7 回答 7

34

在 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
于 2012-10-28T02:54:48.523 回答
4

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

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

frexp() 调用的C 函数只是抓取和调整指数。还有一些'splainin：

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

（来自另一个答案。）

于 2015-04-01T16:10:57.363 回答
3

您可以尝试log2numpy 中的函数，该函数似乎适用于高达 2^62 的幂：

>>> 2**np.log2(2**50) == 2**50
True
>>> 2**np.log2(2**62) == 2**62
True

除此之外（至少对我而言）它由于numpy内部数字类型的限制而失败，但这将处理您所说的范围内的数据。

于 2012-10-28T02:35:03.680 回答
2

适用于我，OSX 10.7 上的 Python 2.6.5 (CPython)：

>>> x = 2**50
>>> x
1125899906842624L
>>> p = int(log(x,2))
>>> p
50
>>> 2**p == x
True

它至少对高达 1e9 的指数仍然有效，到那时它开始需要相当长的时间来进行数学运算。你在测试中实际得到了x什么p？你在什么操作系统上运行什么版本的 Python？

于 2012-10-28T02:35:01.547 回答
2

关于“对大数不准确”，您的挑战是浮点表示确实不如您需要的那么精确（49.999999999993 != 50.0）。一个很好的参考资料是“ What Every Computer Scientist Should Know About Floating-Point Arithmetic ”。

好消息是 C 例程的转换非常简单：

def getpos(value):
    if (value == 0):
        return -1
    pos = 0
    if (value & (value - 1)):
        pos = 1
    if (value & 0xFFFFFFFF00000000):
        pos += 32
        value = value >> 32
    if (value & 0x00000000FFFF0000):
        pos += 16
        value = value >> 16
    if (value & 0x000000000000FF00):
        pos += 8
        value = value >> 8
    if (value & 0x00000000000000F0):
        pos += 4
        value = value >> 4
    if (value & 0x000000000000000C):
        pos += 2
        value = value >> 2
    if (value & 0x0000000000000002):
        pos += 1
        value = value >> 1
    return pos

另一种选择是您可以四舍五入到最接近的整数，而不是截断：

   log(x,2)
=> 49.999999999999993
   round(log(x,2),1)
=> 50.0
于 2012-10-28T02:37:59.297 回答
1

当心！接受的答案返回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
于 2022-02-15T07:19:09.453 回答
0

我需要计算 2 的上限幂（以计算使用模运算符在给定范围内生成随机数需要多少字节的熵）。

从一个粗略的实验中，我认为下面的计算给出了最小整数 p 使得 val < 2^p

它可能是你能得到的最快的，并且只使用按位整数运算。

def log2_approx(val):
    from math import floor
    val = floor(val)
    approx = 0
    while val != 0:
        val &= ~ (1<<approx)
        approx += 1
    return approx

对于给定的 n，您将计算出稍微不同的值

log2_approx(n) - 1

...也许。但无论如何，按位算术可以为您提供如何快速执行此操作的线索。

于 2016-10-31T23:42:57.573 回答