DSA Interview Prep · Lektion

Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen

Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Warum Bitmanipulation wichtig ist

Bitmanipulation ermöglicht es Ihnen, direkt mit der binären Darstellung von Ganzzahlen zu arbeiten. Viele Probleme, die zunächst komplex wirken, werden mit dem richtigen bitweisen Trick trivial: eine fehlende Zahl in O(n) Zeit und mit O(1) Speicher finden, Variablen ohne temporäre Variable vertauschen oder Teilmengen kompakt codieren. Interviewer verwenden solche Probleme, um das Verständnis auf niedriger Ebene und kreatives Denken zu testen.

Python-Ganzzahlen haben beliebige Genauigkeit – sie können so groß werden, wie es der Speicher zulässt –, aber Bitoperationen folgen auf Hardwareebene stets der üblichen Zweierkomplement-Semantik. Alle sechs Operatoren arbeiten Bit für Bit mit binären Darstellungen von Ganzzahlen.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

AND-Operator: Bitmaskierung

Der AND-Operator (&) gibt nur dann 1 aus, wenn beide Eingabebits 1 sind. Sein wichtigster Einsatzbereich ist die Maskierung: Dabei werden bestimmte Bits einer Zahl ausgewählt und alle übrigen auf null gesetzt. Um zu prüfen, ob Bit k in der Zahl n gesetzt ist, berechnen Sie n & (1 << k) – ist das Ergebnis ungleich null, ist Bit k gleich 1.

