Što su česte bit-manipulacijske trikove?

Question

Accepted Answer

**Bitna manipulacija** radi direktno na binarnoj reprezentaciji cijelih brojeva koristeći AND, OR, XOR, NOT i pomake. Omogućava kompaktne, bez-grananja i vrlo brze operacije. ## Osnovne operacije ```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 ``` ## Korisni trikovi ```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) ``` ## Primjer: pronađi jedinstveni broj (XOR trik) ```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 ``` ## Složenost Bitne operacije su O(1); gornja XOR pretraga je **O(n) vrijeme, O(1) prostor**. ## Kada koristiti / zamke Koristite za **bitmaskove** (enumeracija podskupova, DP nad stanjima), zastave, brzu matematiku i kod niske razine/ugrađene sustave. Pazite na bitove znaka, specifičnosti jezika za ponašanje pomaka i čitljivost — komentirajte neobične trikove. ## Zašto je to važno Bitna manipulacija daje elegantna O(1)-prostorna rješenja (kao XOR trik za jedinstveni broj) koja oduševljavaju na intervjuima. Bitmask DP čini mnoge kombinatorijalne probleme prostora stanja mogućima. Neophodno je u sustavima, grafici, kompresiji i kodu osjetljivom na performanse gdje svaki ciklus brojia.