使用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'