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
💡
Intuition
Quando consideramos os números
n e n-1, o bit mais significativo destes dois só se mantém quando a representação binária de n possui outros 1s além do bit mais significativo. Se n for uma potência de 2 ⇒ a representação binária tem apenas um único 1 e, ao subtrair 1, n-1 perde o bit mais significativo (ele torna-se 0 e todos os demais bits passam a ser 1).
Para outros números (6, 67, 144, etc.), as suas representações binárias contêm vários 1s. Por isso, ao subtrair 1, não perdem o seu bit mais significativo.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