将整数转换为二进制的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))

我知道做同样事情的更简单的方法是使用：

^{pr2}$

（切片只是去掉了前缀）但是我想自己实现这个算法。在

[编辑]我发现append()比简单的串联（from this post）更有效。在每一步都加上，然后倒转列表怎么样？或者是否有一个类似有效的函数来添加到列表的开头（比如insert()）？在

Answer 1

速度差是如此之小以至于它真的无关紧要，但一般来说，使用list.append()比使用list = [bit] + list快，使用{}比串联快。在

Here's a reference for that.

Answer 2

strings are immutable objects in Python因此，在您的示例中，如果要连接字符串，则必须为while循环中的每个步骤重新创建它-这意味着它只会比使用列表更不理想。在

Answer 3

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

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

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

这仍然是一个一个地从最低有效位到最高有效位的构建，但是会附加而不是预先添加到列表中。然后我们简单地将列表倒过来。在

• &这里是binary AND operator；它将n的值屏蔽为最低有效位。

• >>=是^{} right bit shift operation的augmented assignment版本；这里它将n的位右移一步，去掉最低有效位。

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

^{pr2}$