Problem
Schreibe n binär mit genau width Bits und fülle dazu bei Bedarf vorne mit Nullen auf. Dann liest du diese Bits rückwärts. Für n = 6 und width = 4 ist 6 binär 0110, umgekehrt wieder 0110, das Ergebnis ist also 6. Bei width = 8 erhältst du 00000110, umgekehrt 01100000, also 96. Bitumkehr kommt in der schnellen Fourier-Transformation (FFT) und bei manchen Hash-Tricks vor.
Implementiere reverse_the_bits(n, width).
Eingabe
n: Eine nicht negative ganze Zahl, die in width Bits passt.
width: Wie viele Bits umgekehrt werden.
Ausgabe
Gib den Wert des umgekehrten width-Bit-Musters zurück.
Einschränkungen
1 ≤ width ≤ 63
0 ≤ n < 2^width
Beispiele
Eingabe:
n = 6
width = 8
Erwartete Ausgabe:
expected = 96
Eingabe:
long long n = 6;
long long width = 8;
Erwartete Ausgabe:
long long expected = 96;
Eingabe:
long n = 6;
long width = 8;
Erwartete Ausgabe:
long expected = 96;
Erläuterung
6 ist mit 8 Bits 00000110, umgekehrt 01100000, und das ist 96.
Eingabe:
n = 1
width = 3
Erwartete Ausgabe:
expected = 4
Eingabe:
long long n = 1;
long long width = 3;
Erwartete Ausgabe:
long long expected = 4;
Eingabe:
long n = 1;
long width = 3;
Erwartete Ausgabe:
long expected = 4;
Erläuterung
1 ist 001, umgekehrt 100, und das ist 4.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Wiederhole width-mal: Nimm das niedrigste Bit von n und verschiebe n dann nach rechts.
Hinweis 2
Verschiebe das Ergebnis um eine Stelle nach links, bevor du das gerade entnommene Bit hinzufügst.
Hinweis 3
Führende Nullen von n werden zu Nullen am Ende des Ergebnisses. Darum kümmert sich die feste Anzahl an Schleifendurchläufen.
Erwartete Komplexität
Zeit O(width), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.