Number of 1 Bits
Se te da un entero no negativo n. Escribe n en binario y devuelve cuántos de sus dígitos son 1. A este recuento también se le llama número de bits activados, recuento de población o peso de Hamming. Por ejemplo, 6 es 110 en binario, así que tiene dos bits 1.
Función
- ninteger
- un entero no negativo que cabe en un entero con signo de 32 bits
- Devuelveinteger
- el número de dígitos 1 en la forma binaria de n
Restricciones
0 ≤ n ≤ 231-1
Ejemplos
- Entrada
- n = 11
- Salida
- 3
- Explicación
- 11 es
1011en binario, que equivale a 8 + 2 + 1. Tres de sus cuatro dígitos binarios son 1, así que la respuesta es 3.
- Entrada
- n = 128
- Salida
- 1
- Explicación
- 128 es 2^7, escrito
10000000: un solo 1 seguido de ceros, así que la respuesta es 1.
- Entrada
- n = 2147483645
- Salida
- 30
- Explicación
- 2^31-1 = 2147483647 son treinta y un bits 1 seguidos. 2147483645 es ese número menos 2, lo que apaga el bit que vale 2 y deja 30 unos.
Para ir más allá
Si esta función se ejecutara millones de veces, ¿cómo podrías contar los bits de un número de 32 bits con cuatro consultas a una tabla de 256 recuentos precalculados?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Fíjate solo en el último dígito binario de
n. ¿Cómo puedes leerlo sin convertirnen una cadena, y cómo llevas después el siguiente dígito al último lugar?n & 1(on % 2) es el último bit, y un desplazamiento a la derecha de una posición (o una división por 2 redondeada hacia abajo) lo elimina. Suma los últimos bits hasta quensea 0.Para un bucle más corto, usa
n & (n-1): esncon su bit 1 menos significativo desactivado. Cuenta cuántas veces puedes aplicarlo antes de quenllegue a 0. Así, el bucle se ejecuta una vez por cada bit 1, en lugar de una vez por cada dígito binario.
Solución
Recorre los dígitos binarios de n sin crear una cadena. Leer el último bit y desplazarlo toma un paso por cada dígito binario, hasta 31. Borrar el bit 1 más bajo con n & (n-1) toma un paso por cada bit 1, exactamente tantos como el resultado.
Comprueba el último bit y desplázate a la derecha
Intuición
n & 1 es el último dígito binario de n: 1 cuando n es impar, 0 cuando es par. Súmalo al conteo. Después, n >> 1 elimina ese dígito y mueve el siguiente a la última posición; para un número no negativo, eso equivale a dividir entre 2 y redondear hacia abajo. Para 11, 1011, los últimos bits son 1, 1, 0 y 1 a medida que n disminuye hasta 0: tres bits 1.
El bucle se detiene cuando n es 0, así que nunca visita los ceros iniciales: aproximadamente log2(n) pasos, 8 para 128 y como máximo 31. Solo almacena n y el conteo.
Algoritmo
- Inicia un contador en 0.
- Mientras
nsea mayor que 0, suman & 1al contador. - Desplaza
nun bit a la derecha. - Cuando
nllegue a 0, devuelve el contador.
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countDesactiva el bit menos significativo establecido con n & (n-1)
Intuición
Restar 1 convierte el bit 1 más bajo en 0 y cada 0 que está por debajo de él en 1, y deja los bits de arriba sin cambios. Así que n & (n-1) conserva los bits superiores y borra el bit 1 más bajo: 12 es 1100, 11 es 1011, y 1100 & 1011 es 1000.
Cada paso elimina exactamente un bit 1, así que la respuesta es el número de pasos hasta que n sea 0. 128 requiere 1 paso en lugar de 8, aunque 2^31-1 sigue requiriendo 31. Lua 5.1 no tiene operadores de bits, así que su versión encuentra el bit 1 más bajo dividiendo por la mitad y lo resta; el bucle sigue ejecutándose una vez por cada bit 1.
Algoritmo
- Inicia un contador en 0.
- Mientras
nno sea 0, reemplazanporn & (n-1). - Suma 1 al contador después de cada reemplazo.
- Devuelve el contador.
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
Errores comunes y casos límite
- Repetir el bucle mientras
n > 1. El bucle se detiene antes del último bit 1 y devuelve 0 paran = 1. - Dividir con un número de punto flotante. En JavaScript, Lua y R,
11 / 2es 5.5 y los residuos que siguen son fracciones. Redondea hacia abajo conMath.floor,math.flooro%/%, o desplaza en su lugar. - Escribir
n & 1en Lua 5.1. No tiene operadores de bits, así que el código no se compila; usan % 2ymath.floor(n / 2).
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Number of 1 Bits?
El bucle de desplazamiento se ejecuta una vez por cada dígito binario: O(log n), como máximo 31 pasos en este caso. El bucle n & (n-1) se ejecuta una vez por cada bit 1: O(k), donde k es la respuesta. Ambos usan espacio adicional O(1).
¿Hay una función integrada que cuente los bits establecidos?
La mayoría de los lenguajes tienen uno, a menudo respaldado por una sola instrucción del procesador: Integer.bitCount en Java, __builtin_popcount en GCC, bits.OnesCount en Go, count_ones en Rust e int.bit_count en Python 3.10 y versiones posteriores. En una entrevista, escribe el bucle y menciona la función integrada.
¿Cuál es la diferencia entre el peso de Hamming y la distancia de Hamming?
El peso de Hamming de un número es la cantidad de dígitos binarios que son 1, que es lo que devuelve este problema. La distancia de Hamming entre dos números es la cantidad de posiciones de bits en las que difieren: cuenta los bits 1 de a ^ b, ya que XOR establece exactamente las posiciones en las que difieren.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def hammingWeight(n):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
n = 11
Salida Esperada
3