Bitmasken: Setzen, Löschen, Umschalten und Prüfen
Implementieren Sie Hilfsfunktionen zum Setzen, Löschen, Umschalten und Prüfen einzelner Bits und verwenden Sie Bitmasken, um Teilmengen in Problemen zur Teilmengenerzeugung darzustellen.
Bitmasken: Setzen, Löschen, Umschalten und Prüfen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was sind Bitmasken?
Eine Bitmaske ist eine Ganzzahl, mit der bestimmte Bits in einer anderen Ganzzahl ausgewählt, verändert oder geprüft werden. Die Maske enthält an den relevanten Positionen Einsen und an allen anderen Positionen Nullen. In Kombination mit bitweisen Operatoren ermöglichen Masken präzise Bitoperationen, ohne andere Bits zu beeinflussen.
Die vier grundlegenden Operationen mit Masken sind: Setzen (ein Bit einschalten), Löschen (ein Bit ausschalten), Umschalten (ein Bit invertieren) und Prüfen (testen, ob ein Bit 1 ist). Jede verwendet einen anderen Operator – OR, AND-NOT, XOR beziehungsweise AND – mit der Maske 1 << k.
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')Bit setzen: Ein Bit einschalten
Um Bit k zu setzen (es unabhängig von seinem aktuellen Wert auf 1 zu setzen), verknüpfen Sie die Zahl per OR mit der Maske 1 << k. Da 0 OR 1 = 1 und 1 OR 1 = 1 gilt, wird das Zielbit zu 1. Alle anderen Bits werden mit 0 per OR verknüpft und bleiben dadurch unverändert.
Das Setzen eines Bits ist idempotent – mehrmaliges Aufrufen hat denselben Effekt wie ein einmaliger Aufruf. Wenn Bit k bereits 1 ist, bleibt das Ergebnis unverändert. Diese Eigenschaft ist bei der Verwaltung von Flags wichtig, wenn Sie eine Funktion aktivieren möchten, ohne ihren aktuellen Zustand berücksichtigen zu müssen.
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')Bit löschen: Ein Bit ausschalten
Um Bit k zu löschen (es unabhängig von seinem aktuellen Wert auf 0 zu setzen), verknüpfen Sie die Zahl per AND mit dem Komplement der Maske: n & ~(1 << k). Das Komplement ~(1 << k) enthält an allen Bitpositionen eine 1, außer an Position k, an der eine 0 steht. Eine Verknüpfung per AND mit 0 setzt das Zielbit auf 0; eine Verknüpfung per AND mit 1 bewahrt alle anderen Bits.
Wie das Setzen ist auch das Löschen idempotent. Das Löschen eines Bits, das bereits 0 ist, lässt die Zahl unverändert. In Python funktioniert ~(1 << k) für jedes k korrekt, weil Python die Vorzeichenerweiterung automatisch verarbeitet – konzeptionell sind alle höherwertigen Bits des Komplements auf 1 gesetzt.
def clear_bit(n, k):
mask = ~(1 << k) # all 1s except bit k
return n & mask
n = 0b11111111 # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = clear_bit(n, k)
print(f'Clear bit {k}: {bin(result)} = {result}')
# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
mask = 0
for k in positions:
mask |= (1 << k)
return n & ~mask
result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}') # 0b01010101 = 85Bit umschalten: Ein Bit invertieren
Um Bit k umzuschalten (es von 0 auf 1 oder von 1 auf 0 zu ändern), verknüpfen Sie die Zahl per XOR mit der Maske 1 << k. XOR mit 1 invertiert das Bit; XOR mit 0 lässt es unverändert. Dies ist die grundlegende Eigenschaft von XOR, angewendet auf ein einzelnes Bit.
Das Umschalten ist die einzige der vier Operationen, die nicht idempotent ist – zweimaliges Aufrufen führt zum ursprünglichen Wert zurück. Dadurch eignet es sich besonders für Funktionen, die zwischen zwei Zuständen wechseln, etwa einen Ein-/Ausschalter oder ein boolesches Flag in einer kompakten Ganzzahldarstellung.
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b10101010 # 170
print(f'Original: {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}') # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}') # on->off: 00101010
# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')
# Toggle all lower k bits
def toggle_lower_k(n, k):
mask = (1 << k) - 1 # k ones in the lowest positions
return n ^ mask
print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')Bit prüfen: Feststellen, ob ein Bit gesetzt ist
Um zu prüfen, ob Bit k gesetzt ist, verschieben Sie n um k Positionen nach rechts und verknüpfen das Ergebnis per AND mit 1: (n >> k) & 1. Dadurch wird Bit k an Position 0 verschoben und alle höherwertigen Bits werden ausgeblendet, sodass 0 (Bit k war 0) oder 1 (Bit k war 1) übrig bleibt. Alternativ können Sie bool(n & (1 << k)) für ein True/False-Ergebnis verwenden.
Das Prüfen eines Bits ist nicht destruktiv – n wird dabei nicht verändert. Sie können mehrere Bits prüfen, indem Sie jede Position unabhängig verschieben und maskieren. Dies bildet die Grundlage für das Durchlaufen der Bitdarstellung einer Zahl, wie es bei der Aufzählung von Teilmengen und beim Dynamic Programming mit Bitmaskenzuständen verwendet wird.
def check_bit(n, k):
return (n >> k) & 1
def is_bit_set(n, k):
return bool(n & (1 << k))
n = 0b10110101 # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')
# Count set bits using check_bit
def count_set_bits(n):
return sum(check_bit(n, k) for k in range(n.bit_length()))
print(f'\nSet bits in {n}: {count_set_bits(n)}')
# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
return [check_bit(n, k) for k in range(width)]
print(f'Bit list (LSB first): {to_bit_list(n)}')Bitmasken zur Darstellung von Teilmengen
Eine Ganzzahl mit n Bits kann eine Teilmenge einer n-elementigen Menge darstellen: Bit k ist 1, wenn Element k in der Teilmenge enthalten ist, andernfalls 0. Dadurch wird eine Teilmenge in einer einzigen Ganzzahl komprimiert, was O(1)-Operationen ermöglicht: eine Elementzugehörigkeit prüfen (mask & (1 << k)), ein Element hinzufügen (mask | (1 << k)), ein Element entfernen (mask & ~(1 << k)) sowie Vereinigungs- und Schnittmengen bilden (mask1 | mask2 und mask1 & mask2).
Bei n Elementen gibt es 2^n mögliche Teilmengen, die jeweils eindeutig durch eine n-Bit-Ganzzahl von 0 bis 2^n - 1 dargestellt werden. Wenn Sie alle Ganzzahlen von 0 bis 2^n - 1 durchlaufen, zählen Sie alle Teilmengen auf.
# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)
def subset_from_mask(mask):
return [elements[k] for k in range(n) if (mask >> k) & 1]
# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n): # 0 to 15 for n=4
print(f' {mask:04b}: {subset_from_mask(mask)}')
# Set operations
mask_ab = 0b0011 # {A, B}
mask_bc = 0b0110 # {B, C}
print(f'\nUnion: {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')Alle Teilmengen einer Maske durchlaufen
Beim Dynamic Programming mit Bitmasken müssen Sie häufig alle Teilmengen einer bestimmten Maske durchlaufen. Ein verbreiteter Trick besteht darin, mit sub = mask zu beginnen und mit sub = (sub - 1) & mask fortzufahren, bis sub den Wert 0 erreicht. Jede Iteration liefert eine andere Teilmaske. Über alle Masken hinweg ergibt dies insgesamt O(3^n), weil jedes Element in der äußeren Maske, aber nicht in der Teilmaske, in beiden oder in keiner der beiden Masken enthalten sein kann.
Diese Technik kommt bei Problemen wie „Array in Teilmengen mit gleichem XOR aufteilen“ oder „das maximale AND einer beliebigen Teilmenge finden“ zum Einsatz. Die effiziente Aufzählung von Teilmasken ist ein Kennzeichen fortgeschrittenen Dynamic Programmings mit Bitmasken.
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # empty subset
return submasks
mask = 0b1011 # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'
print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
print(f' {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')Bitmask-DP: Vorschau auf das Problem des Handlungsreisenden
Bitmask-DP löst Probleme, bei denen der Zustand eine Teilmenge besuchter Elemente enthält. Das klassische Beispiel ist das Problem des Handlungsreisenden (TSP): Finden Sie eine Rundreise mit minimalen Kosten, die n Städte besucht. Der Zustand ist dp[mask][city] = minimale Kosten, um die Städte in mask zu besuchen und in city zu enden. Bei n Städten gibt es 2^n × n Zustände, was eine Laufzeit von O(n^2 × 2^n) ergibt — für n ≤ 20 praktikabel.
Die Maske dient als komprimierte Menge besuchter Städte. Das Setzen, Löschen und Prüfen von Bits entspricht dem Besuchen, Verlassen und Abfragen von Städten. Das ist der Kern der Bitmask-DP: Verwenden Sie Bits als kompakte Menge für den Zustand.
# TSP with bitmask DP
import sys
def tsp(dist):
n = len(dist)
INF = float('inf')
# dp[mask][v] = min cost to reach v having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited (mask=1=0b0001)
for mask in range(1 << n):
for v in range(n):
if dp[mask][v] == INF: continue
if not (mask >> v) & 1: continue # v must be in mask
for u in range(n):
if (mask >> u) & 1: continue # u must not be visited
new_mask = mask | (1 << u)
dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])
full_mask = (1 << n) - 1
return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist)) # should be 80Multi-Bit-Maskierung: Extrahieren eines Felds
Manchmal müssen Sie nicht nur ein einzelnes Bit, sondern ein mehrbitiges Feld extrahieren — einen zusammenhängenden Bitbereich. Um die Bits von Position start bis start+length-1 zu extrahieren, erstellen Sie eine Maske aus length aufeinanderfolgenden 1-Bits: mask = (1 << length) - 1, und verwenden anschließend (n >> start) & mask.
Diese Technik wird beim Parsen gepackter Ganzzahlformate verwendet, etwa bei IP-Adressen, Pixeldaten oder Hardwareregistern, in denen mehrere kleine Werte in einer Ganzzahl gespeichert sind. Ein 16-Bit-RGB565-Pixel speichert beispielsweise Rot in den Bits 15–11, Grün in 10–5 und Blau in 4–0.
def extract_field(n, start, length):
mask = (1 << length) - 1 # e.g., length=3 => mask=0b111
return (n >> start) & mask
# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000 # 63432
red = extract_field(pixel, 11, 5) # bits 15-11
green = extract_field(pixel, 5, 6) # bits 10-5
blue = extract_field(pixel, 0, 5) # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red: {red} ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue: {blue} ({bin(blue)})')
# Packing values back
def pack_rgb565(r, g, b):
return (r << 11) | (g << 5) | b
packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')Bitmasken in Interviewaufgaben
Bitmasken kommen häufig bei folgenden Arten von Interviewaufgaben vor:
- Aufzählung von Teilmengen: Durchlaufen aller 2^n Teilmengen mithilfe der Masken 0 bis 2^n-1
- DP mit Zustandskomprimierung: Kodieren einer Menge besuchter Knoten oder Elemente als Bitmaske im DP-Zustand
- Berechtigungssysteme: Kombinieren der Flags READ/WRITE/EXECUTE mit OR und Prüfen mit AND
- Verfolgung besuchter Gitterzellen: Speichern besuchter Zellen kleiner Gitter in einer einzigen Ganzzahl
Ein wichtiges Anzeichen dafür, dass Bitmasken nützlich sind: Das Problem enthält eine kleine Menge (n ≤ 20 Elemente), und Sie müssen Kombinationen der Zugehörigkeit verfolgen. Für größere Mengen benötigen Sie andere Darstellungen.
# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
n = len(nums)
for mask in range(1 << n):
total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
if total == target:
subset = [nums[k] for k in range(n) if (mask >> k) & 1]
print(f'Found subset {subset} summing to {target}')
return True
return False
subset_sum_exists([3, 1, 4, 1, 5], 10) # finds a subset summing to 10
# Check if permutation covers all required elements (bitmask approach)
required = 0b11111 # need all 5 elements
visited = 0b01101 # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}') # False: missing bits 1 and 4Tricks zur effizienten Bit-Aufzählung
Beim Durchlaufen der gesetzten Bits einer Maske werden zwei gängige Techniken verwendet. Die Methode Verschieben und Prüfen: Verschieben Sie die Zahl nach rechts und prüfen Sie das LSB. Die Methode zur Isolierung des niedrigsten gesetzten Bits: Isolieren Sie das niedrigste gesetzte Bit mit n & -n, verarbeiten Sie es und löschen Sie es anschließend mit n &= n - 1. Die zweite Methode besucht nur gesetzte Bits und ist schneller, wenn die Maske dünn besetzt ist.
In Python können Sie für Popcount auch bin(n).count('1') oder n.bit_count() (ab 3.10) verwenden. Für die Bitposition jedes gesetzten Bits verwenden Sie n.bit_length() - 1, um das höchstwertige gesetzte Bit zu bestimmen.
# Iterate over set bit positions
def set_bit_positions(n):
positions = []
k = 0
while n:
if n & 1:
positions.append(k)
n >>= 1
k += 1
return positions
# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
positions = []
while n:
lsb = n & -n # isolate lowest set bit
k = lsb.bit_length() - 1 # position of that bit
positions.append(k)
n &= n - 1 # clear lowest set bit
return positions
mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast): {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')Kurztest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion aus Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die vier grundlegenden Bitmaskenoperationen sind Setzen (OR), Löschen (AND-NOT), Umschalten (XOR) und Prüfen (Shift-AND); Ganzzahlen können Teilmengen darstellen, wobei jedes Bit die Zugehörigkeit eines Elements kodiert und dadurch die Aufzählung von 2^n Teilmengen ermöglicht; und die Extraktion mehrbitiger Felder sowie Bitmask-DP verwenden dieselben Maskierungsprinzipien für eine komplexere Zustandskodierung. Als Nächstes untersuchen wir das Zählen von Bits, fehlende Zahlen und die Bitumkehrung mithilfe der Techniken aus dieser und der vorherigen Lektion.
Häufig gestellte Fragen
Ist die Lektion „Bitmasken: Setzen, Löschen, Umschalten und Prüfen“ kostenlos?
Ja — der vollständige Text von „Bitmasken: Setzen, Löschen, Umschalten und Prüfen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bitmasken: Setzen, Löschen, Umschalten und Prüfen“?
Implementieren Sie Hilfsfunktionen zum Setzen, Löschen, Umschalten und Prüfen einzelner Bits und verwenden Sie Bitmasken, um Teilmengen in Problemen zur Teilmengenerzeugung darzustellen. Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 3 von 4.
Wie lange dauert die Lektion „Bitmasken: Setzen, Löschen, Umschalten und Prüfen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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