Fácil–medio · Números
¿Es potencia de dos?
Decide si un número es potencia de dos (1, 2, 4, 8…). Un problema corto con un truco de bits precioso.
En una fraseUn n positivo es potencia de dos exactamente cuando n & (n - 1) es 0: trata el 0 aparte, porque 0 & -1 también es 0 y 0 no es potencia de dos.
El problema
Entrada: Un entero n (0 <= n <= 1000000).
Salida: yes si lo es, si no no.
Ejemplo:
| Entrada | Salida |
|---|---|
8 | yes |
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 — Cuidado con el 0
0 no es potencia de dos y ese bucle no termina con 0. Trata n < 1 primero.
Pista 2 — El truco de bits (extra)
Una potencia de dos tiene un solo bit en 1: (n & (n - 1)) == 0 para n > 0.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n < 1) {
cout << "no" << endl;
return 0;
}
while (n % 2 == 0) n /= 2;
if (n == 1) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}El truco es O(1) en vez de O(log n), como el atajo √N de los primos.
Análisis profundo
Por qué funciona
Una potencia de dos tiene exactamente un bit encendido, así que n & (n-1) lo apaga y el resultado es cero. Un bucle se convierte en una instrucción.
El coste
O(1) frente a O(log n) dividiendo una y otra vez: y además es lo que genera el compilador.
Dónde falla
n & (n-1) == 0se analiza comon & ((n-1) == 0)porque == tiene más prioridad que &. Pon paréntesis.- El truco dice que 0 es potencia de dos. Excluye n <= 0 explícitamente.
Siguiente paso
Cuenta los bits en su lugar: Contar bits 1.
Dos cosas para recordar
- n & (n-1) apaga el bit encendido más bajo.
- == tiene más prioridad que &: pon siempre paréntesis.
🐞 Esta versión falla: ábrela y pruébala
== tiene más prioridad que &: la condición no dice lo que crees
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n & (n - 1) == 0) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}