Kokie yra bendri bitų manipuliavimo triukai?

Question

Accepted Answer

**Bit manipulation** tiesiogiai veikia sveikųjų skaičių dvejetainio vaizdo su AND, OR, XOR, NOT ir poslinkio operacijomis. Tai leidžia gauti kompaktiškus, be šakų ir labai greitus veiksmus. ## Pagrindinės operacijos ```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 ``` ## Naudingi triukai ```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) ``` ## Pavyzdys: rasti vieną skaičių (XOR triukas) ```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 ``` ## Sudėtingumas Bitų operacijos yra O(1); aukščiau esantis XOR skėlimas yra **O(n) laikas, O(1) erdvė**. ## Kada naudoti / spąstai Naudokite **bitmask** (pogrupio enumeracijai, DP per būseną), vėliavoms, greitai matematikai ir žemo lygio/įterptam kodui. Atsargiai su ženklų bitais, kalbai specifišku poslinkio elgesiu ir skaitomumu — komentuokite neaiškius triukus. ## Kodėl tai svarbu Bitų manipuliavimas sukuria elegantžius O(1) erdvės sprendimus (pvz., XOR vieno skaičiaus triukas), kurie nustebina interviu. Bitmask DP daro daugybę kombinatorinių būsenos erdvės problemų sprendžiamų. Jis yra būtinas sistemose, grafikoje, suspaudime ir paspartintuotame kode, kur kiekvienas ciklas svarbus.