Overview
Bit-Manipulation operiert direkt auf der Binärdarstellung von Ganzzahlen mit &, |, ^, ~, <<, >>.
Analogy
Eine Reihe von Lichtschaltern (Bits): AND schaltet verschiedene Schalter ab, OR schaltet eingeschaltete an, XOR schaltet bei Unterschieden um.
Step-by-step
- AND (&): beide Bits müssen 1 sein.
- OR (|): eines der Bits muss 1 sein.
- XOR (^): Bits müssen verschieden sein; x^x=0, x^0=x.
- Shift: x<<1 multipliziert mit 2; x>>1 dividiert durch 2.
- Bit k prüfen: (x >> k) & 1. Setzen: x | (1 << k). Löschen: x & ~(1 << k).
Visual
5=0101, 3=0011: 5&3=0001=1, 5|3=0111=7, 5^3=0110=6
Common mistakes
- & (bitweise) mit and (logisch) verwechseln.
- Negative Zahlen Bitmuster unterscheidet sich zwischen Sprachen (Python hat unbegrenzte Präzision, keine feste Breite).
Practice questions
- Prüfen ob Zahl eine Zweierpotenz ist: n > 0 and (n & n-1) == 0.
- Gesetzte Bits zählen (Popcount) mit Brian Kernighans Algorithmus.
Time
O(1) pro Operation, O(log n) für Iteration über Bits