Mitkä ovat yleiset bittien manipuloinnin temppu?

Question

Accepted Answer

**Bittien manipulointi** toimii suoraan kokonaislukujen binäärisessä esityksessä käyttäen AND-, OR-, XOR-, NOT- ja siirtotoimintoja. Se mahdollistaa kompaktit, haaraattomat ja erittäin nopeat operaatiot. ## Ydinoperaatiot ```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 ``` ## Hyödylliset temptu ```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) ``` ## Esimerkki: etsi yksittäinen luku (XOR-temppu) ```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 ``` ## Monimutkaisuus Bittien operaatiot ovat O(1); yllä oleva XOR-skannaus on **O(n) aika, O(1) tila**. ## Milloin käyttää / sudenkuopat Käytä **bittimaskeille** (osajoukon numerointi, DP tiloissa), lipuille, nopealle matematiikalle ja alhaisen tason/sulautetulle koodille. Varovaisuus etumerkkibittien, kielikohtaisen siirtokäyttäytymisen ja luettavuuden kanssa — kommentoi ei-ilmeisiä temppuja. ## Miksi sillä on merkitystä Bittien manipulointi tuottaa tyylikkäitä O(1)-tila ratkaisuja (kuten XOR yksittäinen-luku-temppu), jotka hämmästyttävät haastatteluissa. BittimaskiDP tekee monet kombinatoriset tilaavaruuden ongelmat ratkaistaviksi. Se on olennainen järjestelmissä, grafiikassa, pakkaamisessa ja suorituskyvyn kannalta kriittisissä koodeissa, joissa jokainen sykli on tärkeä.