Sesión 43: Cracking the Coding Interview (Capítulo 5, Parte 1) — Bit Manipulation: Fundamentos y Trucos Binarios#

Navegación rápida:

• ← Sesión 42: Grokking Cap. 9 (Parte 3) & CTCI 8.13 — Secuencias y Matrices DP
• Sesión 44: CTCI Ch5 — Bit Manipulation Avanzada: Inversión, Siguiente Número y Conversión →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_43.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión inauguramos el bloque de Manipulación de Bits a Nivel de Registro. En el hardware real, la memoria no almacena objetos de alto nivel ni estructuras complejas, sino secuencias de voltajes discretos agrupados en palabras de 32 o 64 bits. Consulta el Glosario Maestro y la Guía de Diagramas.

Registro de CPU y Nivel de Silicio#

• (a) En palabras simples (intuición): Imagina un casillero físico de alta velocidad dentro del cerebro del procesador. En lugar de mandar a un empleado al almacén (la memoria RAM) a buscar un dato, el procesador tiene una bandeja metálica justo sobre su mesa de trabajo con capacidad para 32 o 64 interruptores de luz (bits). Trabajar directamente en estos interruptores toma menos de un nanosegundo.
• (b) Definición técnica paso a paso: Unidad de almacenamiento volátil ultrarrápida integrada en el silicio de la CPU (arquitecturas x86_64, ARM64, RISC-V). Los registros de propósito general (como RAX, RBX, X0) tienen un ancho de palabra nativo (32 o 64 bits). Las instrucciones aritmético-lógicas operan directamente sobre registros en un único ciclo de reloj (< 0.3 ns).
• (c) Cómo funciona en Rust (memoria y tipos): Los tipos primitivos como u32, i32, u64, usize se cargan directamente en los registros del procesador. No se ubican en el Heap ni sufren indirección por punteros; viajan por el Stack o directamente en registros según las convenciones de llamada ABI del sistema.
• (d) Error típico de Junior: Asumir que una operación aritmética o de bits necesita memoria Heap; los enteros primitivos en Rust se copian por valor trivialmente (Copy) y residen en registros/Stack.

Operadores Bitwise Básicos (&, |, ^, ~, <<, >>)#

• (a) En palabras simples (intuición): Son interruptores lógicos que trabajan en paralelo sobre cada cable del bus binario:
• AND (&): Solo pasa corriente si ambos cables están activos (intersección).
• OR (|): Pasa corriente si al menos un cable está activo (unión).
• XOR (^): Pasa corriente si exactamente uno de los cables está activo, pero se apaga si ambos son iguales (diferencia estricta / detector de cambios).
• NOT (~ / !): Invierte la señal; si estaba apagado se enciende y viceversa.
• Left Shift (<<): Desplaza todos los interruptores hacia la izquierda, rellenando con ceros a la derecha (equivale a duplicar el valor por cada salto).
• Right Shift (>>): Desplaza hacia la derecha (equivale a dividir por 2 en cada salto).
• (b) Definición técnica paso a paso: Operaciones booleanas vectorizadas a nivel de bit evaluadas por la ALU (Unidad Aritmético-Lógica) en un único ciclo (O(1) tiempo y O(1) espacio). Rust utiliza ! como operador unario de negación de bits para enteros (!x), a diferencia de C/Python que utilizan ~x.
• (c) Cómo funciona en Rust (memoria y tipos): Rust verifica en modo debug desbordamientos en desplazamientos: desplazar un u32 por 32 o más (x << 32) causa pánico en ejecución o error en compilación (attempt to shift left by 32_i32, which would overflow). En modo release, Rust emite la instrucción de ensamble nativa (shl, shr).
• (d) Error típico de Junior: Olvidar que en Rust el operador NOT a nivel de bits es !n y no ~n. Confundir && (AND lógico de cortocircuito booleano) con & (AND bitwise numérico).

