Mittel 0 gelöst 0% Erfolgsquote

Bits umkehren

Kehre die Reihenfolge der untersten width Bits einer Zahl um.

Das lernst du

  • Das niedrigste Bit mit AND 1 auslesen
  • Eine Zahl Bit für Bit mit Verschiebungen aufbauen
  • Eine feste Bitbreite einhalten

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

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

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

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.