Inversión de bits del número entero de Python

Question

Dado un número entero decimal (por ejemplo, 65), ¿cómo se invierten los bits subyacentes en Python? es decir. la siguiente operación:

65 → 01000001 → 10000010 → 130 

Parece que esta tarea se puede dividir en tres etapas:

1. convertir el entero decimal a la representación binaria
2. Invertir los bits
3. convertir de nuevo a decimal

Los pasos # 2 y 3 parecen bastante sencillos (consulte this y this AS pregunta relacionada con el paso # 2), pero estoy atascado en el paso # 1. El problema con el paso n. ° 1 es recuperar la representación decimal completa con ceros de relleno (es decir, 65 = 01000001, no 1000001).

He buscado, pero parece que no encuentro nada.

Answer 1

int('{:08b}'.format(n)[::-1], 2) 

Puede especificar cualquier longitud de relleno en lugar del 8. Si desea obtener realmente de lujo,

b = '{:0{width}b}'.format(n, width=width) 
int(b[::-1], 2) 

le permite especificar el ancho de forma programática.

Answer 2

No es necesario ni imposible "convertir un número entero decimal en representación binaria". Todos los enteros de Python se representan como binarios; solo se convierten a decimal cuando los imprime por conveniencia.

Si quiere seguir this solution al problema de inversión, solo necesita encontrar numbits apropiado. Puede especificar esto a mano o calcular el número de bits necesarios para representar un número entero n con n.bit_length().

Sin embargo, para 65, eso le daría 7, ya que no hay razón para que 65 requiera más bits. (Es posible que desee redondear al múltiplo más cercano de 8 ...)

Answer 3

Si usted está después de más velocidad, se puede utilizar la técnica descrita en http://leetcode.com/2011/08/reverse-bits.html

def reverse_mask(x): 
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1) 
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2) 
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4) 
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8) 
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16) 
    return x 

Answer 4

Puede probar el bit i-ésima de un número mediante un cambio y la máscara. Por ejemplo, el bit 6 de 65 es (65 >> 6) & 1. Puede establecer un bit de forma similar cambiando 1 a la izquierda el número de veces correcto. Estas ideas le dan un código como este (que invierte x en un campo de 'n' bits).

def reverse(x, n): 
    result = 0 
    for i in xrange(n): 
     if (x >> i) & 1: result |= 1 << (n - 1 - i) 
    return result 

print bin(reverse(65, 8)) 

Answer 5

def reverse_bit(num): 
    result = 0 
    while num: 
     result = (result << 1) + (num & 1) 
     num >>= 1 
    return result 

Realmente no es necesario convertir el número entero a binario, ya que en realidad son números enteros binarios en Python.

La idea de invertir es como hacer la inversión de enteros en el espacio.

def reverse_int(x): 
    result = 0 
    pos_x = abs(x) 
    while pos_x: 
     result = result * 10 + pos_x % 10 
     pos_x /= 10 
    return result if x >= 0 else (-1) * result 

Para cada bucle, el número original está soltando el bit de la derecha (en binario). Obtenemos el bit más a la derecha y multiplicamos 2 (<<1) en el siguiente ciclo cuando se agrega el nuevo bit.