Milyen gyakori bit-manipulációs trükkök vannak?

Question

Accepted Answer

**Bit-manipuláció** közvetlenül az egész számok bináris reprezentációján működik AND, OR, XOR, NOT és eltolások segítségével. Lehetővé teszi kompakt, elágazás-mentes és nagyon gyors műveleteket. ## Alapvető műveletek ```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 ``` ## Hasznos trükkök ```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) ``` ## Példa: keressük meg az egyetlen számot (XOR trükk) ```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 ``` ## Bonyolultság Bit-műveletek O(1); a fenti XOR-vizsgálat **O(n) idő, O(1) tér**. ## Mikor használjuk / buktatók Használja a **bitkoszorkúkat** (alcsalád felsorolása, DP állapotokon), jelzőket, gyors matematikát és alacsony szintű/beágyazott kódot. Vigyázzon az előjel bitjeire, a nyelvspecifikus eltolás viselkedésére és az olvashatóságra — jelezze a nem egyértelmű trükkőket. ## Miért fontos ez A bit-manipuláció elegáns O(1)-tér megoldásokat (mint az XOR egyetlen-szám trükk) ad, amelyek lenyűgözik az interjúkban. A bitmask DP számos kombinatorikai állapottér-problémát kezelhetővé tesz. Nélkülözhetetlen a rendszerekben, grafikában, tömörítésben és teljesítménykritikus kódban, ahol minden ciklus számít.