Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Invertir los bits

Invierte el orden de los width bits menos significativos de un número.

Lo que aprenderás

  • Leer el bit menos significativo con AND 1
  • Construir un número bit a bit con desplazamientos
  • Respetar un ancho de bits fijo

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.