Contar bits, número ausente e invertir bits

El problema Counting Bits (LeetCode 338) plantea lo siguiente: dado n, devuelva un array ans de tamaño n+1, donde ans[i] es la cantidad de bits iguales a 1 en i. El enfoque ingenuo es O(n log n), ya que cuenta los bits de cada número por separado. El enfoque de DP es O(n), porque aprovecha la relación entre i y su mitad o su bit establecido menos significativo.

Dos observaciones clave sustentan la DP: (1) i >> 1 elimina el bit menos significativo, por lo que bits[i] = bits[i >> 1] + (i & 1). (2) Al borrar el bit establecido menos significativo: bits[i] = bits[i & (i-1)] + 1. Ambos enfoques ofrecen un tiempo O(n) y un espacio O(n) para el array de salida.

Para la recurrencia de desplazamiento a la derecha dp[i] = dp[i >> 1] + (i & 1): dividir entre 2 mediante un desplazamiento a la derecha elimina el último bit. Si el último bit era 1, el conteo aumenta en 1; si era 0, no cambia. Por tanto, bits[i] = bits[i // 2] + (i mod 2).

Para la recurrencia del bit establecido menos significativo dp[i] = dp[i & (i-1)] + 1: i & (i-1) borra el bit 1 situado más a la derecha, por lo que tiene un bit establecido menos que i. Por tanto, el conteo es el conteo de ese valor reducido más 1. Ambas recurrencias procesan i en orden creciente, de modo que los subproblemas más pequeños siempre se resuelven primero.

El problema Missing Number (LeetCode 268) proporciona un array de n números distintos en [0, n], con exactamente uno ausente. El enfoque con XOR: aplique XOR a todos los índices de 0..n y a todos los valores del array. Los pares se cancelan y queda el número que falta. El enfoque con suma: expected = n*(n+1)//2; devuelva expected - sum(nums).

Ambos enfoques tienen un tiempo O(n) y un espacio O(1). El enfoque con XOR es más robusto en lenguajes con enteros de ancho fijo, ya que evita posibles desbordamientos. En Python, ambos funcionan correctamente porque los enteros tienen precisión arbitraria.

El problema Reverse Bits (LeetCode 190) le pide invertir la representación binaria de un entero sin signo de 32 bits. El enfoque iterativo procesa cada uno de los 32 bits de la entrada, de derecha a izquierda, y los coloca en la salida de izquierda a derecha. En cada iteración, extraiga el bit situado más a la derecha con n & 1, desplace la salida a la izquierda para hacer sitio, aplique OR al bit y, después, desplace n a la derecha.

Después de 32 iteraciones, el entero de salida contiene los 32 bits de n en orden inverso. Esto es O(32) = O(1) por llamada, o O(1) amortizado con almacenamiento en caché para llamadas repetidas sobre bloques de 8 bits.

Un enfoque más rápido, O(log 32) = O(1), invierte los bits mediante un intercambio de divide y vencerás. Primero intercambia los bits adyacentes; después, los grupos adyacentes de 2 bits; luego, los grupos de 4 bits; y así sucesivamente. Cada nivel de intercambio utiliza máscaras para separar grupos alternos y desplazamientos para entrelazarlos. Después de 5 intercambios, los 32 bits quedan invertidos.

Este enfoque utiliza un número fijo de operaciones O(1), independientemente de la entrada, y se usa en implementaciones de hardware. Las máscaras son constantes: 0x55555555 (patrón alterno 01), 0x33333333 (patrón alterno 0011), 0x0f0f0f0f (patrón alterno 00001111), etc.

El problema Number of 1 Bits (LeetCode 191) pide calcular el peso de Hamming (popcount) de un entero sin signo. Hay tres enfoques con distintas ventajas y desventajas: un bucle ingenuo (O(32)), el método de Brian Kernighan (O(k), donde k = cantidad de bits establecidos) y el método integrado de Python n.bit_count() (3.10 o posterior).

El método de Brian Kernighan es el preferido en las entrevistas porque demuestra que comprende el truco n & (n-1). Cada iteración elimina el bit establecido menos significativo, por lo que el bucle se ejecuta exactamente tantas veces como bits 1 haya; esto es mucho más rápido que recorrer los 32 bits completos en enteros dispersos.

A veces necesita contar rápidamente los bits 1 de un intervalo [l, r]. Construya una suma de prefijos de bits establecidos para 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Después, el conteo del intervalo [l, r] es prefix[r] - prefix[l-1]. Esto permite realizar consultas de intervalos en O(1) después de un preprocesamiento O(n).

Esta técnica se generaliza a cualquier agregado basado en bits sobre un intervalo. Por ejemplo, para contar los números de [l, r] que tienen una cantidad par de bits establecidos, se utiliza la misma técnica de prefijos, pero con una función de acumulación diferente.

En Python, los enteros tienen signo y un ancho arbitrario. Al invertir bits para el problema de LeetCode, debemos tratar la entrada como un entero sin signo de 32 bits. Aplique la máscara & 0xFFFFFFFF a la entrada antes de procesarla para asegurarse de que solo se consideren 32 bits. La salida también debe ser un entero sin signo de 32 bits, es decir, no negativo.

Si recibe un entero de Python que puede ser negativo, en el sentido de complemento a dos, aplique primero & 0xFFFFFFFF para obtener la representación sin signo de 32 bits y después inviértala. El resultado siempre es un entero no negativo entre 0 y 2^32 - 1.

El problema de contar bits revela un patrón general de la DP de bits: si conoce la respuesta para una versión más pequeña de i, puede calcularla para i mediante una operación de bits de tiempo constante. Este patrón se generaliza a otros problemas de conteo de bits, como contar los números con exactamente k bits establecidos en [0, n] mediante enumeración binaria, o encontrar la mayor potencia de dos que divide cada número.

Otra observación útil es que la cantidad de bits establecidos de i sigue un patrón repetitivo dentro de cada intervalo de potencias de dos. El patrón para [2^k, 2^(k+1) - 1] es igual al de [0, 2^k - 1], con cada valor incrementado en 1, porque el bit k siempre está establecido en este intervalo.

Muchos problemas de entrevistas combinan el conteo de bits, la lógica de números que faltan y la inversión de bits en una sola pregunta. Por ejemplo: dado un array cuyos elementos son enteros de n bits y en el que falta uno, encuentre el valor que falta. O bien: dada una secuencia de conteos de bits, reconstruya el entero que falta. Estos problemas requieren reconocer qué subtécnica se aplica.

Practique la creación de un mapa mental: si un problema menciona encontrar elementos que faltan, piense en XOR o en la suma. Si dice «cuente los 1 de forma eficiente», piense en Kernighan o en DP. Si dice «invierta los bits», piense en el enfoque iterativo o en divide y vencerás. Estas son las tres herramientas fundamentales de la manipulación de bits en las entrevistas.

Para llamadas repetidas a la inversión de bits, por ejemplo, en una simulación de hardware, almacene en caché los resultados para bloques de 8 bits. Como cada byte solo puede tener 256 valores, precalcule el byte invertido para cada valor de 0 a 255. Para invertir un entero de 32 bits, divídalo en cuatro bloques de 8 bits, invierta cada uno y vuelva a ensamblarlos en orden inverso.

Esto reduce cada llamada a cuatro consultas de tabla y operaciones de bits, mucho más rápidas que un bucle de 32 iteraciones para el procesamiento masivo. La caché se construye una vez en un tiempo O(256 × 8) y se reutiliza para todas las llamadas posteriores en O(1).

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

En esta lección ha aprendido que el conteo de bits utiliza DP con dp[i] = dp[i >> 1] + (i & 1) o dp[i] = dp[i & (i-1)] + 1 para obtener un tiempo O(n); que el número que falta se resuelve en O(n)/O(1) aplicando XOR a todos los índices y todos los valores, o mediante la fórmula de la suma aritmética; y que la inversión de 32 bits se realiza de forma iterativa en O(32) o mediante la técnica de máscaras de divide y vencerás. A continuación exploraremos las pilas monótonas, empezando por la invariante creciente frente a decreciente y las consultas del siguiente elemento mayor.