在Python中计算对数以2为底的上取整值

Question

在Python中计算对数以2为底的上取整值

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。

- Rusty Rob

1

你可能需要阅读位移操作和按位与/或/异或的文档。这可以帮助你将C代码翻译成Python。 - mtrw

类似于https://dev59.com/rnM_5IYBdhLWcg3wlEBH#19164783 - endolith

1

也许您的意思是 floor 而不是 ceiling（天花板）？因为 p 是最大的整数，使得 2^p <= x，那么 p == floor(log(x,2))。 - Bob Stein

在你链接的另一个问题中，他们确实是指天花板函数，就像 q == ceil(log(x,2)) 一样。 - Bob Stein

7个回答

7

注意！被接受的答案返回的是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

- Alex Mykyta

5

你在评论中指明了x是整数，但是对于那些x已经是浮点数的人来说，使用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))。

（摘自另一个答案）

- Bob Stein

3

您可以尝试使用NumPy中的log2函数，它可以处理高达2^62次幂的计算：

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

在我看来，由于numpy内部数字类型的限制，它无法处理超出范围的数据。但是它可以处理您所说的数据范围。

- BrenBarn

2

对我来说可以工作，Python 2.6.5 (CPython) 在 OSX 10.7 上：

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

它至少可以处理指数为1e9的值，但此时进行数学计算需要一些时间。请问在您的测试中x和p分别代表什么？您正在运行哪个操作系统上的Python版本？

- Russell Borogove

以下是一个与程序有关的内容翻译：这里有一个错误示例 -- 你必须点击“运行会话”按钮。 - Brian Cain

1

我得到的是49.999999而不是50.0，可能是因为我的电脑是32位的。 - Rusty Rob

我不会预料到32位和64位会影响math.log函数。很奇怪。 - Russell Borogove

2

关于“对于大数不准确”的问题，您面临的挑战是浮点表示确实不如您需要的那样精确（49.999999999993 != 50.0）。一个很好的参考资料是“计算机科学家应该了解的浮点运算知识”。

好消息是，将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

- Brian Cain

0

我需要计算二的上限幂（以确定使用模运算生成给定范围内随机数所需的熵字节数）。

通过粗略实验，我认为以下计算可以给出最小整数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

或许吧。但无论如何，位运算可以给你一个快速解决这个问题的线索。

- cefn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DSM · Accepted Answer

在 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