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
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