Problema
Escreva n em binário usando exatamente width bits, completando com zeros à esquerda se precisar, e depois leia esses bits de trás para frente. Para n = 6 e width = 4, 6 é 0110, que invertido continua 0110, então o resultado é 6. Com width = 8 fica 00000110, que invertido é 01100000, ou seja, 96. A inversão de bits é usada na transformada rápida de Fourier e em alguns truques de hashing.
Implemente reverse_the_bits(n, width).
Entrada
n: um inteiro não negativo que cabe em width bits.
width: quantos bits devem ser invertidos.
Saída
Retorne o valor do padrão de width bits invertido.
Restrições
1 ≤ width ≤ 63
0 ≤ n < 2^width
Exemplos
Entrada:
n = 6
width = 8
Saída esperada:
expected = 96
Entrada:
long long n = 6;
long long width = 8;
Saída esperada:
long long expected = 96;
Entrada:
long n = 6;
long width = 8;
Saída esperada:
long expected = 96;
Explicação
Em 8 bits, 6 é 00000110; invertido fica 01100000, que vale 96.
Entrada:
n = 1
width = 3
Saída esperada:
expected = 4
Entrada:
long long n = 1;
long long width = 3;
Saída esperada:
long long expected = 4;
Entrada:
long n = 1;
long width = 3;
Saída esperada:
long expected = 4;
Explicação
1 é 001; invertido fica 100, que vale 4.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Repita width vezes: pegue o bit menos significativo de n e depois desloque n para a direita.
Dica 2
Desloque o resultado uma posição para a esquerda antes de somar o bit que você acabou de pegar.
Dica 3
Os zeros à esquerda de n viram zeros à direita do resultado, e o número fixo de repetições do laço cuida disso.
Complexidade esperada
tempo O(width), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.