Counting Bits

Q: ¿Existe 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 mayor o igual que 1. Para 12 ( 1100 ), 12 & 11 es 8 ( 1000 ), que tiene un 1, así que 12 tiene dos.

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

Llamar a uno para cada número, como Integer.bitCount en Java o __builtin_popcount en C y C++, da una respuesta correcta. Los entrevistadores suelen pedir la versión sin ello, porque el objetivo del problema es reutilizar respuestas que ya calculaste.

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

+10

Dado un número entero n que sea 0 o mayor, devuelve un arreglo de n+1 elementos donde el elemento i es el número de unos en la forma binaria de i, para cada i desde 0 hasta n.

Función

countBits(n: integer) → integer-array

ninteger: el último número que se cuenta, 0 o más
Devuelveinteger-array: un arreglo de n+1 conteos, 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: 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; 4 es 100, con uno. Con 0, 1 y 2 del primer ejemplo, los recuentos son 0, 1, 1, 2, 1, 2.

Para ir más allá

¿Puedes llenar todo el arreglo en tiempo O(n), sin una función integrada que cuente 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 cada número desde cero repite trabajo: 13 es 1101, los bits de 6 (110) con un dígito más al final. Completa las respuestas en orden creciente y cada entrada reutiliza una más pequeña con una suma.

Cuenta los bits de cada número

Intuición

Cuenta directamente cada bit 1 de un número: suma x & 1 a un contador, desplaza x un lugar a la derecha y detente en 0. Para 13 (1101), los bits son 1, 0, 1, 1, así que el recuento es 3.

Un número hasta n tiene aproximadamente log2 n dígitos binarios, así que la ejecución es O(n log n): unos 20,000 × 15 = 300,000 pasos para n = 2 × 10^4.

Algoritmo

Inicia una lista de resultados vacía.
Para cada i desde 0 hasta 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, y i & 1 es ese dígito. Así que i tiene los unos de i >> 1 más su último dígito: bits[i] = bits[i >> 1] + (i & 1).

Para todo i mayor o igual que 1, i >> 1 es menor que i, así que rellenar el arreglo de izquierda a derecha, empezando por bits[0] = 0, significa que la entrada que lees siempre está lista. Para n = 5: 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: tiempo O(n) y sin memoria adicional aparte de la salida.

Algoritmo

Crea un array bits de n+1 ceros. bits[0] se mantiene en 0.
Para i de 1 a 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

Devolver n elementos en lugar de n+1. Para n = 0, la respuesta es [0].
Precedencia de operadores. En Python, C, Java y JavaScript, + tiene mayor precedencia que &, así que bits[i >> 1] + i & 1 significa (bits[i >> 1] + i) & 1. Conserva 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 arreglos empiezan en 1, así que el recuento para i está en el índice i+1 y la consulta para i >> 1 está en floor(i/2) + 1. Lua 5.1 no tiene operador de desplazamiento, así que divide entre dos usando math.floor(i / 2).

Preguntas frecuentes3

¿Cuál es la complejidad temporal de contar 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 por separado lleva O(n log n). Ambas usan O(1) de memoria además del arreglo de salida.

¿Existe 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 mayor o igual que 1. Para 12 (1100), 12 & 11 es 8 (1000), que tiene un 1, así que 12 tiene dos.

¿Puedo usar una función popcount integrada?

Llamar a uno para cada número, como Integer.bitCount en Java o __builtin_popcount en C y C++, da una respuesta correcta. Los entrevistadores suelen pedir la versión sin ello, porque el objetivo del problema es reutilizar respuestas que ya calculaste.

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

Prueba #1

Prueba #2

Argumento

n = 2

Salida Esperada

[0, 1, 1]