Complemento a Dos (Two's Complement)#

• (a) En palabras simples (intuición): Es un truco matemático genial inventado para que el procesador no necesite circuitos separados para restar. En lugar de restar A - B, la CPU suma A + (-B). Para convertir un número positivo en negativo, inviertes todos sus interruptores y le sumas 1 al final.
• (b) Definición técnica paso a paso: Sistema matemático para representar enteros con signo en binario. Dado un entero x, su opuesto aditivo -x se define como:

El bit más significativo (MSB) actúa como indicador de signo (0 positivo, 1 negativo). Permite que la suma de x + (-x) = x + (!x + 1) = (x + !x) + 1 = (2^N - 1) + 1 = 2^N ≡ 0 ±od{2^N}.

• (c) Cómo funciona en Rust (memoria y tipos): Rust expone métodos explícitos para trabajar con desbordamiento en complemento a dos: wrapping_neg(), wrapping_add(), saturating_add(), y overflowing_add(). En tipos sin signo (u32), la negación directa -x está prohibida por el compilador, requiriendo x.wrapping_neg().
• (d) Error típico de Junior: Intentar escribir -num cuando num es de tipo u32. El compilador de Rust rechaza cannot apply unary operator '-' to type 'u32'. Debe usarse num.wrapping_neg().

Algoritmo de Brian Kernighan (n & (n - 1))#

• (a) En palabras simples (intuición): Es como una goma de borrar mágica que localiza el último 1 encendido en la derecha del número y lo apaga en un solo movimiento, sin tener que revisar los demás bits uno por uno.
• (b) Definición técnica paso a paso: Identidad algebraica bitwise. Al restar 1 a un número binario, su bit 1 menos significativo se apaga a 0 y todos los bits a su derecha (que eran 0) se convierten en 1s. Al calcular la conjunción lógica n & (n - 1), el bit 1 menos significativo se anula a cero limpiamente:

Permite contar bits encendidos (Hamming Weight) en O(k) pasos, donde k es la cantidad de 1s, en lugar de iterar por los 32 bits.

• (c) Cómo funciona en Rust (memoria y tipos): Aunque el algoritmo manual se programa con un bucle while n != 0 { n &= n - 1; count += 1; }, Rust provee el método intrínseco n.count_ones(), el cual el compilador LLVM mapea directamente a la instrucción nativa de hardware POPCNT (Population Count) en procesadores x86_64 modernos.
• (d) Error típico de Junior: En lenguajes como Python, olvidar que los enteros no tienen límite de 32 bits; en Python n & (n - 1) con números negativos entra en bucle infinito si no se aplica una máscara de 32 bits (& 0xFFFFFFFF).

Propiedad Involutiva y Cancelativa de XOR (x oplus x = 0)#

• (a) En palabras simples (intuición): Es como presionar dos veces el interruptor de encendido de una lámpara: la primera vez la enciende y la segunda la vuelve a dejar apagada. Si tienes muchos pares de gemelos idénticos y una sola persona solitaria en una fiesta, el interruptor XOR cancela a todas las parejas y deja al descubierto a la persona solitaria.
• (b) Definición técnica paso a paso: Propiedades algebraicas del grupo conmutativo de XOR:

1. Identidad: x oplus 0 = x
2. Elemento inverso (autoinverso): x oplus x = 0
3. Conmutativa y Asociativa: a oplus b oplus a = (a oplus a) oplus b = 0 oplus b = b.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa limpiamente sobre iteradores con .fold(0, |acc, &x| acc ^ x). No genera ninguna asignación en memoria Heap.
• (d) Error típico de Junior: Usar una tabla Hash (HashSet o HashMap) para encontrar un elemento único en un array duplicado, gastando O(N) memoria extra cuando XOR resuelve el problema en O(1) espacio auxiliar.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

Las 4 Operaciones Atómicas de CTCI Capítulo 5#

En cualquier entrevista que involucre manipulación de bits, estas cuatro operaciones deben salir de memoria muscular:

1. get_bit(num, i): ¿El bit en la posición i es 0 o 1? - Desplazamos el bit deseado hasta la posición del extremo derecho (posición 0): (num >> i). - Aislamos el bit con una máscara de 1: (num >> i) & 1.
2. set_bit(num, i): Encender el bit en la posición i a 1 sin alterar los demás. - Creamos una máscara con un único 1 en la posición i: (1 << i). - Aplicamos unión lógica OR: num | (1 << i).
3. clear_bit(num, i): Apagar el bit en la posición i a 0 sin alterar los demás. - Creamos una máscara con un único 0 en la posición i y 1s en todos los demás lugares: !(1 << i). - Aplicamos intersección lógica AND: num & !(1 << i).
4. update_bit(num, i, val): Asignar un valor específico (0 o 1) al bit i. - Primero limpiamos el bit i a 0: num & !(1 << i). - Luego desplazamos el valor deseado a la posición i y unimos con OR: ... | ((val as u32) << i).

Inserción de Bits: CTCI 5.1 (Paso a Paso)#

Problema: Tienes dos números de 32 bits, N y M, y dos posiciones de bit, i y j. Inserta M dentro de N de modo que M comience en el bit j y termine en el bit i. Se asume que j ≥ i y que M cabe holgadamente.

Ejemplo:

• N = 10000000000₂ (1024₁₀)
• M = 10011₂ (19₁₀)
• i = 2, j = 6
• Resultado esperado: 10001001100₂ (1100₁₀)

Proceso de Construcción de la Máscara:#

Para no alterar los bits de N que están fuera del rango [i, j], necesitamos una máscara que tenga ceros exactamente en el intervalo [i, j] y unos en todas las demás posiciones.

1. Calcular la longitud de la ventana:
   window_len = j - i + 1 = 6 - 2 + 1 = 5 bits
2. Crear una tira de 1s del tamaño de la ventana:
   (1 ll 5) - 1 = 32 - 1 = 31 = 0000011111₂
3. Desplazar esa tira a la posición de inicio i = 2:
   0000011111₂ ll 2 = 0001111100₂
4. Invertir los bits para crear la máscara de limpieza:
   mask = !(0001111100₂) = 1110000011₂
5. Limpiar el espacio en N:
   N_{cleared} = N & mask = 10000000000₂ & 111110000011₂ = 10000000000₂
6. Desplazar M a la posición i y fusionar:
   M ll 2 = 10011₂ ll 2 = 1001100₂
   Resultado = N_{cleared} | (M ll 2) = 10001001100₂ = 1100₁₀

Brian Kernighan vs Instrucción de Hardware POPCNT#

¿Por qué n & (n - 1) borra el bit menos significativo en 1?

Tomemos n = 12 = 1100₂:

• n = 1100₂
• n - 1 = 1011₂ (el 1 en la posición 2 se convirtió en 0, y los ceros inferiores se convirtieron en 1s).
• n & (n - 1) = 1100₂ & 1011₂ = 1000₂ = 8₁₀.
• ¡El bit 1 menos significativo desapareció en una sola operación!

En la siguiente iteración:

• n = 1000₂
• n - 1 = 0111₂
• n & (n - 1) = 1000₂ & 0111₂ = 0000₂ = 0.
• El bucle termina tras 2 iteraciones, exactamente los dos bits en 1 que tenía el número.

En Rust, cuando compilas con optimizaciones (--release), u32::count_ones() compila directamente a:

popcnt eax, edi

Esta instrucción de hardware ejecuta el conteo en un único ciclo de reloj en CPUs x86 con soporte SSE4.2+.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Transición de Estados#

Consulta el diagrama vectorial:

flowchart TD
    START["Inicio: n"] --> IS_ZERO{"¿n == 0?"}
    IS_ZERO -->|Sí| END["Fin: Retornar count"]
    IS_ZERO -->|No| KERNIGHAN["n = n & (n - 1)<br/>(Apaga el bit 1 menos significativo)"]
    KERNIGHAN --> INC["count += 1"]
    INC --> IS_ZERO

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Registros CPU)#

