LeetCode-Meditationen – Kapitel Bit-Manipulation

Inhaltsverzeichnis

• Einführung
• Bitweise Operatoren
  • UND (&)
  • ODER (|)
  • XOR (^)
  • NICHT (~)
  • Linksverschiebung (Nullfüllung) (<<)
  • Rechtsverschiebung (zeichenerhaltend) (>>)
  • Rechtsverschiebung (ohne Vorzeichen) (>>>)
• Ein bisschen langsam
• Ein bisschen einstellen
• Ressourcen

Wir sind im letzten Kapitel dieser Serie und es ist endlich Zeit, einen kurzen Blick auf die Bit-Manipulation zu werfen.

Wie Wikipedia es definiert, bearbeitet eine bitweise Operation eine Bitfolge, ein Bitarray oder eine Binärzahl (als Bitfolge betrachtet) auf der Ebene ihrer einzelnen Bits.

---

Stellen wir zunächst eine Zahl binär dar (Basis 2). Wir können die toString-Methode für eine Zahl verwenden und die Basis:
angeben

const n = 17;

console.log(n.toString(2)); // 10001

Wir können auch eine Ganzzahl analysieren und ihr eine Basis geben:

console.log(parseInt(10001, 2)); // 17

Beachten Sie, dass wir eine Binärzahl auch mit dem Präfix 0b darstellen können:

console.log(0b10001); // 17
console.log(0b101); // 5

Zum Beispiel sind dies die gleichen Nummern:

0b1 === 0b00000001 // true

---

Alle bitweisen Operationen werden an 32-Bit-Binärzahlen in JavaScript ausgeführt.
Das heißt, bevor eine bitweise Operation ausgeführt wird, konvertiert JavaScript Zahlen in 32-Bit-Ganzzahlen mit **Vorzeichen*.*

So ist beispielsweise 17 nicht einfach 10001, sondern 00000000 00000000 00000000 00010001.

Nachdem die bitweise Operation ausgeführt wurde, wird das Ergebnis zurück in 64-Bit-JavaScript-Zahlen konvertiert.

Bitweise Operatoren

UND (&)

Wenn zwei Bits 1 sind, ist das Ergebnis 1, andernfalls 0.

Note

The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const n = 17;

console.log(n.toString(2)); // 10001

ODER (|)

Wenn eines der Bits 1 ist, ist das Ergebnis 1, andernfalls 0.

console.log(parseInt(10001, 2)); // 17

XOR (^)

Wenn die Bits unterschiedlich sind (eines ist 1 und das andere ist 0), ist das Ergebnis 1, andernfalls 0.

console.log(0b10001); // 17
console.log(0b101); // 5

NICHT (~)

Dreht die Bits um (1 wird zu 0, 0 wird zu 1).

0b1 === 0b00000001 // true

Note

Bitwise NOTing any 32-bit integer x yields -(x 1).

Wenn wir eine Hilfsfunktion verwenden, um die binären Darstellungen anzuzeigen, ist es wie erwartet:

const n = 17;

console.log(n.toString(2)); // 10001

Das Bit ganz links gibt das Signal an – ob die Zahl negativ oder positiv ist.

Denken Sie daran, dass wir gesagt haben, dass JavaScript 32-Bit-vorzeichenbehaftete Ganzzahlen für bitweise Operationen verwendet.
Das Bit ganz links ist 1 für negative Zahlen und 0 für positive Zahlen.
Außerdem der Operator bearbeitet die Bitdarstellungen der Operanden im Zweierkomplement. Der Operator wird auf jedes Bit angewendet und das Ergebnis wird bitweise erstellt.

Beachten Sie, dass das Zweierkomplement es uns ermöglicht, eine Zahl mit einem inversen Signal zu erhalten.
Eine Möglichkeit besteht darin, die Bits der Zahl in der positiven Darstellung umzukehren und 1 hinzuzufügen:

console.log(parseInt(10001, 2)); // 17

Linksverschiebung (Nullfüllung) (<<)

Schiebt die angegebene Anzahl von Bits nach links und fügt null von rechts nach innen verschobene Bits hinzu.

console.log(0b10001); // 17
console.log(0b101); // 5

Beachten Sie, dass das 32. Bit (das ganz linke) verworfen wird.

Rechtsverschiebung (zeichenerhaltend) (>>)

Verschiebt die angegebene Anzahl von Bits nach rechts und behält das Vorzeichen bei, wenn Bits von links hinzugefügt werden.

0b1 === 0b00000001 // true

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

Rechtsverschiebung (ohne Vorzeichen) (>>>)

Verschiebt die angegebene Anzahl von Bits nach rechts und fügt Nullen hinzu, wenn Bits von links hinzugefügt werden, unabhängig vom Vorzeichen.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

---

Immer ein bisschen

Um ein bestimmtes Bit zu erhalten, müssen wir zunächst eine Bitmaske erstellen.
Wir können dies tun, indem wir 1 um den Index des Bits, das wir erhalten möchten, nach links verschieben.
Das Ergebnis ist das und der Binärzahl und der Bitmaske.

Mit JavaScript können wir jedoch auch eine vorzeichenlose Rechtsverschiebung durch den Index durchführen, um das Bit an die erste Stelle zu setzen (so dass wir nicht den tatsächlichen Wert erhalten, der sich an dieser Position befindet, sondern ob es eine 1 ist oder eine 0):

const n = 17;

const result = ~n; // -18

Versuchen wir zum Beispiel 13, was im Binärformat 1101 ist:

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

Etwas einstellen

Wenn wir ein Bit auf 1 stellen wollen (mit anderen Worten: „ein Bit setzen“), können wir etwas Ähnliches tun.

Zuerst können wir erneut eine Bitmaske erstellen, indem wir 1 um den Index des Bits, das wir auf 1 setzen möchten, nach links verschieben.
Das Ergebnis ist das oder der Zahl und der Bitmaske:

function twosComplement(n) {
  return ~n + 0b1;
}

Denken Sie daran, dass in unserem Beispiel 13 binär 1101 war. Nehmen wir an, wir möchten die 0 an Index 1 setzen:

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

---

Wir haben uns kurz die bitweisen Operationen sowie das Abrufen/Festlegen eines Bits angesehen. In diesem letzten Kapitel werfen wir einen Blick auf fünf Probleme, beginnend mit der Anzahl der 1-Bits. Bis dahin viel Spaß beim Codieren.

Ressourcen

• „Die absoluten Grundlagen für die Bitmanipulation in JavaScript“ – Lucas F. Costa
• Bitweise JS-Operatoren
• Nummer (MDN)
• Bitweises UND (MDN)
• Bitweise NICHT (MDN)
• Bitweises ODER (MDN)
• Bitweises XOR (MDN)
• Linksverschiebung (MDN)
• Rechtsverschiebung (MDN)
• Vorzeichenlose Rechtsverschiebung (MDN)

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