Care sunt trucurile comune de manipulare a biților?

Question

Accepted Answer

**Manipularea biților** operează direct pe reprezentarea binară a numerelor întregi folosind AND, OR, XOR, NOT și deplasări. Aceasta permite operații compacte, fără ramificații și foarte rapide. ## Operații de bază ```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 ``` ## Trucuri utile ```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) ``` ## Exemplu: găsirea numărului singular (trucul 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 ``` ## Complexitate Operațiile pe biți sunt O(1); scanarea XOR de mai sus este **O(n) timp, O(1) spațiu**. ## Când să folosești / capcane Foloseș pentru **măști de biți** (enumerare submulțimi, DP peste stări), flaguri, matematică rapidă și cod low-level/embedded. Fii atent la biții de semn, comportamentul deplasărilor specific limbajului și lizibilitate — comentează trucurile non-evidente. ## De ce conteaza Manipularea biților produce soluții elegante O(1)-spațiu (cum ar fi trucul numărului singular XOR) care uimesc la interviuri. Bitmask DP face tractabile multe probleme de spațiu de stări combinatoriale. Este esențial în sisteme, grafică, compresie și cod critic din perspectiva performanței, unde fiecare ciclu contează.