整数转二进制: questions about efficiency的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:]

(切片只是去掉前缀)但我想尝试自己实现算法。

[edit] 我看到 append() 比简单的连接更有效(来自 this post )。在每一步追加然后反转列表怎么样？或者是否有类似有效的函数用于添加到列表的开头(如 insert())？

Answer 1

从不同的字符构建字符串时，使用列表然后 str.join() 比附加到字符串更快。后者必须为每个字符构建一个新的字符串对象。

也就是说，您可以通过使用位移位和位掩码来改进您的版本:

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

这仍然是从最低位到最高位逐位构建，但是附加而不是添加到列表中。然后我们在最后简单地反转列表。

• & 这里是binary AND operator ;它将 n 的值隐藏到最低有效位。

• >>= 是 augmented assignment >> right bit shift operation 的版本;这里它将 n 的位向右移动一位，丢弃最低有效位。

当然，在 Python 中将整数转换为二进制的最有效方法是不在 Python 中执行。内置的 bin() 函数很好，但是 format() function最好，因为它允许您指定是否包含 0b 前缀，并指定要显示的位数:

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