Inverter a ordem dos bits
A missão
Problema
Trate um número inteiro não negativo como um campo fixo de 32 dígitos binários, preenchido com zeros à esquerda. Retorne o valor obtido ao inverter a ordem desses 32 dígitos, de modo que o dígito mais baixo vire o mais alto e vice-versa. A largura é sempre 32, qualquer que seja o tamanho da entrada.
Exemplos
Input: value = 1
Output: 2147483648
Por quê: o único dígito baixo vai até o topo do campo
Input: value = 3
Output: 3221225472
Por quê: os dois dígitos mais baixos viram os dois mais altos
Input: value = 0
Output: 0
Por quê: edge case: um campo de zeros é igual lido em qualquer direção
Dicas
0 / 3
Transformar o número em texto, inverter o texto e lê-lo de volta funciona, mas a graça aqui é fazer isso com aritmética sobre o próprio número.
Monte a resposta dígito a dígito. Ler a entrada a partir do dígito mais baixo, subindo, produz exatamente a ordem em que a resposta precisa receber os seus dígitos.
Repita 32 vezes: abra espaço no resultado deslocando-o uma posição para cima, copie o dígito mais baixo da entrada para esse espaço e depois desloque a entrada uma posição para baixo. São exatamente as 32 rodadas que fixam a largura do campo.
- Tempo-alvo
- O(1)
- Espaço-alvo
- O(1)
Restrições
- value is a non-negative integer read as 32 bits
Solução
Ler a entrada de baixo para cima e escrever o resultado de baixo para cima produz a inversão sem custo extra, porque o primeiro dígito lido acaba empurrado para o ponto mais à esquerda pelos deslocamentos de bits (shift) seguintes. Cada rodada desloca o resultado para cima para abrir uma posição, copia para ela o dígito mais baixo da entrada com uma máscara e um OR e depois descarta esse dígito da entrada. Rodar exatamente 32 rodadas é o que completa um número pequeno até a largura total do campo, em vez de parar antes. O tempo é O(32), que é constante, e o espaço é 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)) # -> 0Travou na ideia, e não no código? Binário e operações bit a bit explica isso.