Verificare se un numero è una potenza di 2 con una singola operazione bitwise
Dato un intero positivo n, l’obiettivo è determinare se n è una potenza di 2. È possibile stabilirlo utilizzando una sola operazione bitwise. Se osserviamo la rappresentazione bitwise di un numero che è una potenza di 2, notiamo che c’è un unico 1 e tutti gli altri bit sono 0.
Numero | Rappresentazione binaria |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Numero casuale | Rappresentazione binaria |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Questo si comprende dalla definizione stessa della rappresentazione binaria. Ogni posizione con 1 corrisponde all’aggiunta di quella potenza di 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Avere un unico 1 nella rappresentazione binaria di un numero vuol dire che non sono presenti altre potenze di 2 oltre a quella singola. Il problema quindi si riduce a verificare se c’è un unico 1 nella rappresentazione binaria di n.
Un modo semplice per farlo è effettuare l’operazione bitwise & tra n e n-1. Se il risultato è 0 ⇒ n è una potenza di 2.
Per tutti i numeri che non sono potenze di 2, il risultato di n & (n-1) sarà diverso da 0:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
Tuttavia, per le potenze di 2, il risultato è sempre 0:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Input
La prima riga dell’input contiene un singolo intero n (2 ≤ n ≤ ).
Output
Il programma deve stampare Yes se n è una potenza di 2, altrimenti deve stampare No.
Examples
Input | Output |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB