Bitmasken als kleine Mengen
Stellen Sie Teilmengen als Ganzzahlen dar
Bitmasken als kleine Mengen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Eine Ganzzahl als Menge
Eine einzige Ganzzahl kann für eine ganze Menge stehen: Ist Bit i gleich 1, ist Element i enthalten. So lassen sich Teilmengen in einem kleinen, schnellen Wert speichern. 🎒
Leere und vollständige Mengen
Die Zahl 0 ist die leere Menge, während ein Wert, bei dem die niedrigsten n Bits alle gesetzt sind, jedes Element enthält.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsEin Element hinzufügen
Um Element i zur Menge hinzuzufügen, setzen Sie sein Bit per OR. Das entspricht genau dem Setzen eines Bits, diesmal verstanden als Vereinigung mit einem Element.
s = 0
s |= (1 << 2) # add element 2Ein Element entfernen
Um Element i zu entfernen, verknüpfen Sie die Maske per AND mit dem invertierten Bit. Das Element verlässt die Menge, während alle anderen unverändert bleiben. Das ist die Differenz mit einem Element.
s &= ~(1 << 2) # remove element 2Zugehörigkeit testen
Prüfen Sie, ob Element i enthalten ist, indem Sie die Maske per AND mit seinem Bit verknüpfen. Ein Ergebnis ungleich null bedeutet, dass es ein Element der Menge ist.
if s & (1 << 2):
print('2 is in the set')Vereinigung und Schnittmenge
Verknüpfen Sie zwei Masken per OR für ihre Vereinigung und per AND für ihre Schnittmenge. Ganze Mengenoperationen werden so jeweils zu einer einzigen Maschineninstruktion.
union = a | b
inter = a & bDie Mengengröße ist Popcount
Die Anzahl der Elemente in einer Bitmaske entspricht einfach der Anzahl ihrer gesetzten Bits. Verwenden Sie bit_count, um die Größe sofort zu erhalten.
size = mask.bit_count()Alle Teilmengen durchlaufen
Für n Elemente enumerieren die ganzen Zahlen von 0 bis 2 hoch n minus 1 jede mögliche Teilmenge. Eine einfache Schleife über diesen Bereich deckt sie alle ab.
for mask in range(1 << n):
pass # mask is one subsetTeilmasken schnell durchlaufen
Um nur die Teilmengen einer bestimmten Maske zu durchlaufen, verwenden Sie die klassische Teilmasken-Schleife. Sie durchläuft jede Teilmenge in absteigender Reihenfolge.
sub = mask
while sub:
sub = (sub - 1) & maskHier kommt Bitmasken-DP zum Einsatz
Bitmasken bilden den Zustand vieler DP-Probleme, etwa beim Problem des Handlungsreisenden, bei dem die Maske festhält, welche Knoten Sie bereits besucht haben.
Halten Sie n klein
Bei 2 hoch n Teilmengen bleibt dieser Trick nur für kleine n praktikabel, normalerweise bis ungefähr 20. Darüber hinaus explodiert die Anzahl. ⚠️
Kurztest
Noch eine Frage zu Mengen als Masken.
Rückblick: Mengen mit Bitmasken
Sie können eine Menge in einer einzigen Ganzzahl speichern, Elemente mit Masken hinzufügen und entfernen und jede Teilmenge durchlaufen. Damit wird schnelles Bitmasken-DP möglich. 🎉
Häufig gestellte Fragen
Ist die Lektion „Bitmasken als kleine Mengen“ kostenlos?
Ja — der vollständige Text von „Bitmasken als kleine Mengen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bitmasken als kleine Mengen“?
Stellen Sie Teilmengen als Ganzzahlen dar Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 4 von 4.
Wie lange dauert die Lektion „Bitmasken als kleine Mengen“?
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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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
- AND, OR, XOR und Shifts
- Ein Bit setzen, löschen und umschalten
- Bits und das niedrigste gesetzte Bit zählen
- Bitmasken als kleine Mengen