LeetCode-Meditationen: Umkehrbits

Die Beschreibung für Reverse Bits ist sehr kurz:

Bits einer gegebenen 32-Bit-Ganzzahl ohne Vorzeichen umkehren.

Es gibt auch einen Hinweis:

• Beachten Sie, dass es in einigen Sprachen, wie z. B. Java, keinen vorzeichenlosen Ganzzahltyp gibt. In diesem Fall werden sowohl Eingabe als auch Ausgabe als vorzeichenbehafteter Ganzzahltyp angegeben. Sie sollten sich nicht auf Ihre Implementierung auswirken, da die interne Binärdarstellung der Ganzzahl dieselbe ist, unabhängig davon, ob sie vorzeichenbehaftet oder ohne Vorzeichen ist.

• In Java stellt der Compiler die vorzeichenbehafteten Ganzzahlen mithilfe der 2er-Komplement-Notation dar. Daher stellt in Beispiel 2 die Eingabe die vorzeichenbehaftete Ganzzahl -3 und die Ausgabe die vorzeichenbehaftete Ganzzahl -1073741825 dar.

Zum Beispiel:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Oder:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Es wird außerdem angegeben, dass die Eingabe eine Binärzeichenfolge der Länge 32 in den Einschränkungen sein muss.

---

Da wir wissen, dass die Eingabe eine 32-Bit-Ganzzahl ist, können wir die umgekehrte Position jedes Bits leicht berechnen. Beispielsweise entspricht der 0. dem 31., der 1. dem 30. und so weiter.

Aber wir betreiben Bit-Manipulation, was bedeutet, dass wir jedes Bit einzeln bearbeiten müssen.
Wir können also eine for-Schleife ausführen, um genau das zu tun. Jedes Mal können wir das Bit um den Index an die Position ganz rechts verschieben, was so aussehen kann:

n >>> idx

Ein Bit (egal ob 0 oder 1) zu erhalten, kann einfach durch eine UND-Verknüpfung mit 1 erfolgen.
Wenn das Bit 0 ist, ergeben 0 und 1 0.
Wenn es 1 ist, ergibt 1 & 1 1.

Hinweis Wir können uns

Note

We can think of ANDing with 1 as the multiplicative identity (for example, $7\cdot 1=7$7⋅1=7 ).

AND-Verknüpfung mit 1 als multiplikative Identität vorstellen (zum Beispiel $7\cdot 1=7$7⋅1=7 ).

Zuerst können wir das Bit bekommen:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Dann müssen wir das Bit, das wir haben, in die umgekehrte Position bringen. Dazu können wir das Bit nach links verschieben und dabei das Ergebnis erhöhen:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Wir müssen das Ergebnis als 32-Bit-Ganzzahl zurückgeben. Dazu können wir einen Trick anwenden, indem wir den vorzeichenlosen Rechtsverschiebungsoperator verwenden:

n >>> idx

Und die endgültige Lösung sieht so aus:

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

Zeit- und Raumkomplexität

Wir wissen, dass die Eingabe und unser Ergebnis immer 32-Bit-Ganzzahlen sind (und wir müssen keine andere zusätzliche Datenstruktur verwenden). Wir führen auch 32 Mal eine Schleife aus, was eine feste Zahl ist Sowohl die zeitliche als auch die räumliche Komplexität sind groß $O(1)$O(1) .

---

Als nächstes werfen wir einen Blick auf die fehlende Nummer. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Umkehrbits. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!