Quais são os truques comuns de manipulação de bits?

Question

Accepted Answer

**Manipulação de bits** opera diretamente na representação binária de inteiros usando AND, OR, XOR, NOT e deslocamentos. Ela permite operações compactas, livres de ramificações e muito rápidas. ## Operações principais ```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 ``` ## Truques úteis ```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) ``` ## Exemplo: encontrar o número único (truque 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 ``` ## Complexidade Operações de bits são O(1); a varredura XOR acima é **O(n) de tempo, O(1) de espaço**. ## Quando usar / armadilhas Use para **máscaras de bits** (enumeração de subconjuntos, DP sobre estados), flags, matemática rápida e código de baixo nível/embarcado. Cuidado com bits de sinal, comportamento de deslocamento específico da linguagem e legibilidade — comente truques não óbvios. ## Por que isso importa Manipulação de bits oferece soluções elegantes com espaço O(1) (como o truque do número único XOR) que impressionam em entrevistas. DP com máscara de bits torna muitos problemas de espaço de estados combinatorial tratáveis. É essencial em sistemas, gráficos, compressão e código sensível a desempenho, onde cada ciclo conta.