La lógica del programa para invertir los bits no está clara.
Me pidieron que escribiera un programa para invertir los bits de un entero sin signo de 32 bits dado.
Por ejemplo, si la entrada es 43261596, la salida debería ser 964176192 (el binario de la entrada es 00000010100101000001111010011100, y después de invertir la salida se convierte en 00111001011110000010100101000000 cuyo equivalente decimal es 964176192).
Escribí el siguiente programa:
class Solution:
def reverseBits(self, n: int) -> int:
binary = ""
for i in range(32):
binary = binary + str(n%2)
n = n//2
return int(binary,2)
Al enviarlo, se recibió una respuesta con una solución alternativa que se afirmaba ser más eficiente en tiempo y espacio. Aquí está la alternativa:
class Solution:
def reverseBits(self, n: int) -> int:
if (n == 0):
return 0
result = 0
for i in range(32):
result <<= 1
if ((n & 1) == 1):
result +=1
n >>= 1
return result
La lógica que proporcionaron fue el desplazamiento de bits hacia la izquierda/derecha.
Estoy completamente perdido en cuanto a cómo el desplazamiento de bits hacia la izquierda/derecha ayuda a invertir los bits de un entero decimal. Para aclarar aún más, escribí esta sección de código:
a = 9
print(a>>1,a<<1)
Las salidas fueron 4 y 18, respectivamente (la mitad y el doble del entero).
¿Pero cómo contribuye este concepto a la inversión de los bits de un entero? ¿Y por qué se considera más eficiente en tiempo y espacio que mi solución? Por favor ayúdeme.
davy.ai
El desplazamiento de bits es una forma de multiplicar o dividir rápidamente un número por dos. En el ejemplo que proporcionó,
a >> 1es lo mismo quea / 2ya << 1es lo mismo quea * 2.En la solución alternativa, el desplazamiento de bits se utiliza para invertir los bits del número. La idea es comenzar con el bit menos significativo (LSB) del número y moverlo al bit más significativo (MSB) del resultado. Para hacer esto, se comprueba el LSB del número y si es 1, se incrementa el resultado en 1. Luego, el número se desplaza hacia la derecha en 1 bit y el proceso se repite hasta que se hayan procesado todos los bits del número.
Esta solución es más eficiente en tiempo y espacio que su solución porque no requiere la conversión del número a una cadena binaria y luego de vuelta a un número entero. Tampoco requiere el uso de un bucle, lo que la hace más rápida.