Quali sono i trucchi comuni di manipolazione dei bit?

Question

Accepted Answer

**Bit manipulation** opera direttamente sulla rappresentazione binaria degli interi utilizzando AND, OR, XOR, NOT e shift. Consente operazioni compatte, senza ramificazioni e molto veloci. ## Operazioni principali ```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 ``` ## Trucchi utili ```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) ``` ## Esempio: trovare il numero singolo (trick 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 ``` ## Complessità Le operazioni su bit sono O(1); la scansione XOR precedente è **O(n) tempo, O(1) spazio**. ## Quando usare / insidie Usare per **bitmask** (enumerazione di sottoinsiemi, DP su stati), flag, operazioni matematiche veloci e codice a basso livello/embedded. Attenzione ai bit di segno, al comportamento degli shift specifico del linguaggio e alla leggibilità — commenta i trucchi non ovvi. ## Perché è importante La manipolazione dei bit produce soluzioni eleganti con spazio O(1) (come il trick XOR del numero singolo) che stupiscono nei colloqui. Bitmask DP rende molti problemi combinatori con spazio degli stati trattabili. È essenziale nei sistemi, grafica, compressione e codice critico per le prestazioni dove ogni ciclo conta.