Python中正整数的位长

Question

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

如何获取整数的位长度，即在Python中表示正整数所需的位数？

Answer 1

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

注意：对于负数不起作用，可能需要减3而不是2

Answer 2

如果您的Python版本有它（Python 2的≥2.7，Python 3的≥3.1），请使用标准库中的^{}方法。

否则，len(bin(n))-2as suggested by YOU很快（因为它是用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 3

在python 2.7+中有一个^{}方法：

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