Operatory bitowe: AND, OR, XOR, NOT i przesunięcia

Operacje bitowe pozwalają działać bezpośrednio na binarnej reprezentacji liczb całkowitych. Wiele problemów, które wydają się złożone, staje się trywialnych dzięki odpowiedniej sztuczce bitowej: można znaleźć brakującą liczbę w czasie O(n) i przy użyciu O(1) pamięci, zamienić wartości zmiennych bez zmiennej tymczasowej lub zwięźle zakodować podzbiory. Rekruterzy wykorzystują takie zadania do sprawdzania znajomości działania na niskim poziomie oraz kreatywnego myślenia.

Liczby całkowite w Pythonie mają dowolną precyzję — mogą być tak duże, jak pozwala na to pamięć — ale operacje bitowe zawsze stosują na poziomie sprzętowym standardową semantykę uzupełnienia do dwóch. Wszystkie sześć operatorów działa bit po bicie na binarnych reprezentacjach liczb całkowitych.

Operator AND (&) zwraca 1 tylko wtedy, gdy oba bity wejściowe mają wartość 1. Jego głównym zastosowaniem jest maskowanie: wybieranie określonych bitów liczby przy jednoczesnym wyzerowaniu wszystkich pozostałych. Aby sprawdzić, czy bit k jest ustawiony w liczbie n, należy obliczyć n & (1 << k) — jeśli wynik jest różny od zera, bit k ma wartość 1.

AND służy także do zerowania najmniej znaczącego ustawionego bitu: n & (n - 1) usuwa najbardziej prawy bit 1. Wykorzystuje się to do wydajnego zliczania ustawionych bitów oraz do sprawdzania, czy liczba jest potęgą dwójki (potęga dwójki ma dokładnie jeden ustawiony bit, więc n & (n-1) == 0).

Operator OR (|) zwraca 1, jeśli co najmniej jeden bit wejściowy ma wartość 1. Jego głównym zastosowaniem jest ustawianie określonego bitu na 1 bez wpływania na pozostałe. Aby ustawić bit k w liczbie n, należy użyć n | (1 << k). Jedynka przesunięta na pozycję k włącza ten bit, a wszystkie pozostałe bity pozostają niezmienione, ponieważ operacja OR dowolnego bitu z 0 daje jego pierwotną wartość.

OR służy także do łączenia flag: jeśli flagi funkcji są reprezentowane jako pojedyncze bity, za pomocą OR można włączyć wiele flag. Na przykład READ | WRITE | EXECUTE łączy trzy bity uprawnień w jedną liczbę całkowitą.

Operator XOR (^) zwraca 1, gdy bity wejściowe różnią się. XOR ma trzy ważne właściwości algebraiczne: a ^ a = 0 (takie same wartości wejściowe się znoszą), a ^ 0 = a (zero jest elementem neutralnym), a także jest przemienny i łączny. Dzięki tym właściwościom XOR jest podstawowym narzędziem do znajdowania unikalnych elementów.

XOR służy także do przełączania określonego bitu: n ^ (1 << k) odwraca bit k, pozostawiając pozostałe bity bez zmian. Jeśli bit k miał wartość 0, otrzyma wartość 1, a jeśli miał wartość 1, otrzyma wartość 0.

Operator NOT (~) odwraca wszystkie bity. W Pythonie ~n jest równe -(n+1) ze względu na reprezentację w uzupełnieniu do dwóch. Dla wielu osób jest to zaskakujące: ~5 = -6, a nie naiwnie oczekiwane 0b11111010. Liczby całkowite w Pythonie mają nieskończoną precyzję, więc odwrócenie wszystkich bitów liczby dodatniej daje wynik ujemny w uzupełnieniu do dwóch.

W praktyce operatora ~ rzadko używa się w Pythonie samodzielnie do operacji bitowych. Zamiast tego stosuje się go w połączeniu z AND do zerowania określonych bitów albo oblicza ~n & mask, gdzie maska ogranicza szerokość do określonej liczby bitów (np. & 0xFFFFFFFF dla 32 bitów).

Operator przesunięcia w lewo (<<) przesuwa wszystkie bity o k pozycji w lewo, wypełniając zwolnione pozycje z prawej strony zerami. Jest to równoważne mnożeniu przez 2^k. Przesunięcie w lewo o 1 podwaja wartość, a przesunięcie o k mnoży ją przez 2^k.

W zadaniach rekrutacyjnych przesunięcia w lewo najczęściej służą do tworzenia masek bitowych: 1 << k tworzy liczbę, w której ustawiony jest tylko bit k. Stanowi to podstawę wszystkich operacji bitowych — ustawianie, zerowanie, przełączanie i sprawdzanie pojedynczych bitów zaczyna się od 1 << k.

