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
💡
Intuizione
Quando consideriamo i numeri
n e n-1, il bit più significativo di entrambi rimane invariato solo se la rappresentazione binaria di n contiene altri 1 oltre a quello più significativo. Se n è una potenza di 2 ⇒ la rappresentazione binaria contiene un solo 1, e sottraendo 1 (n-1) si azzera quel bit più significativo (diventa 0) e tutti gli altri bit passano a 1.
Per gli altri numeri (6, 67, 144, ecc.), le loro rappresentazioni binarie contengono più 1. Di conseguenza, quando si sottrae 1, non si perde il bit più significativo.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