Verificar si un número es una potencia de 2 con una sola operación a nivel de bits
Dado un entero positivo
n, se te pide determinar si es una potencia de 2. Esto puede lograrse con una sola operación a nivel de bits. Si analizamos la representación en binario de un número que sea potencia de 2, veremos que contiene un solo 1 y el resto son 0.Número | Representación binaria |
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Número aleatorio | Representación binaria |
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Esto se desprende de la definición de la representación binaria. Cada posición con un 1 corresponde a sumar esa potencia de 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Por lo tanto, tener un solo
1 en la representación binaria significa que no hay otras potencias de 2 en la suma aparte de esa. Así, el problema se reduce a verificar si existe un único 1 en la representación binaria de n.Una forma sencilla de hacerlo es con la operación a nivel de bits
& entre n y n-1. Si el resultado es 0 ⇒ significa que n es una potencia de 2.Para cualquier número que no sea potencia de 2, el resultado de
n & (n-1) será distinto de 0:- 7 & 6 = 111 & 110 = 110 (6)
- 67 & 66 = 1000011 & 1000010 = 1000010 (66)
- 144 & 143 = 10010000 & 10001111 = 10000000 (128)
Sin embargo, para potencias de 2, siempre será 0:
- 8 & 7 = 1000 & 111 = 0
- 32 & 31 = 100000 & 11111 = 0
- 128 & 127 = 10000000 & 1111111 = 0
💡
Intuición
Al comparar
n y n-1, el bit más significativo solo se conserva en ambos números cuando la representación binaria de n tiene otros 1 aparte del bit más significativo. Si n es una potencia de 2 ⇒ su representación binaria posee un único 1, y al restar 1, n-1 pierde ese bit más significativo (pasa a 0 y el resto se vuelve 1).
Para otros números (6, 67, 144, etc.), su representación binaria contiene varios 1, de modo que al restar 1 no se pierde el bit más significativo.Entrada
La primera línea de la entrada contiene un entero
n (2 ≤ n ≤ 10^9).Salida
El programa debe imprimir
Yes si n es potencia de 2 y No en caso contrario.Ejemplos
Input | Output |
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB