Problema
Scrivi n in binario usando esattamente width bit, aggiungendo zeri iniziali se serve, poi leggi quei bit al contrario. Per n = 6 e width = 4, 6 è 0110, che al contrario è di nuovo 0110, quindi il risultato è 6. Con width = 8 diventa 00000110, al contrario 01100000, cioè 96. L'inversione dei bit si usa nella trasformata di Fourier veloce (FFT) e in alcuni trucchi di hashing.
Implementa reverse_the_bits(n, width).
Input
n: un intero non negativo rappresentabile con width bit.
width: quanti bit invertire.
Output
Restituisci il valore della sequenza di width bit invertita.
Vincoli
1 ≤ width ≤ 63
0 ≤ n < 2^width
Esempi
Input:
n = 6
width = 8
Output atteso:
expected = 96
Input:
long long n = 6;
long long width = 8;
Output atteso:
long long expected = 96;
Input:
long n = 6;
long width = 8;
Output atteso:
long expected = 96;
Spiegazione
Su 8 bit 6 è 00000110; al contrario diventa 01100000, cioè 96.
Input:
n = 1
width = 3
Output atteso:
expected = 4
Input:
long long n = 1;
long long width = 3;
Output atteso:
long long expected = 4;
Input:
long n = 1;
long width = 3;
Output atteso:
long expected = 4;
Spiegazione
1 è 001; al contrario è 100, cioè 4.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ripeti width volte: prendi il bit meno significativo di n, poi sposta n a destra di un bit.
Suggerimento 2
Sposta il risultato a sinistra di un bit prima di aggiungere il bit appena preso.
Suggerimento 3
Gli zeri iniziali di n diventano zeri finali del risultato, e il numero fisso di iterazioni se ne occupa da solo.
Complessità attesa
tempo O(width), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.