Bitmasks como conjuntos diminutos
Represente subconjuntos como enteros
Bitmasks como conjuntos diminutos es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Un entero como conjunto
Un solo entero puede representar un conjunto completo: que el bit i sea 1 significa que el elemento i pertenece a él. Así puede empaquetar subconjuntos en un único valor pequeño y rápido. 🎒
Los conjuntos vacío y completo
El número 0 es el conjunto vacío, mientras que un valor cuyos n bits de menor posición estén activados significa que todos los elementos están presentes.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAñadir un elemento
Para añadir el elemento i al conjunto, aplique OR a su bit. Es exactamente la operación de activar un bit, interpretada ahora como una unión con un elemento.
s = 0
s |= (1 << 2) # add element 2Eliminar un elemento
Para eliminar el elemento i, aplique AND con el bit invertido. El elemento sale del conjunto y todos los demás permanecen en su sitio. Es la diferencia de conjuntos con un solo elemento.
s &= ~(1 << 2) # remove element 2Comprobar la pertenencia
Compruebe si el elemento i pertenece al conjunto aplicando AND con su bit. Un resultado distinto de cero significa que es un miembro del conjunto.
if s & (1 << 2):
print('2 is in the set')Unión e intersección
Aplique OR a dos máscaras para obtener su unión y AND para obtener su intersección. Las operaciones con conjuntos completos se convierten en una instrucción de máquina cada una.
union = a | b
inter = a & bEl tamaño del conjunto es el popcount
El número de elementos de una bitmask es simplemente su cantidad de bits activados. Use bit_count para obtener el tamaño al instante.
size = mask.bit_count()Recorrer todos los subconjuntos
Para n elementos, los enteros del 0 al 2 elevado a n menos 1 enumeran todos los subconjuntos. Un sencillo bucle de rango los cubre todos.
for mask in range(1 << n):
pass # mask is one subsetIterar rápidamente sobre las submáscaras
Para visitar únicamente los subconjuntos de una máscara dada, use el clásico bucle de submask. Recorre cada subconjunto en orden descendente.
sub = mask
while sub:
sub = (sub - 1) & maskAquí vive la DP con bitmask
Las bitmasks representan el estado en muchos problemas de DP, como el del viajante, donde la máscara registra qué nodos ha visitado.
Mantenga n pequeño
Con 2 elevado a n subconjuntos, este truco solo resulta práctico para valores pequeños de n, normalmente hasta aproximadamente 20. A partir de ahí, el conteo crece de forma explosiva. ⚠️
Comprobación rápida
Una última pregunta sobre conjuntos representados como máscaras.
Resumen: conjuntos con bitmask
Puede almacenar un conjunto en un solo entero, añadir y eliminar elementos con máscaras y recorrer todos los subconjuntos. Esto permite usar DP rápida con bitmasks. 🎉
Preguntas frecuentes
¿La lección «Bitmasks como conjuntos diminutos» es gratis?
Sí — el texto completo de «Bitmasks como conjuntos diminutos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Bitmasks como conjuntos diminutos»?
Represente subconjuntos como enteros Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Bitmasks como conjuntos diminutos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- AND, OR, XOR y desplazamientos
- Establezca, borre y alterne un bit
- Cuente bits y el bit activado más bajo
- Bitmasks como conjuntos diminutos