Invertir el orden de los bits
La misión
Problema
Trata un número entero no negativo como un campo fijo de 32 dígitos binarios, rellenado con ceros a la izquierda. Devuelve el valor que obtienes al invertir el orden de esos 32 dígitos, de modo que el dígito más bajo pase a ser el más alto y viceversa. El ancho siempre es 32, sea cual sea el tamaño de la entrada.
Ejemplos
Input: value = 1
Output: 2147483648
Por qué: el único dígito bajo sube hasta lo más alto del campo
Input: value = 3
Output: 3221225472
Por qué: los dos dígitos bajos pasan a ser los dos más altos
Input: value = 0
Output: 0
Por qué: caso límite: un campo de ceros se lee igual en ambas direcciones
Pistas
0 / 3
Convertir el número en texto, invertir el texto y volver a leerlo funciona, pero la idea aquí es hacerlo con aritmética sobre el propio número.
Construye la respuesta dígito por dígito. Leer la entrada desde su dígito más bajo hacia arriba da exactamente el orden en que la respuesta necesita ir agregando sus dígitos.
Repite 32 veces: haz espacio en el resultado desplazándolo una posición hacia arriba, copia el dígito más bajo de la entrada en ese espacio y luego desplaza la entrada una posición hacia abajo. Hacer exactamente 32 rondas es lo que fija el ancho del campo.
- Tiempo objetivo
- O(1)
- Espacio objetivo
- O(1)
Restricciones
- value is a non-negative integer read as 32 bits
Solución
Leer la entrada de abajo hacia arriba y escribir el resultado de abajo hacia arriba produce la inversión sin costo extra, porque los desplazamientos posteriores empujan el primer dígito leído hasta lo más a la izquierda. Cada ronda desplaza el resultado hacia arriba para abrir un hueco, copia en él el dígito más bajo de la entrada con una máscara y un OR, y luego descarta ese dígito de la entrada. Hacer exactamente 32 rondas es lo que rellena un número pequeño hasta el ancho completo del campo en lugar de detenerse antes. El tiempo es O(32), que es constante, y el espacio es O(1).
def reverse_bits(value):
result = 0
for _ in range(32): # a fixed width, whatever the input size
result = (result << 1) | (value & 1) # open a slot, copy the low digit
value >>= 1 # drop the digit just consumed
return result
print(reverse_bits(1)) # -> 2147483648
print(reverse_bits(3)) # -> 3221225472
print(reverse_bits(0)) # -> 0¿Lo que te frena es la idea y no el código? Binario y operaciones a nivel de bits lo explica.