Veamos el comportamiento de los registros durante la ejecución de insertion(1024, 19, 2, 6):

STACK / REGISTROS (Convención x86_64 ABI):
RDI (n):          0b0000_0000_0000_0000_0000_0100_0000_0000 (1024)
RSI (m):          0b0000_0000_0000_0000_0000_0000_0001_0011 (19)
RDX (i):          2
RCX (j):          6

PASO 1: window_len = j - i + 1 = 5
PASO 2: (1 << window_len) - 1 = 0b0001_1111 (31)
PASO 3: mask_zeros = 0b0001_1111 << 2 = 0b0111_1100
PASO 4: mask = !mask_zeros = 0b1111_1111_..._1000_0011
PASO 5: n_cleared = n & mask = 0b0100_0000_0000 (bits [2..6] garantizados en 0)
PASO 6: m_shifted = m << 2   = 0b0000_0100_1100
PASO 7: RAX = n_cleared | m_shifted:
        0b0100_0000_0000
      | 0b0000_0100_1100
      ------------------
      = 0b0100_0100_1100 (1100 en base 10)
Retorno en registro RAX: 1100 (0 bytes asignados en Heap).

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Precedencia de Operadores Bitwise frente a Operadores Aritméticos#

• El error: Escribir 1 << i + 1 pensando que se evalúa como (1 << i) + 1.
• Por qué falla: En Rust, C y Java, el operador de suma + tiene mayor precedencia que el operador de desplazamiento <<. Por tanto, 1 << i + 1 se evalúa como 1 << (i + 1).
• La solución: Encierra siempre entre paréntesis cada expresión bitwise:

  let mask = (1 << i) + 1; // Correcto y sin ambigüedad

Trampa 2: Desbordamiento en Desplazamientos Mayores o Iguales a 32 Bits#

