Python中精确计算log(x,2)的方法

Question

在Python中，我需要获取以2为底的正整数向下取整后的对数，包括大数。

但是，由于使用了浮点数计算，可能会得到错误的结果，例如：

>>> import math
>>> int(math.log(281474976710655, 2))
48

然而：

>>> 2 ** 48
281474976710656

因此，正确的结果应该向下取整为47。

我如何获取正确的值？

- Udi

Answer 1

在Python 3中，整数具有`.bit_length`方法，因此您应该使用它来获取向下取整的基数2对数。

以下是一个简短的演示：

m = 2 ** 1000
for n in (281474976710655, m-1, m, m+1):
    a = n.bit_length() - 1
    b = 2 ** a
    print(a, b <= n < 2 * b)

输出

47 True
999 True
1000 True
1000 True

- PM 2Ring

Answer 2

在Python 3中，int类型甚至有一个高效的.bit_length()方法！

>>> (281474976710655).bit_length()
48
>>> (281474976710656).bit_length()
49

在Python 2中，可以通过计算位数来代替使用浮点数运算：

def log2(n):
    assert n >= 1
    return len(bin(n)) - 3  # bin() returns a string starting with '0b'

(在此评论之后编辑)

- Udi

---

这对于Python 2来说没问题，但在Python 3中，.bit_length 比将数字转换为二进制字符串更有效。顺便说一句，在Python 2.6+中，使用 format(n, 'b') 比 bin 更方便，因为你不会得到那个讨厌的 '0b'。 - PM 2Ring