Python中正整数所需的最小位长度

Question

1 = 0b1 -> 1
5 = 0b101 -> 3
10 = 0b1010 -> 4
100 = 0b1100100 -> 7
1000 = 0b1111101000 -> 10
…

我怎样才能得到一个整数的位数，也就是在Python中表示一个正整数所需的位数？

Answer 1

如果你的Python版本支持这个功能（Python 2需要版本≥2.7，Python 3需要版本≥3.1），可以使用标准库里的bit_length方法。

如果不支持，可以用len(bin(n))-2，这个方法很快（因为它是用Python实现的）。需要注意的是，这个方法对0的返回值是1。

另外，还有一个简单的方法，就是不断地把数字除以2（这其实就是简单的位移操作），然后数一下需要多少次才能除到0。

def bit_length(n): # return the bit size of a non-negative integer
    bits = 0
    while n >> bits: bits += 1
    return bits

对于大数字来说，这种方法会显著更快（根据我的快速测试，处理1000位数字时速度比之前的方法快10倍以上），可以一次性处理多个字节，然后再回过头来处理最后一个字节的位。

def bit_length(n): # return the bit size of a non-negative integer
    if n == 0: return 0
    bits = -32
    m = 0
    while n:
        m = n
        n >>= 32; bits += 32
    while m: m >>= 1; bits += 1
    return bits

在我的快速测试中，len(bin(n))的速度明显比处理多个字节的方法还要快。虽然bin(n)会生成一个字符串并立即丢弃，但它的速度快是因为它内部有一个编译成机器代码的循环。（math.log的速度更快，但这不重要，因为它的结果是错误的。）

Answer 2

>>> len(bin(1000))-2
10
>>> len(bin(100))-2
7
>>> len(bin(10))-2
4

注意: 这个方法对负数不适用，可能需要减去3而不是2。

Answer 3

在 Python 2.7 及以上版本中，有一个叫做 int.bit_length() 的方法：

>>> a = 100
>>> a.bit_length()
7

Python中正整数所需的最小位长度

7 个回答

撰写回答