Publicado · en mejora
Algorithm
La manipulación de bits trata los enteros como dígitos binarios y usa AND, OR, XOR y desplazamientos para manejar conjuntos, flags y DP con máscaras.
La manipulación de bits consiste en ver un entero como una secuencia de ceros y unos y usar AND, OR, XOR, NOT y desplazamientos para leer, activar, desactivar o invertir bits concretos. Los ordenadores guardan los enteros en binario y los negativos en complemento a dos, así que cada una de estas operaciones suele ser una sola instrucción de la CPU. Una expresión corta como x & -x (el bit activo más bajo) o x & (x - 1) (ese bit borrado) puede sustituir a un bucle completo.
Es importante porque un solo entero puede representar un conjunto de unos 20 elementos, lo que permite recorrer todos sus subconjuntos y usar conjuntos como estados en programación dinámica con máscaras de bits. En las entrevistas técnicas aparecen a menudo la enumeración de subconjuntos, las propiedades de XOR y el popcount, y en producción los bits sostienen permisos de archivos, feature flags, cálculo de subredes, tablas hash e índices de mapa de bits. Las reglas cambian según el lenguaje: los enteros de Python no tienen límite, JavaScript convierte a 32 bits y ofrece >>>, Java también tiene >>> y en C++ conviene usar tipos sin signo para las máscaras.
Conviene empezar convirtiendo números a binario y a complemento a dos a mano. Después, practica las cuatro operaciones sobre un bit (activar, desactivar, invertir y comprobar) e imprime todos los subconjuntos recorriendo una máscara de 0 a 2^n - 1. A continuación pasa a la enumeración de submáscaras y a problemas de DP con máscaras, como la asignación de tareas o el problema del viajante, y por último revisa el ancho de los enteros y las reglas de desplazamiento de tus lenguajes.
Un número negativo se obtiene invirtiendo todos los bits y sumando 1. El desplazamiento a la izquierda multiplica por 2 y el de la derecha divide por 2, y cada lenguaje distingue entre desplazamiento aritmético y lógico.
Con la máscara 1 << i, OR activa el bit i, AND NOT lo desactiva y XOR lo invierte. x & -x aísla el bit activo más bajo y x & (x - 1) lo elimina.
Los subconjuntos de n elementos se corresponden uno a uno con los enteros de 0 a 2^n - 1, y la unión, la intersección y la diferencia cuestan una sola operación de bits.
Los bits activos se cuentan repitiendo x &= x - 1 o con una función integrada. Como a ^ a = 0, XOR encuentra el valor sin pareja y da distancias de Hamming y códigos Gray.
popcount cuenta los bits activos borrando el más bajo con x &= x - 1 hasta que no queda ninguno. subsets recorre una máscara de 0 a 2^n - 1 y elige los elementos cuyo bit está activo, generando todos los subconjuntos. La última línea muestra 12 & -12 = 4 (el bit activo más bajo), 12 & 11 = 8 (ese bit borrado) y x ^ x = 0. Se ejecuta con python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Manipulación de bits.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Manipulación de bits.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.