Medio · Bits
Contar los bits 1
¿Cuántos bits 1 tiene la forma binaria de un número? Se llama popcount, y es una instrucción real de CPU.
En una fraseCuenta los bits a 1 desplazando n a la derecha y sumando n & 1; o borra un bit por paso con n &= n - 1, que itera exactamente tantas veces como unos haya.
El problema
Entrada: Un entero no negativo (0 <= n <= 1000000).
Salida: El número de bits 1 en n.
Ejemplo:
| Entrada | Salida |
|---|---|
7 | 3 |
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Suma los restos
Mientras n > 0: ones += n % 2; n /= 2;.
Pista 2 — El truco de Kernighan
while (n) { n &= n - 1; ones++; } limpia el 1 más bajo cada vuelta.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int ones = 0;
while (n > 0) {
ones += n % 2;
n /= 2;
}
cout << ones << endl;
return 0;
}C++ moderno tiene std::popcount(n) (C++20), que compila a una instrucción.
Análisis profundo
Por qué funciona
Tres formas de contar bits encendidos —desplazar y probar, el n&(n-1) de Kernighan y el popcount del hardware— son un recorrido compacto por «misma respuesta, tres perfiles de coste».
El coste
Ingenua: siempre 32 vueltas. Kernighan: una por bit encendido. Hardware: O(1) con una sola instrucción.
Dónde falla
- Desplazar a la derecha un negativo con signo es comportamiento definido por la implementación y puede no terminar nunca, porque el bit de signo se rellena solo.
n >>= 1sobre un negativo no llega jamás a cero. Usaunsigned.
Siguiente paso
Pon esos bits a trabajar: Representación binaria.
Dos cosas para recordar
- Kernighan: una vuelta por bit encendido, no por bit.
- Desplaza solo valores sin signo: el desplazamiento con signo está definido por la implementación.
🐞 Esta versión falla: ábrela y pruébala
Solo mira los 8 bits bajos
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int c = 0;
for (int i = 0; i < 8; i++) {
if (n % 2 == 1) c++;
n /= 2;
}
cout << c << endl;
return 0;
}