Counting Bits

Q: ¿Por qué funciona bits[i] = bits[i >> 1] + (i & 1)?

i >> 1 es i sin su último dígito binario, y i & 1 es ese dígito eliminado. Los unos de i son los unos del número más corto más el último dígito. Para 11, que es 1011 , el número más corto es 5 ( 101 , dos unos) y el último dígito es 1, así que 11 tiene tres.

Q: ¿Hay otra recurrencia O(n) para contar bits?

Sí. i & (i-1) borra el bit 1 menos significativo de i , así que bits[i] = bits[i & (i-1)] + 1 para todo i igual o mayor que 1. Para 12 ( 1100 ), 12 & 11 es 8 ( 1000 ), que tiene un 1, así que 12 tiene dos. Es tan rápido como la regla de desplazamiento y utiliza el mismo relleno de izquierda a derecha.

Q: ¿Puedo usar una función popcount integrada?

La mayoría de los lenguajes tienen una, como Integer.bitCount en Java o __builtin_popcount en C y C++, y llamarla para cada número da una respuesta correcta. En las entrevistas suelen pedir la versión sin ella, porque el objetivo del problema es reutilizar respuestas que ya calculaste. La recurrencia también funciona en lenguajes que no tienen esa función.

FácilManipulación de bits Programación dinámica

+10

Se te da un número entero n que es 0 o mayor. Para cada número i de 0 a n, cuenta cuántos unos aparecen cuando i se escribe en binario. Devuelve los recuentos como un array de n+1 elementos, donde el elemento i es el recuento para el número i.

Función

countBits(n: integer) → integer-array

ninteger: el último número que se va a contar, 0 o más
Devuelveinteger-array: un arreglo de n+1 recuentos, donde la entrada i es el número de bits 1 en i

Restricciones

0 ≤ n ≤ 2 × 10⁴

Ejemplos

Entrada: n = 2
Salida: [0, 1, 1]
Explicación: En binario, 0 es 0, 1 es 1 y 2 es 10. Eso es ningún 1, después uno, después uno.

Entrada: n = 5
Salida: [0, 1, 1, 2, 1, 2]
Explicación: 3 es 11 y 5 es 101, dos unos cada uno, mientras que 4 es 100 con un solo 1. Con 0, 1 y 2 del primer ejemplo, los recuentos del 0 al 5 son 0, 1, 1, 2, 1, 2.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes llenar todo el arreglo en tiempo O(n), sin una función integrada que cuente los bits y sin contar cada número desde cero?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Contar los 1 de cada número por separado funciona, pero repite trabajo. 13 es 1101 y 6 es 110: los bits de 13 son los bits de 6 con un dígito más al final. Si completas las respuestas en orden creciente, el recuento que necesitas para i ya está en el arreglo, y cada entrada cuesta una suma.

Cuenta los bits de cada número

Intuición

Toma cada número de 0 a n y cuenta directamente sus bits 1. El bit menos significativo de x es x & 1. Súmalo a un contador y luego desplaza x a la derecha con x >> 1 para que el siguiente bit pase a ser el menos significativo. Detente cuando x llegue a 0.

Para 13, que es 1101, los bits se obtienen como 1, 0, 1, 1 de derecha a izquierda, así que el recuento es 3. Cada número requiere un paso por cada dígito binario, y un número de hasta n tiene aproximadamente log2 n dígitos.

Eso hace que el proceso completo sea O(n log n). Para n = 2 × 10^4 son unos 20,000 × 15 = 300,000 pasos, lo que se ejecuta a tiempo. Aun así, se desperdicia trabajo: contar 13 repite todos los pasos que ya hiciste para 6. El espacio es O(1), aparte del arreglo de salida.

Algoritmo

Inicia una lista de resultados vacía.
Para cada i de 0 a n, establece count en 0 y x en i.
Mientras x sea mayor que 0, suma x & 1 a count y desplaza x un bit a la derecha.
Añade count al resultado.
Devuelve el resultado.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Construye sobre la mitad del número

Intuición

Desplazar i un lugar a la derecha elimina su último dígito binario. Así que i tiene exactamente los bits 1 de i >> 1, más uno cuando su último dígito es 1. Ese último dígito es i & 1, lo que da la regla bits[i] = bits[i >> 1] + (i & 1).

Para cada i mayor o igual que 1, i >> 1 es menor que i. Si llenas el arreglo de izquierda a derecha, empezando con bits[0] = 0, la entrada que consultas ya está llena. Esto es programación dinámica: cada respuesta se construye a partir de una más pequeña.

Para n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Cada entrada requiere un desplazamiento, una operación AND y una suma, así que el tiempo es O(n) y no se necesita memoria aparte de la salida.

Algoritmo

Crea un arreglo bits de n+1 ceros. bits[0] permanece en 0.
Para i desde 1 hasta n, establece bits[i] en bits[i >> 1] + (i & 1).
Devuelve bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Errores comunes y casos límite

La regla cabe en una sola línea, así que los errores se esconden a su alrededor.

El array tiene n+1 entradas, no n. Para n = 0, la respuesta es [0]: una entrada, para el número 0.
Precedencia de operadores. En Python, C, Java y JavaScript, + tiene mayor prioridad que &, así que bits[i >> 1] + i & 1 se interpreta como (bits[i >> 1] + i) & 1. Mantén los paréntesis alrededor de (i & 1).
Consultar bits[i-1] en lugar de bits[i >> 1]. Los números vecinos no siguen una regla sencilla: 7 es 111, con tres 1, y 8 es 1000, con uno.
En Lua y R, los arrays empiezan en 1, así que el recuento para i está en el índice i+1 y la consulta para i >> 1 está en el índice floor(i/2) + 1. El Lua del ejecutor no tiene operador de desplazamiento, así que divide entre dos usando math.floor(i / 2).
Convertir cada número en una cadena binaria y contar los caracteres 1 da la respuesta correcta, pero crea una cadena nueva para cada número.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Counting Bits?

La mejor solución se ejecuta en tiempo O(n): cada una de las n+1 entradas proviene de una entrada anterior con una suma. Contar los bits de cada número uno por uno tarda O(n log n), porque un número de hasta n tiene aproximadamente log2 n dígitos binarios. Ambas usan O(1) de memoria adicional a la matriz de salida.

¿Por qué funciona bits[i] = bits[i >> 1] + (i & 1)?

i >> 1 es i sin su último dígito binario, y i & 1 es ese dígito eliminado. Los unos de i son los unos del número más corto más el último dígito. Para 11, que es 1011, el número más corto es 5 (101, dos unos) y el último dígito es 1, así que 11 tiene tres.

¿Hay otra recurrencia O(n) para contar bits?

Sí. i & (i-1) borra el bit 1 menos significativo de i, así que bits[i] = bits[i & (i-1)] + 1 para todo i igual o mayor que 1. Para 12 (1100), 12 & 11 es 8 (1000), que tiene un 1, así que 12 tiene dos. Es tan rápido como la regla de desplazamiento y utiliza el mismo relleno de izquierda a derecha.

¿Puedo usar una función popcount integrada?

La mayoría de los lenguajes tienen una, como Integer.bitCount en Java o __builtin_popcount en C y C++, y llamarla para cada número da una respuesta correcta. En las entrevistas suelen pedir la versión sin ella, porque el objetivo del problema es reutilizar respuestas que ya calculaste. La recurrencia también funciona en lenguajes que no tienen esa función.

Python

def countBits(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

n = 2

Esperado

[0, 1, 1]