Manipulación de bits explicada: operadores, trucos y ejemplos

Qué problema resuelve la manipulación de bits

Un entero es una fila de bits, y muchos problemas tratan en realidad de esos bits: permisos de archivos como rwx, banderas de funcionalidades, máscaras de red, colores de píxeles, conjuntos compactos de opciones, sumas de verificación y hashes. Los operadores bit a bit permiten leer y cambiar muchos bits a la vez en una sola operación, lo que es compacto en memoria y muy rápido.

Las preguntas de entrevista también usan trucos con bits porque dan soluciones elegantes con espacio O(1), por ejemplo encontrar el único número que aparece una vez cuando todos los demás aparecen dos veces.

Los operadores

Los ejemplos usan a = 12 (binario 1100) y b = 10 (binario 1010).

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

Operaciones con un solo bit

Las posiciones de los bits se cuentan desde 0 a la derecha (el bit menos significativo). La máscara 1 << i tiene activado solo el bit i.

Ejemplo resuelto: contar bits activos

El método de Brian Kernighan borra el bit activo más bajo hasta que no queda ninguno, por lo que itera una vez por cada bit en 1, no una vez por cada posición de bit. Traza para x = 44 (binario 101100):

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() está disponible desde Python 3.10. int.bit_length() devuelve el número de bits necesarios para escribir el número en binario, sin el signo.

Trucos clásicos en Python

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

La máscara 0 es el conjunto vacío, 5 (binario 101) es ['a', 'c'] y 7 son los tres elementos. La programación dinámica con máscaras de bits usa la misma idea, con una máscara como estado, para problemas de hasta unos 20 elementos, como el problema del viajante en entradas pequeñas.

Dos clásicos más: x & 1 vale 1 para los números impares, y hacer XOR de todos los números de 0 a n con todos los valores de una lista encuentra el único número que falta.

Complejidad temporal y espacial

Una máscara de bits usa un bit por cada posible elemento, de modo que un conjunto de 64 banderas cabe en un único entero de 64 bits, frente a 64 variables booleanas o elementos de lista independientes.

Errores comunes

• Números negativos: los enteros de Python se comportan como si tuvieran infinitos bits de signo, así que ~5 es -6 y bin(-5) es -0b101, no una cadena en complemento a dos. Para ver patrones de 32 bits, aplica una máscara al valor: -5 & 0xFFFFFFFF.
• El desplazamiento a la derecha de números negativos en Python es aritmético: -8 >> 1 es -4, y -1 >> 10 sigue siendo -1.
• Desbordamiento en lenguajes de ancho fijo: en Java o C, 1 << 31 en un int de 32 bits se vuelve negativo o indefinido; usa un tipo de 64 bits y 1L << 40 o 1ULL << 40.
• Confundir operadores lógicos y bit a bit: and y or (&&, || en lenguajes de tipo C) devuelven valores de verdad, mientras que & y | operan bit a bit.
• Legibilidad: sustituir x * 2 por x << 1 no aporta ninguna mejora de velocidad en los compiladores modernos ni en Python, y hace el código más difícil de leer.

Usos en el mundo real

• Permisos de archivos en Unix: chmod 754 establece tres grupos de 3 bits (rwx = 4 + 2 + 1).
• Redes: máscaras de subred IPv4, donde ip & mask da la dirección de red de un bloque CIDR.
• Banderas y opciones: re.IGNORECASE | re.MULTILINE de Python y enum.Flag combinan opciones con OR.
• Gráficos y colores: un valor RGB de 24 bits empaqueta rojo, verde y azul como (r << 16) | (g << 8) | b.
• Estructuras de datos y algoritmos: filtros de Bloom, bitsets, árboles de Fenwick (que usan i & -i), hashing y sumas de verificación.
• Problemas de entrevista: single number, counting bits, potencia de dos, invertir bits, número que falta, subconjuntos mediante máscara de bits, suma de dos enteros sin +.