pasar - Representación de Base-2(Binario) con Python

conversion de binario a decimal

Question

Sobre la base de cómo se expresan literales binarios en Python , estaba pensando en formas sensatas e intuitivas de hacer esa castaña de programación 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

No gritando, rápido, pero directo:

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

También es 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 (para mi definición de "corrección" :)):

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

Answer 2

Para obtener la mejor eficacia, generalmente desea procesar más de un bit por 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) ahora dará una representación acolchada cero de los 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)]

Entonces puede usar esto en su función real, eliminando ceros a la izquierda al devolverlo. También he agregado el manejo de los números con signo, ya que sin él obtendrás un bucle infinito (los números enteros negativos tienen conceptualmente un número infinito de bits de signo configurados).

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.
[Edit2] Aquí hay algunas cifras de tiempo de las diversas soluciones. bin es la función de arriba, constantin_bin es de la respuesta de Constantin 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 puede ver, cuando se procesan valores largos utilizando grandes fragmentos realmente vale la pena, pero nada supera al código C de bajo nivel de la función incorporada de python3 (¡que extrañamente parece constantemente más rápida 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.