0Pricing
DSA Interview Prep · Lección

Máscaras de bits: establecer, borrar, alternar y comprobar

Implemente funciones auxiliares para establecer, borrar, alternar y comprobar bits individuales, y aplique máscaras de bits para representar subconjuntos en problemas de enumeración de subconjuntos.

Máscaras de bits: establecer, borrar, alternar y comprobar es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.

Qué son las máscaras de bits

Una máscara de bits es un entero que se utiliza para seleccionar, modificar o comprobar bits específicos de otro entero. La máscara contiene unos en las posiciones que le interesan y ceros en las demás. Combinadas con operadores bit a bit, las máscaras permiten realizar operaciones precisas sobre bits sin afectar a los demás.

Las cuatro operaciones fundamentales con máscaras son: establecer (activar un bit), borrar (desactivar un bit), alternar (invertir un bit) y comprobar (verificar si un bit vale 1). Cada una utiliza un operador diferente — OR, AND-NOT, XOR y AND, respectivamente — con la máscara 1 << k.

# The four fundamental bit mask operations
def set_bit(n, k):    return n | (1 << k)       # OR to set
def clear_bit(n, k):  return n & ~(1 << k)      # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k)       # XOR to toggle
def check_bit(n, k):  return (n >> k) & 1       # shift+AND to check

n = 0b10110101  # 181
print(f'n = {bin(n)}')
print(f'set   bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')

Establecer un bit: activar un bit

Para establecer el bit k (forzarlo a 1 independientemente de su valor actual), aplique OR al número con la máscara 1 << k. Como 0 OR 1 = 1 y 1 OR 1 = 1, el bit objetivo pasa a valer 1. A todos los demás bits se les aplica OR con 0, lo que los deja sin cambios.

Establecer un bit es una operación idempotente: llamarla varias veces produce el mismo efecto que llamarla una sola vez. Si el bit k ya vale 1, el resultado no cambia. Esta propiedad es importante para gestionar indicadores cuando desea activar una funcionalidad sin preocuparse por su estado actual.

def set_bit(n, k):
    mask = 1 << k
    return n | mask

# Set various bits
n = 0b00001010  # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
    result = set_bit(n, k)
    print(f'Set bit {k}: {bin(result)} = {result}')

# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')

# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4)  # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')

Borrar un bit: desactivar un bit

Para borrar el bit k (forzarlo a 0 independientemente de su valor actual), aplique AND al número con el complemento de la máscara: n & ~(1 << k). El complemento ~(1 << k) tiene todos los bits establecidos en 1 salvo el bit k, que vale 0. Aplicar AND con 0 fuerza el bit objetivo a 0; aplicar AND con 1 conserva todos los demás bits.

Al igual que establecer, borrar es una operación idempotente. Borrar un bit que ya vale 0 no modifica el número. En Python, ~(1 << k) funciona correctamente para cualquier k porque Python gestiona automáticamente la extensión de signo: conceptualmente, el complemento tiene todos los bits superiores establecidos en 1.

def clear_bit(n, k):
    mask = ~(1 << k)     # all 1s except bit k
    return n & mask

n = 0b11111111  # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
    result = clear_bit(n, k)
    print(f'Clear bit {k}: {bin(result)} = {result}')

# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
    mask = 0
    for k in positions:
        mask |= (1 << k)
    return n & ~mask

result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}')  # 0b01010101 = 85

Alternar un bit: invertir un bit

Para alternar el bit k (cambiarlo de 0 a 1 o de 1 a 0), aplique XOR al número con la máscara 1 << k. Aplicar XOR con 1 invierte el bit; aplicar XOR con 0 lo deja sin cambios. Esta es la propiedad fundamental de XOR aplicada a un solo bit.

Alternar es la única de las cuatro operaciones que no es idempotente: llamarla dos veces devuelve el valor original. Esto la hace perfecta para funcionalidades que alternan entre dos estados, como un interruptor de encendido y apagado o un indicador booleano en una representación entera compacta.

def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b10101010  # 170
print(f'Original:    {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}')  # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}')  # on->off: 00101010

# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')

# Toggle all lower k bits
def toggle_lower_k(n, k):
    mask = (1 << k) - 1   # k ones in the lowest positions
    return n ^ mask

print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')

Comprobar un bit: verificar si está establecido

Para comprobar si el bit k está establecido, desplace n k posiciones a la derecha y aplique AND con 1: (n >> k) & 1. Esto lleva el bit k a la posición 0 y enmascara todos los bits superiores, dejando 0 (el bit k valía 0) o 1 (el bit k valía 1). Como alternativa, utilice bool(n & (1 << k)) para obtener un resultado True/False.

Comprobar un bit no es destructivo: no modifica n. Puede comprobar varios bits desplazando y enmascarando cada posición de forma independiente. Esta es la base para recorrer la representación binaria de un número, algo que se utiliza en la enumeración de subconjuntos y en la programación dinámica con estados representados mediante máscaras de bits.

