Bits und das niedrigste gesetzte Bit zählen
Verwenden Sie popcount und den Trick n & -n
Bits und das niedrigste gesetzte Bit zählen ist eine kostenlose Competitive Programming Academy-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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Die Einsen zählen
In vielen Aufgaben soll ermittelt werden, wie viele Bits in einer Zahl gesetzt sind. Diese Anzahl wird popcount genannt und kommt bei Teilmengengrößen, Paritätsprüfungen und Bewertungen zum Einsatz. 🔢
Pythons integrierte Zählung
Die schnellste Möglichkeit, gesetzte Bits zu zählen, ist die Ganzzahlmethode bit_count(). Keine Schleife, kein Aufwand, einfach die Anzahl der Einsen.
print((13).bit_count()) # 0b1101 has 3 onesMit bin und count zählen
Falls Sie bit_count vergessen, wandeln Sie die Zahl in Binärtext um und zählen Sie die Einsen. Das ist langsamer, aber verständlich und leicht zu merken.
print(bin(13).count('1')) # 3Das niedrigste gesetzte Bit
Das niedrigste gesetzte Bit ist die am weitesten rechts stehende 1 einer Zahl. Es zu isolieren, ist später ein wichtiger Schritt bei Fenwick-Bäumen und Teilmengen-Tricks.
Mit n und -n isolieren
Der berühmte Trick n & -n behält nur das niedrigste gesetzte Bit. Negative Zahlen im Zweierkomplement machen das möglich.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Warum n und -n funktioniert
Beim Negieren werden alle Bits invertiert und 1 addiert, sodass alles unterhalb der niedrigsten 1 invertiert wird. AND lässt nur dieses einzelne Bit übrig.
Das niedrigste gesetzte Bit entfernen
Beim Subtrahieren von 1 zieht sich der Übertrag durch die nachfolgenden Nullen, sodass n & (n - 1) das niedrigste gesetzte Bit löscht. Wiederholen Sie den Vorgang, um die Einsen nacheinander zu entfernen.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Zählen nach Brian Kernighan
Führen Sie eine Schleife aus, solange die Zahl ungleich null ist, und löschen Sie bei jedem Durchlauf das niedrigste gesetzte Bit. Die Schleife läuft einmal pro gesetztem Bit und ist daher bei wenigen gesetzten Bits eine schnelle Methode für popcount.
c = 0
while n:
n &= n - 1
c += 1Eine Zweierpotenz prüfen
Eine positive Zweierpotenz hat genau ein gesetztes Bit, daher ist n & (n - 1) gleich 0. Eine einzige AND-Operation liefert sofort die Antwort.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Parität aus der Bitanzahl
Die Parität einer Zahl ist einfach ihre Popcount modulo 2. Damit können Sie in einem einzigen Schritt feststellen, ob die Anzahl der gesetzten Bits gerade oder ungerade ist.
parity = (13).bit_count() & 1 # 1Das schnellste Werkzeug wählen
Für maximale Geschwindigkeit verwenden Sie bit_count; um gesetzte Bits zu durchlaufen, verwenden Sie die Schleife mit n & (n-1). Mit dem richtigen Werkzeug halten Sie auch enge Zeitlimits ein. ⚡
Kurztest
Testen Sie den Trick mit dem niedrigsten gesetzten Bit.
Rückblick: Bits zählen
Sie können Einsen mit bit_count zählen, das niedrigste Bit mit n & -n isolieren und es mit n & (n-1) entfernen. Leistungsstarke Einzeiler. 🎉
Häufig gestellte Fragen
Ist die Lektion „Bits und das niedrigste gesetzte Bit zählen“ kostenlos?
Ja — der vollständige Text von „Bits und das niedrigste gesetzte Bit zählen“ 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 „Bits und das niedrigste gesetzte Bit zählen“?
Verwenden Sie popcount und den Trick n & -n 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 3 von 4.
Wie lange dauert die Lektion „Bits und das niedrigste gesetzte Bit zählen“?
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