Verificar se um número é uma potência de 2 com uma única operação bit a bit
Dado um número inteiro positivo n, pretende-se verificar se é uma potência de 2. É possível fazer isso com uma única operação bit a bit. Se pensarmos na representação binária de um número que seja potência de 2, ele terá um único 1 na sua representação, e todos os outros dígitos serão 0.
Número | Representação binária |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Número Aleatório | Representação binária |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Isso fica claro a partir da definição de representação binária. Cada posição que contenha um 1 corresponde à adição daquela potência de 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Assim, ter apenas um 1 na representação binária de um número significa que não há outras potências de 2 na soma além daquela. Logo, o problema passa a ser verificar se existe apenas um único 1 na representação binária de n.
Uma forma simples de verificar isso é aplicando a operação bit a bit & entre n e (n-1). Se o resultado for 0 ⇒ é uma potência de 2.
Para qualquer número que não seja uma potência de 2, o resultado de n & (n-1) será diferente de 0:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
Já para as potências de 2, o resultado é sempre 0:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Entrada
A primeira linha da entrada contém um único inteiro n (2 ≤ n ≤ ).
Saída
O programa deve imprimir Yes se n for uma potência de 2 e No caso contrário.
Exemplos
Entrada | Saída |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB