Jakie są powszechne sztuczki manipulacji bitami?

Question

Accepted Answer

**Manipulacja bitami** operuje bezpośrednio na binarnej reprezentacji liczb całkowitych za pomocą operacji AND, OR, XOR, NOT i przesunięć. Umożliwia kompaktowe, wolne od rozgałęzień i bardzo szybkie operacje. ## Operacje podstawowe ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Przydatne sztuczki ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## Przykład: znalezienie pojedynczej liczby (sztuczka XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Złożoność Operacje bitowe to O(1); skan XOR powyżej to **O(n) czas, O(1) przestrzeń**. ## Kiedy używać / pułapki Używaj dla **masek bitowych** (wyliczanie podzbiorów, DP nad stanami), flag, szybkiej matematyki i kodu niskopoziomowego/wbudowanego. Uważaj na bity znaku, zachowanie przesunięć specyficzne dla języka i czytelność — opatrz komentarzem nieoczywiste sztuczki. ## Dlaczego to ważne Manipulacja bitami daje eleganckie rozwiązania w O(1) przestrzeni (jak sztuczka XOR dla pojedynczej liczby), które zadziwiają podczas rozmów rekrutacyjnych. DP na maskach bitowych czyni wiele kombinatorycznych problemów przestrzeni stanów rozwiązywalnych. Jest niezbędna w systemach, grafice, kompresji i kodzie krytycznym dla wydajności, gdzie liczy się każdy cykl.