def check_bit(n, k):
    return (n >> k) & 1

def is_bit_set(n, k):
    return bool(n & (1 << k))

n = 0b10110101  # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
    print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')

# Count set bits using check_bit
def count_set_bits(n):
    return sum(check_bit(n, k) for k in range(n.bit_length()))

print(f'\nSet bits in {n}: {count_set_bits(n)}')

# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
    return [check_bit(n, k) for k in range(width)]

print(f'Bit list (LSB first): {to_bit_list(n)}')

Máscaras de bits para representar subconjuntos

Un entero con n bits puede representar un subconjunto de un conjunto de n elementos: el bit k vale 1 si el elemento k pertenece al subconjunto y 0 en caso contrario. Esto comprime un subconjunto en un solo entero y permite operaciones O(1): comprobar la pertenencia (mask & (1 << k)), añadir un elemento (mask | (1 << k)), eliminar un elemento (mask & ~(1 << k)) y calcular la unión o intersección de conjuntos (mask1 | mask2 y mask1 & mask2).

Con n elementos hay 2^n subconjuntos posibles, cada uno representado de forma única por un entero de n bits entre 0 y 2^n - 1. Recorrer todos los enteros del 0 al 2^n - 1 enumera todos los subconjuntos.

# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)

def subset_from_mask(mask):
    return [elements[k] for k in range(n) if (mask >> k) & 1]

# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n):   # 0 to 15 for n=4
    print(f'  {mask:04b}: {subset_from_mask(mask)}')

# Set operations
mask_ab = 0b0011   # {A, B}
mask_bc = 0b0110   # {B, C}
print(f'\nUnion:        {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')

Recorrer todos los subconjuntos de una máscara

En la programación dinámica con máscaras de bits, a menudo es necesario recorrer todos los subconjuntos de una máscara determinada. Un truco habitual consiste en comenzar con sub = mask y actualizar mediante sub = (sub - 1) & mask hasta que sub llegue a 0. Cada iteración produce una submáscara diferente. El coste total para todas las máscaras es O(3^n), porque cada elemento puede estar en la máscara exterior pero no en la submáscara, en ambas o en ninguna.

Esta técnica aparece en problemas como «dividir un array en subconjuntos con el mismo XOR» o «encontrar el AND máximo de cualquier subconjunto». La capacidad de enumerar submáscaras de forma eficiente es característica de la programación dinámica avanzada con máscaras de bits.

def all_submasks(mask):
    submasks = []
    sub = mask
    while sub > 0:
        submasks.append(sub)
        sub = (sub - 1) & mask
    submasks.append(0)  # empty subset
    return submasks

mask = 0b1011   # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'

print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
    print(f'  {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')

DP con máscaras de bits: vista previa del problema del viajante

La DP con máscaras de bits resuelve problemas cuyo estado incluye un subconjunto de elementos visitados. El ejemplo clásico es el problema del viajante (TSP): encontrar el recorrido de coste mínimo que visite n ciudades. El estado es dp[mask][city] = coste mínimo para visitar las ciudades de mask y terminar en city. Con n ciudades, hay 2^n × n estados, lo que da un tiempo O(n^2 × 2^n), viable para n ≤ 20.

La máscara actúa como un conjunto comprimido de elementos visitados. Establecer, borrar y comprobar bits corresponde a visitar, abandonar y consultar ciudades. Este es el núcleo de la DP con máscaras de bits: usar bits como un conjunto compacto para el estado.

# TSP with bitmask DP
import sys

def tsp(dist):
    n = len(dist)
    INF = float('inf')
    # dp[mask][v] = min cost to reach v having visited cities in mask
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0   # start at city 0, only city 0 visited (mask=1=0b0001)

    for mask in range(1 << n):
        for v in range(n):
            if dp[mask][v] == INF: continue
            if not (mask >> v) & 1: continue  # v must be in mask
            for u in range(n):
                if (mask >> u) & 1: continue  # u must not be visited
                new_mask = mask | (1 << u)
                dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))

dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist))  # should be 80

Enmascaramiento de varios bits: extracción de un campo

A veces necesita extraer no solo un bit, sino también un campo de varios bits, es decir, un intervalo contiguo de bits. Para extraer los bits desde la posición start hasta start+length-1, cree una máscara de length bits consecutivos iguales a 1: mask = (1 << length) - 1; después, use (n >> start) & mask.

Esta técnica se utiliza al analizar formatos de enteros empaquetados, como direcciones IP, datos de píxeles o registros de hardware, en los que varios valores pequeños se almacenan en un solo entero. Por ejemplo, un píxel RGB565 de 16 bits almacena el rojo en los bits 15-11, el verde en 10-5 y el azul en 4-0.