• El error: Escribir 1u32 << 32 para generar una máscara completa de 32 unos.
• Por qué falla: En arquitecturas x86 y ARM, la instrucción de desplazamiento solo lee los últimos 5 bits del número de desplazamiento (k ±od{32}). Desplazar por 32 equivale a desplazar por 0 (1 << 0 = 1). Además, en Rust en modo debug esto provoca un pánico por overflow.
• La solución: Validar explícitamente si el desplazamiento es ≥ 32:

  let mask = if window_len >= 32 { 0u32 } else { !(((1u32 << window_len) - 1) << i) };

Trampa 3: Asumir que el Operador NOT en Rust es ~#

• El error: Escribir ~mask en Rust como se hace en C, C++, Java o Python.
• Por qué falla: En Rust, el símbolo ~ fue reservado antiguamente y no es un operador válido. El operador NOT a nivel de bits en Rust es el signo de exclamación !:

  let inverted = !num; // Invierte todos los bits de num

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_43.rs)#

/// CTCI 5.1: Inserción de M en N entre las posiciones de bit j e i (j >= i).
pub fn insertion(n: u32, m: u32, i: u32, j: u32) -> u32 {
    if j < i || j >= 32 {
        return n;
    }
    let window_len = j - i + 1;
    let mask = if window_len >= 32 {
        0u32
    } else {
        !(((1u32 << window_len) - 1) << i)
    };
    let n_cleared = n & mask;
    let m_masked = if window_len >= 32 {
        m
    } else {
        m & ((1u32 << window_len) - 1)
    };
    n_cleared | (m_masked << i)
}

/// LeetCode 191: Conteo de bits en 1 con Algoritmo de Brian Kernighan.
pub fn count_one_bits_kernighan(mut n: u32) -> u32 {
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    count
}

/// LeetCode 338: Counting Bits con Programación Dinámica Bitwise.
pub fn count_bits_dp(n: usize) -> Vec<usize> {
    let mut ans = vec![0usize; n + 1];
    for i in 1..=n {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    ans
}

/// LeetCode 136: Single Number mediante XOR.
pub fn single_number(nums: &[i32]) -> i32 {
    nums.iter().fold(0, |acc, &x| acc ^ x)
}

/// LeetCode 268: Missing Number mediante XOR en rango [0..n].
pub fn missing_number(nums: &[usize]) -> usize {
    let n = nums.len();
    let mut missing = n;
    for (i, &num) in nums.iter().enumerate() {
        missing ^= i ^ num;
    }
    missing
}

Implementación de Referencia en Python (practica/dia_43_bit_manipulation_fundamentos.py)#

from typing import List


def insertion(n: int, m: int, i: int, j: int) -> int:
    """CTCI 5.1: Inserción de M en N entre los bits j e i."""
    window_len = j - i + 1
    mask = ~(((1 << window_len) - 1) << i)
    n_cleared = n & mask
    m_masked = m & ((1 << window_len) - 1)
    return n_cleared | (m_masked << i)


def count_one_bits(n: int) -> int:
    """LeetCode 191: Hamming Weight con Brian Kernighan."""
    n = n & 0xFFFFFFFF
    count = 0
    while n != 0:
        n &= (n - 1)
        count += 1
    return count


def count_bits(n: int) -> List[int]:
    """LeetCode 338: DP con bits O(N)."""
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans


def single_number(nums: List[int]) -> int:
    """LeetCode 136: Elemento único usando XOR."""
    unique = 0
    for num in nums:
        unique ^= num
    return unique


def missing_number(nums: List[int]) -> int:
    """LeetCode 268: Número faltante usando XOR."""
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Inserción que Ocupa la Palabra Completa (i = 0, j = 31): - Prueba insertion(n, m, 0, 31). Verifica que toda la palabra de N se borra y queda reemplazada por M. Asegúrate de que el código no cause desbordamiento de desplazamiento 1 << 32.
2. Paso Límite 2: Potencia de 2 en Números Negativos: - En complemento a dos, el valor mínimo con signo i32::MIN (-2147483648, 0x80000000) tiene un único bit en 1. Explica por qué n > 0 es crucial en la verificación de potencias de 2.
3. Paso Límite 3: Inversión de Bits (LeetCode 190): - Diseña un algoritmo que invierta el orden de los 32 bits de un u32 (el bit 0 pasa al bit 31, etc.) utilizando máscaras de división y conquista (0x55555555, 0x33333333, 0x0F0F0F0F) en O(1) operaciones fijas.

Navegación final:

• ← Sesión 42: Grokking Cap. 9 (Parte 3) & CTCI 8.13 — Secuencias y Matrices DP
• Sesión 44: CTCI Ch5 — Bit Manipulation Avanzada: Inversión, Siguiente Número y Conversión →
• Glosario Maestro
• Guía de Diagramas de Arquitectura