Was sind häufige Bit-Manipulations-Tricks?

Question

Accepted Answer

**Bit-Manipulation** arbeitet direkt mit der binären Darstellung von Ganzzahlen unter Verwendung von AND, OR, XOR, NOT und Shifts. Sie ermöglicht kompakte, verzweigungsfreie und sehr schnelle Operationen. ## Kerneoperationen ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Nützliche Tricks ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## Beispiel: Eine einzelne Zahl finden (XOR-Trick) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Komplexität Bit-Operationen sind O(1); der XOR-Scan oben ist **O(n) Zeit, O(1) Raum**. ## Wann zu verwenden / Fallstricke Verwendet für **Bitmasks** (Teilmenge-Enumeration, DP über Zustände), Flags, schnelle Mathematik und Low-Level-/Embedded-Code. Vorsicht vor Vorzeichenbits, sprachspezifischem Shift-Verhalten und Lesbarkeit — kommentiert nicht offensichtliche Tricks. ## Warum es wichtig ist Bit-Manipulation ergibt elegante O(1)-Raum-Lösungen (wie der XOR-Single-Number-Trick), die in Interviews beeindrucken. Bitmask DP macht viele kombinatorische Zustandsraum-Probleme lösbar. Es ist wesentlich in Systemen, Grafik, Kompression und leistungskritischem Code, wo jeder Zyklus zählt.