Operator przesunięcia w prawo (>>) przesuwa wszystkie bity o k pozycji w prawo, odrzucając k najbardziej prawych bitów. Jest to równoważne dzieleniu całkowitemu przez 2^k. Przesunięcie w prawo w Pythonie jest zawsze arytmetyczne: najbardziej lewe bity są wypełniane bitem znaku (0 dla liczby dodatniej, 1 dla liczby ujemnej).

Typowa sztuczka rekrutacyjna polega na wyodrębnieniu bitu k z liczby n za pomocą (n >> k) & 1. Bit k zostaje w ten sposób przesunięty na pozycję 0, a wszystkie pozostałe bity są odfiltrowywane za pomocą maski. Jest to najprostszy sposób sprawdzenia dowolnego określonego bitu bez konieczności obliczania i porównywania pełnej maski.

Oto zestawienie najczęściej spotykanych idiomów operacji bitowych, z którymi można się zetknąć podczas rozmów rekrutacyjnych. Należy zapamiętać te wzorce — pojawiają się wielokrotnie w dziesiątkach zadań:

• n & 1 — sprawdzenie, czy n jest nieparzyste
• n & (n-1) — wyzerowanie najmniej znaczącego ustawionego bitu
• n & -n — wyodrębnienie najmniej znaczącego ustawionego bitu
• n | (1 << k) — ustawienie bitu k
• n & ~(1 << k) — wyzerowanie bitu k
• n ^ (1 << k) — przełączenie bitu k
• (n >> k) & 1 — sprawdzenie bitu k

Zliczanie liczby bitów 1 w liczbie całkowitej nazywa się zliczaniem populacji (popcount). Naiwne podejście polega na iterowaniu po wszystkich bitach. Sztuczka Briana Kernighana jest szybsza: polega na wielokrotnym zerowaniu najmniej znaczącego ustawionego bitu za pomocą n &= n - 1 i zliczaniu iteracji aż do momentu, gdy n stanie się równe 0. Każda iteracja usuwa dokładnie jeden bit 1, więc pętla wykonuje się dokładnie tyle razy, ile jest bitów 1.

Python 3.10+ udostępnia metodę int.bit_count(), która bezpośrednio zwraca tę liczbę. W starszych wersjach standardowym ręcznym rozwiązaniem jest sztuczka Kernighana. Technika ta rozwiązuje także problem „Hamming Weight” na LeetCode.

W przeciwieństwie do C/Java liczby całkowite w Pythonie są dowolnie duże — nie występuje przepełnienie 32-bitowe ani 64-bitowe. Oznacza to, że podczas rozwiązywania problemów wymagających działania na 32 bitach trzeba ręcznie ograniczać wyniki za pomocą maski: należy użyć & 0xFFFFFFFF, aby zachować tylko 32 najmłodsze bity.

Operator NOT ~n w Pythonie zwraca -(n+1), a nie wersję z odwróconymi bitami, której można by oczekiwać na podstawie języka C. W problemach 32-bitowych należy użyć ~n & 0xFFFFFFFF albo obliczyć 0xFFFFFFFF ^ n, aby uzyskać oczekiwane 32-bitowe dopełnienie. Te różnice często sprawiają problemy kandydatom przyzwyczajonym do operacji bitowych w stylu języka C.

Przesunięcia w lewo i w prawo zapewniają niezwykle szybki sposób mnożenia lub dzielenia przez potęgi dwójki. Na poziomie sprzętowym przesunięcia bitowe są operacjami wykonywanymi w jednej instrukcji, podczas gdy mnożenie i dzielenie wymagają wielu cykli. W Pythonie mnożenie liczb całkowitych jest już wydajne, ale zrozumienie tej zależności pomaga wyraźniej dostrzegać wzorce bitowe.

Przydatna zależność: aby sprawdzić, czy n jest wielokrotnością 2^k, należy użyć (n & (2^k - 1)) == 0. Maska 2^k - 1 ma ustawione wszystkie niższe k bitów; wykonanie na niej operacji AND daje resztę z dzielenia przez 2^k. Jest to równoważne n % (2^k), ale szybsze w językach opartych na C.

Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.

W tej lekcji poznali Państwo następujące zagadnienia: AND maskuje bity, OR ustawia bity, XOR przełącza bity i wykrywa różnice, NOT odwraca bity (w Pythonie daje wynik -(n+1)), a przesunięcia służą do mnożenia i dzielenia przez potęgi dwójki, n & (n-1) zeruje najmniej znaczący ustawiony bit i stanowi podstawę sprawdzania potęg dwójki oraz zliczania bitów, a także Python nie ma przepełnienia dla stałej szerokości, dlatego problemy 32-bitowe wymagają jawnego maskowania za pomocą & 0xFFFFFFFF. W następnej części wykorzystamy właściwość samoodwrotności XOR do rozwiązywania rodziny problemów z pojedynczą liczbą.