Tutte le sfide
Media 0 risolte 0% di accettazione

Invertire i bit

Inverti l'ordine dei width bit meno significativi di un numero.

Cosa imparerai

  • Leggere il bit meno significativo con AND 1
  • Costruire un numero bit per bit con gli shift
  • Rispettare una larghezza in bit fissata

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

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

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

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.