Veröffentlicht · wird verbessert
Algorithm
Bitmanipulation behandelt Ganzzahlen als Binärziffern und nutzt AND, OR, XOR und Shifts, um Mengen, Flags und Bitmasken-DP schnell und kompakt abzubilden.
Bei der Bitmanipulation betrachtet man eine Ganzzahl als Folge von Nullen und Einsen und liest, setzt, löscht oder kippt einzelne Bits mit AND, OR, XOR, NOT und Shifts. Computer speichern Ganzzahlen binär und negative Zahlen im Zweierkomplement, deshalb entspricht jede dieser Operationen meist einem einzigen CPU-Befehl. Ein kurzer Ausdruck wie x & -x (das niedrigste gesetzte Bit) oder x & (x - 1) (dieses Bit gelöscht) ersetzt oft eine ganze Schleife.
Wichtig ist das Thema, weil eine einzige Ganzzahl eine Menge von etwa 20 Elementen darstellen kann. So lassen sich alle Teilmengen durchlaufen und Mengen als Zustände in dynamischer Programmierung mit Bitmasken verwenden. In Coding-Interviews tauchen Teilmengen-Aufzählung, XOR-Eigenschaften und Popcount regelmäßig auf, und in der Praxis stecken Bits in Dateirechten, Feature-Flags, Subnetzberechnungen, Hashtabellen und Bitmap-Indizes. Die Regeln unterscheiden sich allerdings je nach Sprache: Python-Ganzzahlen sind unbegrenzt, JavaScript rechnet mit 32 Bit und kennt >>>, Java ebenfalls >>>, und in C++ sind vorzeichenlose Typen für Masken die sichere Wahl.
Am besten beginnt man damit, Zahlen von Hand ins Binärsystem und ins Zweierkomplement umzurechnen. Danach übt man die vier Einzelbit-Operationen (setzen, löschen, kippen, prüfen) und gibt alle Teilmengen aus, indem man eine Maske von 0 bis 2^n - 1 laufen lässt. Anschließend folgen Teilmasken-Aufzählung und Bitmasken-DP wie das Zuordnungsproblem oder das Problem des Handlungsreisenden, und zuletzt prüft man Ganzzahlbreite und Shift-Regeln der eigenen Sprachen.
Negative Zahlen entstehen, indem man alle Bits kippt und 1 addiert. Linksshift multipliziert mit 2, Rechtsshift teilt durch 2, wobei Sprachen arithmetische und logische Rechtsshifts unterscheiden.
Mit der Maske 1 << i setzt OR das Bit i, AND NOT löscht es und XOR kippt es. x & -x isoliert das niedrigste gesetzte Bit, x & (x - 1) entfernt es.
Die Teilmengen von n Elementen entsprechen eins zu eins den Zahlen 0 bis 2^n - 1; Vereinigung, Schnitt und Differenz kosten jeweils nur eine Bitoperation.
Gesetzte Bits zählt man durch wiederholtes x &= x - 1 oder mit einer eingebauten Funktion. Wegen a ^ a = 0 findet XOR den Wert ohne Partner und liefert Hamming-Abstände und Gray-Codes.
popcount zählt die gesetzten Bits, indem es mit x &= x - 1 so lange das niedrigste Bit löscht, bis nichts mehr übrig ist. subsets lässt eine Maske von 0 bis 2^n - 1 laufen und wählt die Elemente, deren Bit gesetzt ist, sodass jede Teilmenge entsteht. Die letzte Zeile zeigt 12 & -12 = 4 (niedrigstes gesetztes Bit), 12 & 11 = 8 (dieses Bit gelöscht) und x ^ x = 0. Ausgeführt wird das Programm mit python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Bitmanipulation.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Bitmanipulation aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.