使用Python的基-2（二进制）表示法

Question

基于How Do You Express Binary Literals in Python的构建，我正在考虑以明智，直观的方式来编程以基本-2形式显示整数的栗子。这是我想出的最好的，但我想用一个更好的算法取代它，或者至少有一个应该有尖叫快的性能。

def num_bin(N, places=8): 
    def bit_at_p(N, p): 
     ''' find the bit at place p for number n ''' 
     two_p = 1 << p # 2^p, using bitshift, will have exactly one 
         # bit set, at place p 
     x = N & two_p # binary composition, will be one where *both* numbers 
         # have a 1 at that bit. this can only happen 
         # at position p. will yield two_p if N has a 1 at 
         # bit p 
     return int(x > 0) 

    bits = (bit_at_p(N,x) for x in xrange(places)) 
    return "".join((str(x) for x in bits)) 

    # or, more consisely 
    # return "".join([str(int((N & 1 << x)>0)) for x in xrange(places)]) 

Answer 1

为了获得最佳效率，您一般需要一次处理多个位。 您可以使用一种简单的方法来获取固定宽度的二进制表示。例如。

def _bin(x, width): 
    return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1)) 

_bin（x，8）现在将给出x的低8位的零填充表示。这可以用来建立一个查找表，允许你的转换器一次处理8位（或者如果你想把内存专用于它）更多。

_conv_table = [_bin(x,8) for x in range(256)] 

然后你就可以在你的真正的功能使用，剥离返回时，前导零。我还添加了对处理有符号数，因为没有它，你会得到一个无限循环（负整数概念上有一组符号位无限多的。）

def bin(x): 
    if x == 0: 
     return '0' #Special case: Don't strip leading zero if no other digits 
    elif x < 0: 
     sign='-' 
     x*=-1 
    else: 
     sign = '' 
    l=[] 
    while x: 
     l.append(_conv_table[x & 0xff]) 
     x >>= 8 
    return sign + ''.join(reversed(l)).lstrip("0") 

[编辑]更改代码来处理符号整数。
[编辑2]下面是各种解决方案的时序图。 bin是上面的函数，constantin_bin从Constantin's answer开始，num_bin是原始版本。出于好奇，我也尝试了上述16位查找表变种（bin16以下），并试用了Python3的内置bin（）函数。所有计时都是使用01010101位模式进行100000次运行。

Num Bits:    8  16  32  64  128  256 
--------------------------------------------------------------------- 
bin    0.544 0.586 0.744 1.942 1.854 3.357 
bin16    0.542 0.494 0.592 0.773 1.150 1.886 
constantin_bin  2.238 3.803 7.794 17.869 34.636 94.799 
num_bin   3.712 5.693 12.086 32.566 67.523 128.565 
Python3's bin  0.079 0.045 0.062 0.069 0.212 0.201 

正如你所看到的，使用大块处理长值时，是值得的，但没有什么比python3的内置的低级别的C代码（这奇怪的是，似乎在比128 256位始终更快！）。使用16位查找表可以改善事情，但除非真的需要它，否则可能不值得，因为它耗尽了大量内存，并且可能会引入一个小而简单的启动延迟来预先计算表。

Answer 2

不尖叫快，但简单：

>>> def bin(x): 
...  sign = '-' if x < 0 else '' 
...  x = abs(x) 
...  bits = [] 
...  while x: 
...    x, rmost = divmod(x, 2) 
...    bits.append(rmost) 
...  return sign + ''.join(str(b) for b in reversed(bits or [0])) 

它也快于num_bin：

>>> import timeit 
>>> t_bin = timeit.Timer('bin(0xf0)', 'from __main__ import bin') 
>>> print t_bin.timeit(number=100000) 
4.19453350997 
>>> t_num_bin = timeit.Timer('num_bin(0xf0)', 'from __main__ import num_bin') 
>>> print t_num_bin.timeit(number=100000) 
4.70694716882 

更有甚者，它实际工作正常（我的 “正确性” 的定义:) ）：

>>> bin(1) 
'1' 
>>> num_bin(1) 
'10000000'