Kateri so pogosti trikovi za manipulacijo bitov?

Question

Accepted Answer

**Manipulacija bitov** deluje neposredno na binarni predstavitvi celih števil z uporabo AND, OR, XOR, NOT in premikov. Omogoča kompaktne, brez-vejne in zelo hitre 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 ``` ## Koristni 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) ``` ## Primer: poiščite enojno število (trik 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 ``` ## Kompleksnost Bitne operacije so O(1); zgornji XOR scan je **O(n) čas, O(1) prostor**. ## Kdaj uporabiti / pasti Uporabite za **bitmask** (enumeracija podmnožic, DP preko stanj), zastavice, hitro matematiko in kodo nizke ravni/vgrajeno. Pazite na bity znaka, obnašanje premika specifično za jezik in berljivost — komentirajte neočitne trikove. ## Zakaj je to važno Manipulacija bitov daje elegantne rešitve O(1)-prostora (kot je trik XOR enojnega števila), ki preseneتijo na razgovorih. Bitmask DP naredi številne probleme kombinatoričnega prostora stanj izvedljive. Je bistvena v sistemih, grafiki, kompresiji in kodi kritični za zmogljivost, kjer šteje vsak cikel.