使用Python进行二进制表示

Question

在讨论如何在Python中表示二进制字面量的基础上，我在想一些简单易懂的方法来展示整数的二进制形式。这是我想到的最好方法，但我希望能用一个更好的算法来替代它，或者至少是一个性能非常快的算法。

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):
...     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'

Answer 2

为了提高效率，通常你希望一次处理多个比特位，而不是单个比特位。你可以用一个简单的方法来获取固定宽度的二进制表示。例如：

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 的回答，num_bin 是原始版本。出于好奇，我还尝试了上面的 16 位查找表变体（bin16），并试用了 Python3 的内置 bin() 函数。所有的时间都是基于 100000 次运行，使用的是 01010101 的比特模式。

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 代码（奇怪的是，它在 256 位时的速度似乎比 128 位更快！）。使用 16 位查找表可以改善性能，但如果你不真的需要，可能不值得，因为这会占用大量内存，并且可能会引入一个小但明显的启动延迟来预计算表格。