Zliczanie bitów i najniższy ustawiony bit
Używanie popcount i sztuczki n & -n
Zliczanie bitów i najniższy ustawiony bit to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Zliczanie jedynek
W wielu zadaniach trzeba policzyć, ile bitów w liczbie jest ustawionych. Wynik ten nazywa się popcount. Pojawia się między innymi przy obliczaniu rozmiarów podzbiorów, sprawdzaniu parzystości i naliczaniu punktów. 🔢
Wbudowane zliczanie w Pythonie
Najszybszym sposobem zliczania ustawionych bitów jest metoda liczby całkowitej bit_count(). Bez pętli i bez zbędnych komplikacji otrzymuje się po prostu liczbę jedynek.
print((13).bit_count()) # 0b1101 has 3 onesZliczanie za pomocą bin i count
Jeśli nie pamięta się o bit_count, można zamienić liczbę na zapis binarny i policzyć jedynki. To rozwiązanie jest wolniejsze, ale przejrzyste i łatwe do zapamiętania.
print(bin(13).count('1')) # 3Najniższy ustawiony bit
Najniższy ustawiony bit to skrajna prawa jedynka w liczbie. Izolowanie go jest ważną techniką używaną później w drzewach Fenwicka i przy operacjach na podzbiorach.
Izolowanie za pomocą n i -n
Słynna sztuczka n & -n pozostawia tylko najniższy ustawiony bit. Liczby ujemne zapisane w kodzie uzupełnień do dwóch sprawiają, że działa to niemal jak magia.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Dlaczego n i -n działa
Negacja odwraca wszystkie bity i dodaje 1, więc wszystkie bity poniżej najniższej jedynki zostają odwrócone. Wykonanie AND pozostawia tylko ten pojedynczy bit.
Usuwanie najniższego ustawionego bitu
Odjęcie 1 powoduje pożyczkę przez końcowe zera, dlatego n & (n - 1) usuwa najniższy ustawiony bit. Powtarzanie tej operacji pozwala usuwać jedynki po kolei.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Zliczanie metodą Briana Kernighana
Należy wykonywać pętlę, dopóki liczba jest różna od zera, za każdym razem czyszcząc najniższy bit. Pętla wykonuje się raz na każdy ustawiony bit, więc jest szybka przy rzadkim popcount.
c = 0
while n:
n &= n - 1
c += 1Sprawdzanie potęgi dwójki
Dodatnia potęga dwójki ma dokładnie jeden ustawiony bit, więc n & (n - 1) daje 0. Jedna operacja AND pozwala natychmiast to sprawdzić.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Parzystość na podstawie liczby bitów
Parzystość liczby to po prostu jej popcount modulo 2. Pozwala w jednym kroku rozstrzygnąć, czy liczba ustawionych bitów jest parzysta, czy nieparzysta.
parity = (13).bit_count() & 1 # 1Wybór najszybszego narzędzia
Do uzyskania maksymalnej szybkości należy użyć bit_count, a do przechodzenia po ustawionych bitach — pętli z n & (n-1). Wybór właściwego narzędzia pomaga zmieścić się w ścisłych limitach czasu. ⚡
Szybkie sprawdzenie
Proszę sprawdzić sztuczkę z najniższym ustawionym bitem.
Podsumowanie: zliczanie bitów
Jedynki można zliczać za pomocą bit_count, izolować najniższy bit przez n & -n, a usuwać go za pomocą n & (n-1). To potężne jednolinijkowe operacje. 🎉
Często zadawane pytania
Czy lekcja „Zliczanie bitów i najniższy ustawiony bit” jest bezpłatna?
Tak — pełny tekst „Zliczanie bitów i najniższy ustawiony bit” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Zliczanie bitów i najniższy ustawiony bit”?
Używanie popcount i sztuczki n & -n Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Zliczanie bitów i najniższy ustawiony bit”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- AND, OR, XOR i przesunięcia
- Ustawianie, czyszczenie i przełączanie bitu
- Zliczanie bitów i najniższy ustawiony bit
- Maski bitowe jako małe zbiory