¿Cuáles son los trucos comunes de manipulación de bits?

Question

Accepted Answer

**La manipulación de bits** opera directamente sobre la representación binaria de números enteros usando AND, OR, XOR, NOT y desplazamientos. Permite operaciones compactas, sin ramificaciones y muy rápidas. ## Operaciones principales ```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 ``` ## Trucos útiles ```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) ``` ## Ejemplo: encontrar el número único (truco 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 ``` ## Complejidad Las operaciones de bits son O(1); el escaneo XOR anterior es **O(n) tiempo, O(1) espacio**. ## Cuándo usar / Trampas Usa para **máscaras de bits** (enumeración de subconjuntos, DP sobre estados), banderas, matemáticas rápidas y código de bajo nivel/embebido. Ten cuidado con los bits de signo, el comportamiento de desplazamiento específico del lenguaje y la legibilidad — comenta trucos no obvios. ## Por qué es importante La manipulación de bits produce soluciones elegantes O(1)-espacio (como el truco XOR del número único) que sorprenden en las entrevistas. El DP con máscara de bits hace que muchos problemas combinatorios de espacio de estados sean manejables. Es esencial en sistemas, gráficos, compresión y código crítico para el rendimiento donde cada ciclo cuenta.