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.

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!