Python中正整数的位长度

Question

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

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

Answer 1

在python 2.7+中有一个int.bit_length()方法:

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

Answer 2

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

注意:对于负数不起作用,可能需要减去3而不是2

Answer 3

如果您的 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 4

def bitcounter(n):
    return math.floor(math.log(n,2)) + 1

编辑已修复，使其适用于 1