AND wird auch verwendet, um das niedrigstwertige gesetzte Bit zu löschen: n & (n - 1) entfernt das am weitesten rechts stehende 1-Bit. Dies wird zum effizienten Zählen gesetzter Bits und zum Prüfen verwendet, ob eine Zahl eine Zweierpotenz ist (eine Zweierpotenz hat genau ein gesetztes Bit, daher gilt n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

OR-Operator: Bits setzen

Der OR-Operator (|) gibt 1 aus, wenn mindestens eines der Eingabebits 1 ist. Sein wichtigster Einsatzbereich ist das Setzen eines bestimmten Bits auf 1, ohne andere Bits zu verändern. Um Bit k in der Zahl n zu setzen, verwenden Sie n | (1 << k). Die an Position k verschobene 1 schaltet dieses Bit ein; alle anderen Bits bleiben unverändert, weil eine Verknüpfung mit OR und 0 den Wert unverändert lässt.

OR wird auch zum Kombinieren von Flags verwendet: Wenn Sie Feature-Flags als einzelne Bits darstellen, aktivieren Sie mehrere Flags mit OR. Beispielsweise kombiniert READ | WRITE | EXECUTE drei Berechtigungsbits zu einer Ganzzahl.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

XOR-Operator: Umschalten und Unterschiede erkennen

Der XOR-Operator (^) gibt 1 aus, wenn sich die Eingabebits unterscheiden. XOR hat drei leistungsstarke algebraische Eigenschaften: a ^ a = 0 (gleiche Eingaben heben sich auf), a ^ 0 = a (null ist das neutrale Element), und XOR ist sowohl kommutativ als auch assoziativ. Aufgrund dieser Eigenschaften ist XOR das bevorzugte Werkzeug zum Finden eindeutiger Elemente.

XOR wird auch zum Umschalten eines bestimmten Bits verwendet: n ^ (1 << k) kippt Bit k um und lässt die übrigen Bits unverändert. War Bit k gleich 0, wird es zu 1; war es gleich 1, wird es zu 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

NOT-Operator und Zweierkomplement

Der NOT-Operator (~) invertiert alle Bits. In Python gilt aufgrund der Zweierkomplementdarstellung ~n = -(n+1). Das überrascht viele: ~5 = -6 und nicht das naiv erwartete 0b11111010. Python-Ganzzahlen haben unendliche Genauigkeit, daher ergibt das Invertieren aller Bits einer positiven Zahl im Zweierkomplement ein negatives Ergebnis.

In der Praxis verwenden Sie ~ in Python für Bitmanipulation selten allein. Verwenden Sie es stattdessen in Kombination mit AND, um bestimmte Bits zu löschen, oder berechnen Sie ~n & mask, wobei mask die Breite auf eine bestimmte Anzahl von Bits begrenzt (z. B. & 0xFFFFFFFF für 32 Bit).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Linksverschiebung: Multiplikation mit Zweierpotenzen

Der Linksverschiebungsoperator (<<) verschiebt alle Bits um k Positionen nach links und füllt die rechts frei gewordenen Positionen mit Nullen. Dies entspricht der Multiplikation mit 2^k. Eine Linksverschiebung um 1 verdoppelt den Wert; eine Verschiebung um k multipliziert ihn mit 2^k.

In Interviewaufgaben werden Linksverschiebungen am häufigsten zum Erstellen von Bitmasken verwendet: 1 << k erzeugt eine Zahl, bei der nur Bit k gesetzt ist. Dies bildet die Grundlage aller Bitmanipulationsoperationen – das Setzen, Löschen, Umschalten und Prüfen einzelner Bits beginnt mit 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Rechtsverschiebung: Division durch Zweierpotenzen

Der Rechtsverschiebungsoperator (>>) verschiebt alle Bits um k Positionen nach rechts und verwirft die k am weitesten rechts stehenden Bits. Dies entspricht der Ganzzahldivision durch 2^k. Die Rechtsverschiebung in Python ist immer arithmetisch: Die führenden Bits werden mit dem Vorzeichenbit aufgefüllt (0 für positive, 1 für negative Zahlen).

Ein häufiger Trick in Interviews: Um Bit k aus der Zahl n zu extrahieren, verwenden Sie (n >> k) & 1. Dadurch wird Bit k auf Position 0 verschoben und alle anderen Bits werden maskiert. Dies ist die direkteste Möglichkeit, ein bestimmtes Bit zu prüfen, ohne eine vollständige Maske berechnen und vergleichen zu müssen.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Praktischer Spickzettel für Bit-Tricks

Hier finden Sie eine Sammlung der häufigsten Bitmanipulationsmuster, die Ihnen in Interviews begegnen werden. Prägen Sie sich diese Muster ein – sie tauchen in Dutzenden von Problemen immer wieder auf:

n & 1 — prüft, ob n ungerade ist
n & (n-1) — löscht das niedrigstwertige gesetzte Bit
n & -n — isoliert das niedrigstwertige gesetzte Bit
n | (1 << k) — setzt Bit k
n & ~(1 << k) — löscht Bit k
n ^ (1 << k) — schaltet Bit k um
(n >> k) & 1 — prüft Bit k

# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Gesetzte Bits zählen (Popcount)

Das Zählen der 1-Bits einer Ganzzahl wird als Population Count (Popcount) bezeichnet. Die naive Vorgehensweise durchläuft alle Bits. Der Brian-Kernighan-Trick ist schneller: Er löscht wiederholt das niedrigstwertige gesetzte Bit mit n &= n - 1 und zählt die Iterationen, bis n gleich 0 ist. Jede Iteration entfernt genau ein 1-Bit, daher läuft die Schleife genau so oft, wie 1-Bits vorhanden sind.

Python 3.10+ stellt int.bit_count() bereit, das die Anzahl direkt zurückgibt. Für ältere Versionen ist der Kernighan-Trick die übliche manuelle Vorgehensweise. Diese Technik löst auch das Problem „Hamming Weight“ auf LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Bitmanipulation in Python: Wichtige Fallstricke

Im Gegensatz zu C/Java sind Python-Ganzzahlen beliebig groß – es gibt keinen Überlauf bei 32 oder 64 Bit. Daher müssen Sie Ergebnisse manuell auf eine feste Breite maskieren, wenn Probleme ein 32-Bit-Verhalten erwarten: Verwenden Sie & 0xFFFFFFFF, um nur die unteren 32 Bits beizubehalten.

Der NOT-Operator ~n in Python gibt -(n+1) zurück und nicht die bitweise invertierte Version, die Sie aus C erwarten würden. Verwenden Sie bei 32-Bit-Problemen ~n & 0xFFFFFFFF oder berechnen Sie 0xFFFFFFFF ^ n, um das erwartete 32-Bit-Komplement zu erhalten. Diese Unterschiede bringen viele Kandidaten durcheinander, die an Bitmanipulation im C-Stil gewöhnt sind.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Verschiebungsoperatoren und Multiplikation

Links- und Rechtsverschiebungen ermöglichen eine äußerst schnelle Multiplikation oder Division durch Zweierpotenzen. Auf Hardwareebene sind Bitverschiebungen Operationen mit einer einzigen Maschineninstruktion, während Multiplikation und Division mehrere Taktzyklen benötigen. In Python ist die Ganzzahlmultiplikation bereits effizient, aber das Verständnis dieses Zusammenhangs hilft Ihnen, Bitmuster klarer zu erkennen.

Eine nützliche Identität: Um zu prüfen, ob n ein Vielfaches von 2^k ist, verwenden Sie (n & (2^k - 1)) == 0. Die Maske 2^k - 1 hat alle unteren k Bits auf 1 gesetzt; eine AND-Verknüpfung damit liefert den Rest bei der Division durch 2^k. Dies entspricht n % (2^k), ist aber in C-basierten Sprachen schneller.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

Lektionszusammenfassung

In dieser Lektion haben Sie gelernt: AND maskiert Bits, OR setzt Bits, XOR schaltet Bits um und erkennt Unterschiede, NOT invertiert (ergibt -(n+1) in Python), und Verschiebungen multiplizieren/dividieren mit Zweierpotenzen, n & (n-1) löscht das niedrigstwertige gesetzte Bit und bildet die Grundlage für Prüfungen auf Zweierpotenzen und das Zählen von Bits und Python hat keinen Überlauf bei fester Bitbreite, daher erfordern 32-Bit-Probleme eine explizite Maskierung mit & 0xFFFFFFFF. Als Nächstes untersuchen wir die Selbstinvers-Eigenschaft von XOR, um die Problemfamilie rund um die einzelne Zahl zu lösen.

Häufig gestellte Fragen

Ist die Lektion „Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen“ kostenlos?

Ja — der vollständige Text von „Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen“?

Wiederholen Sie alle sechs bitweisen Operatoren anhand von Wahrheitstabellen und Python-Beispielen und verstehen Sie, wie Links- und Rechtsschiebungen mit Multiplikation und Division durch zwei zusam… Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen
Single Number und XOR-Eigenschaften
Bitmasken: Setzen, Löschen, Umschalten und Prüfen
Bits zählen, fehlende Zahl und Bits umkehren

← Zurück zu DSA Interview Prep