Problema
Escribe n en binario usando exactamente width bits, con los ceros a la izquierda que hagan falta, y luego lee esos bits al revés. Para n = 6 y width = 4, 6 es 0110, que invertido vuelve a ser 0110, así que el resultado es 6. Con width = 8 queda 00000110, que invertido es 01100000, es decir, 96. La inversión de bits se usa en la transformada rápida de Fourier y en algunos trucos de hashing.
Implementa reverse_the_bits(n, width).
Entrada
n: un entero no negativo que cabe en width bits.
width: cuántos bits hay que invertir.
Salida
Devuelve el valor del patrón invertido de width bits.
Restricciones
1 ≤ width ≤ 63
0 ≤ n < 2^width
Ejemplos
Entrada:
n = 6
width = 8
Salida esperada:
expected = 96
Entrada:
long long n = 6;
long long width = 8;
Salida esperada:
long long expected = 96;
Entrada:
long n = 6;
long width = 8;
Salida esperada:
long expected = 96;
Explicación
6 es 00000110 en 8 bits; invertido queda 01100000, que vale 96.
Entrada:
n = 1
width = 3
Salida esperada:
expected = 4
Entrada:
long long n = 1;
long long width = 3;
Salida esperada:
long long expected = 4;
Entrada:
long n = 1;
long width = 3;
Salida esperada:
long expected = 4;
Explicación
1 es 001; invertido queda 100, que vale 4.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Repite width veces: toma el bit menos significativo de n y luego desplaza n a la derecha.
Pista 2
Desplaza el resultado una posición a la izquierda antes de añadirle el bit que acabas de tomar.
Pista 3
Los ceros a la izquierda de n se convierten en ceros a la derecha del resultado, y eso lo resuelve el número fijo de iteraciones.
Complejidad esperada
tiempo O(width), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.