Cuente bits y el bit activado más bajo
Use popcount y el truco n & -n
Cuente bits y el bit activado más bajo es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Contar los unos
Muchos problemas preguntan cuántos bits están activados en un número, lo que se denomina popcount. Aparece en tamaños de subconjuntos, comprobaciones de paridad y puntuaciones. 🔢
El método integrado de Python
La forma más rápida de contar los bits activados es el método de enteros bit_count(). Sin bucles ni complicaciones: solo el número de unos.
print((13).bit_count()) # 0b1101 has 3 onesContar con bin y count
Si olvida bit_count, convierta el número en texto binario y cuente los unos. Es más lento, pero claro y fácil de recordar.
print(bin(13).count('1')) # 3El bit activado de menor valor
El bit activado de menor valor es el 1 situado más a la derecha en un número. Aislarlo es una técnica clave para los árboles de Fenwick y los trucos con subconjuntos que verá más adelante.
Aislarlo con n y -n
El famoso truco n & -n conserva únicamente el bit activado de menor valor. Los negativos en complemento a dos hacen que funcione como por arte de magia.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Por qué funciona n y -n
Negar invierte todos los bits y suma 1, por lo que todo lo que está por debajo del 1 de menor valor se invierte. Aplicar AND deja en pie únicamente ese bit.
Eliminar el bit activado de menor valor
Al restar 1 se pide prestado a través de los ceros finales, por lo que n & (n - 1) elimina el bit activado de menor valor. Repita la operación para quitar los unos de uno en uno.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000El conteo de Brian Kernighan
Repita el bucle mientras el número no sea cero y borre el bit de menor valor en cada iteración. El bucle se ejecuta una vez por cada bit activado, por lo que es rápido para un popcount disperso.
c = 0
while n:
n &= n - 1
c += 1Comprobar si es una potencia de dos
Una potencia de dos positiva tiene exactamente un bit activado, por lo que n & (n - 1) es igual a 0. Una sola operación AND se lo indica al instante.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0La paridad a partir del conteo de bits
La paridad de un número es simplemente su popcount módulo 2. Permite responder en un solo paso a las preguntas sobre si hay una cantidad par o impar de unos.
parity = (13).bit_count() & 1 # 1Elija la herramienta más rápida
Para obtener la máxima velocidad, use bit_count; para recorrer los bits activados, use el bucle n & (n-1). Elegir la herramienta adecuada ayuda a cumplir los límites de tiempo estrictos. ⚡
Comprobación rápida
Pruebe el truco del bit activado de menor valor.
Resumen: contar bits
Puede contar los unos con bit_count, aislar el bit de menor valor mediante n & -n y eliminarlo con n & (n-1). Son líneas únicas muy potentes. 🎉
Preguntas frecuentes
¿La lección «Cuente bits y el bit activado más bajo» es gratis?
Sí — el texto completo de «Cuente bits y el bit activado más bajo» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Cuente bits y el bit activado más bajo»?
Use popcount y el truco n & -n Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Cuente bits y el bit activado más bajo»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- AND, OR, XOR y desplazamientos
- Establezca, borre y alterne un bit
- Cuente bits y el bit activado más bajo
- Bitmasks como conjuntos diminutos