将整数转换为二进制的Python算法：效率问题

Question

我写了一个简单的算法，用来把一个整数转换成二进制，并把这个二进制以字符串的形式返回。目前，我是把每一位二进制数加到一个列表的前面。这样做在时间或空间上会更有效率吗？如果用每一步都拼接字符串的方式呢？这样做有什么好处或坏处？

def toBinary(n):
    l = []
    while n > 0:
        bit = n%2
        n = math.floor(n/2)
        l = [bit]+l
    return ''.join(map(str,l))

我知道有一个更简单的方法可以做到同样的事情，就是用：

bin(10)[2:]

（这里的切片只是去掉了前面的部分），但我想自己实现这个算法。

[编辑] 我发现使用append()比简单的字符串拼接要高效（参考这篇文章）。那么如果每一步都添加到列表中，然后再反转这个列表呢？或者有没有什么同样高效的方法可以在列表的开头添加元素（比如insert()）？

Answer 1

在Python中，字符串是不可变的对象，这意味着一旦你创建了一个字符串，它就不能被改变。所以在你的例子中，如果你想把字符串连接起来，每次在循环中都需要重新创建一个新的字符串。这就导致了效率不如使用列表。

Answer 2

速度上的差别非常小，几乎可以忽略不计。不过一般来说，使用 list.append() 这个方法比用 list = [bit] + list 要快，而使用 ''.join(list) 这个方法比直接拼接字符串要快。

这里有个参考链接。

Answer 3

在用不同的字符拼接成一个字符串时，先把字符放到一个列表里，然后用 str.join() 方法比直接往字符串后面加要快。因为后者每加一个字符就得重新创建一个新的字符串对象。

不过，你可以通过使用位移和位掩码来改进你的代码：

def toBinary(n):
    l = []
    while n:
        l.append(n & 1)
        n >>= 1
    return ''.join(map(str, reversed(l)))

这个方法还是一个一个地从最低位到最高位构建位，但它是往列表后面加，而不是前面加。最后我们只需要把列表反转一下就行了。

• & 是一个 二进制与运算符；它只保留 n 的最低有效位。

• >>= 是 增强赋值 版本的 >> 右移位运算；这里它把 n 的位向右移动了一位，丢掉了最低有效位。

当然，在 Python 中把整数转换成二进制的最有效方法其实是不要在 Python 中做。内置的 bin() 函数不错，但 format() 函数 更好，因为它可以让你选择是否包含 0b 前缀，还可以指定显示的位数：

>>> format(10, 'b')
'1010'
>>> format(10, '#b')
'0b1010'
>>> format(10, '08b')
'00001010'
>>> format(10, '#010b')
'0b00001010'