Todos os desafios
Médio 0 resolvidos 0% de aceitação

Inverter os bits

Inverta a ordem dos width bits menos significativos de um número.

O que você vai aprender

  • Ler o bit menos significativo com AND 1
  • Montar um número bit a bit com deslocamentos
  • Respeitar uma largura fixa de bits

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.