使用Python的Base-2(二进制)表示

在如何使用Python表达二进制文字的基础上,我正在考虑以明智,直观的方式来实现以基础2形式显示整数的编程101板栗.这是我提出的最好的,但我想用更好的算法替换它,或者至少一个应该具有尖叫 - 快速性能的算法.

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)])

Brian.. 13

为了获得最佳效率,您通常希望一次处理多个位.您可以使用一种简单的方法来获得固定宽度的二进制表示.例如.

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")

[编辑]更改了代码以处理有符号整数.
[Edit2]以下是各种解决方案的一些时序图.bin是上面的函数,constantin_bin来自Constantin的答案,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代码更好(奇怪的是,它似乎始终比256位快128位!).使用16位查找表可以改善一些事情,但可能不值得,除非你真的需要它,因为它占用了大量的内存,并且可以引入一个小的但非常规的启动延迟来预先计算表.

为了获得最佳效率,您通常希望一次处理多个位.您可以使用一种简单的方法来获得固定宽度的二进制表示.例如.

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")

[编辑]更改了代码以处理有符号整数.
[Edit2]以下是各种解决方案的一些时序图.bin是上面的函数,constantin_bin来自Constantin的答案,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代码更好(奇怪的是,它似乎始终比256位快128位!).使用16位查找表可以改善一些事情,但可能不值得,除非你真的需要它,因为它占用了大量的内存,并且可以引入一个小的但非常规的启动延迟来预先计算表.