def extract_field(n, start, length):
    mask = (1 << length) - 1   # e.g., length=3 => mask=0b111
    return (n >> start) & mask

# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000  # 63432
red   = extract_field(pixel, 11, 5)   # bits 15-11
green = extract_field(pixel, 5, 6)    # bits 10-5
blue  = extract_field(pixel, 0, 5)    # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red:   {red}   ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue:  {blue}  ({bin(blue)})')

# Packing values back
def pack_rgb565(r, g, b):
    return (r << 11) | (g << 5) | b

packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')

Máscaras de bits en problemas de entrevistas

Las máscaras de bits suelen aparecer en estos tipos de problemas de entrevistas:

  • Enumeración de subconjuntos: recorrer los 2^n subconjuntos usando máscaras de 0 a 2^n-1
  • DP de compresión de estados: codificar un conjunto de nodos o elementos visitados como una máscara de bits en el estado de la DP
  • Sistemas de permisos: combinar las banderas READ/WRITE/EXECUTE con OR y comprobarlas con AND
  • Seguimiento de celdas visitadas en una cuadrícula: en cuadrículas pequeñas, empaquetar las celdas visitadas en un solo entero

Un indicador clave de que las máscaras de bits son útiles es que el problema incluya un conjunto pequeño (n ≤ 20 elementos) y que necesite realizar un seguimiento de combinaciones de pertenencia. Para conjuntos más grandes se necesitan otras representaciones.

# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
    n = len(nums)
    for mask in range(1 << n):
        total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
        if total == target:
            subset = [nums[k] for k in range(n) if (mask >> k) & 1]
            print(f'Found subset {subset} summing to {target}')
            return True
    return False

subset_sum_exists([3, 1, 4, 1, 5], 10)  # finds a subset summing to 10

# Check if permutation covers all required elements (bitmask approach)
required = 0b11111  # need all 5 elements
visited  = 0b01101  # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}')  # False: missing bits 1 and 4

Trucos para enumerar bits de forma eficiente

Al recorrer los bits establecidos de una máscara, se utilizan dos técnicas habituales. El método de desplazamiento y comprobación: desplazar a la derecha y comprobar el LSB. El método de aislamiento del bit establecido menos significativo: aislar el bit establecido menos significativo con n & -n, procesarlo y después borrarlo con n &= n - 1. El segundo método solo visita los bits establecidos y es más rápido cuando la máscara es dispersa.

En Python, también puede usar bin(n).count('1') o n.bit_count() (3.10 o posterior) para calcular el popcount. Para obtener la posición de cada bit establecido, use n.bit_length() - 1 para el bit establecido de mayor posición.

# Iterate over set bit positions
def set_bit_positions(n):
    positions = []
    k = 0
    while n:
        if n & 1:
            positions.append(k)
        n >>= 1
        k += 1
    return positions

# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
    positions = []
    while n:
        lsb = n & -n           # isolate lowest set bit
        k = lsb.bit_length() - 1  # position of that bit
        positions.append(k)
        n &= n - 1             # clear lowest set bit
    return positions

mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast):  {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')

Comprobación rápida

Compruebe sus conocimientos sobre los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección ha aprendido que las cuatro operaciones fundamentales con máscaras de bits son establecer (OR), borrar (AND-NOT), alternar (XOR) y comprobar (shift-AND); que los enteros pueden representar subconjuntos, donde cada bit codifica la pertenencia de un elemento, lo que permite enumerar los 2^n subconjuntos; y que la extracción de campos de varios bits y la DP con máscaras de bits utilizan los mismos principios de enmascaramiento para codificar estados más complejos. A continuación exploraremos el conteo de bits, los números que faltan y la inversión de bits mediante las técnicas de esta lección y de la anterior.

Preguntas frecuentes

¿La lección «Máscaras de bits: establecer, borrar, alternar y comprobar» es gratis?

Sí — el texto completo de «Máscaras de bits: establecer, borrar, alternar y comprobar» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Máscaras de bits: establecer, borrar, alternar y comprobar»?

Implemente funciones auxiliares para establecer, borrar, alternar y comprobar bits individuales, y aplique máscaras de bits para representar subconjuntos en problemas de enumeración de subconjuntos. Practicas DSA Interview Prep 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 DSA Interview Prep?

No se requiere experiencia previa. DSA Interview Prep 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 3 de 4.

¿Cuánto tiempo toma la lección «Máscaras de bits: establecer, borrar, alternar y comprobar»?

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 DSA Interview Prep?

Sí. Cada lección de DSA Interview Prep 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

  1. Operadores bit a bit: AND, OR, XOR, NOT y desplazamientos
  2. Single Number y propiedades de XOR
  3. Máscaras de bits: establecer, borrar, alternar y comprobar
  4. Contar bits, número ausente e invertir bits
← Volver a DSA Interview Prep