Representación de Base-2 (Binario) usando Python

Question

Construyendo en How Do You Express Binary Literals in Python, estaba pensando en formas sensatas e intuitivas de hacer eso Programando 101 castaño de mostrar enteros en forma de base-2. Esto es lo mejor que se me ocurrió, pero me gustaría reemplazarlo con un mejor algoritmo, o al menos uno que debería tener un rendimiento increíblemente rápido.

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

Para obtener la mejor eficacia, generalmente desea procesar más de un bit a la vez. Puede usar un método simple para obtener una representación binaria de ancho fijo. p.ej.

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

_bin (x, 8) será ahora dar una representación acolchado cero de 8 bits inferiores de x. Esto se puede utilizar para crear una tabla de búsqueda, lo que permite que su convertidor procese 8 bits a la vez (o más si desea dedicarle la memoria).

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

Luego puede usar esto en su función real, quitando los ceros a la izquierda al devolverlo. También he añadido el manejo de números con signo, ya que sin ella obtendrá un bucle infinito (enteros negativos conceptualmente tienen un número infinito de bits de signo de ajuste.)

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

[Editar] código modificado para manejar enteros con signo.
[Editar2] Aquí hay algunas cifras de tiempo de las diversas soluciones. bin es la función anterior, constantin_bin es de Constantin's answer y num_bin es la versión original. Por curiosidad, también probé una variante de tabla de búsqueda de 16 bits de la anterior (bin16 a continuación), y probé la función bin() integrada de Python3. Todos los tiempos fueron para 100000 ejecuciones usando un patrón de 01010101 bits.

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 

Como se puede ver, procesar valores largos usando grandes trozos realmente vale la pena, pero no hay nada como el código C de bajo nivel de orden interna de python3 (que extrañamente parece consistentemente más rápido a 256 bits que 128!). Usar una tabla de búsqueda de 16 bits mejora las cosas, pero probablemente no valga la pena a menos que realmente lo necesite, ya que consume una gran cantidad de memoria y puede presentar un retraso de inicio pequeño pero no significativo para calcular previamente la tabla.

Answer 2

No gritando rápido, pero sencillo:

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

Es también más rápido que 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 

Aún más, en realidad funciona correctamente (por mi definición de "corrección" :)):

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