Vérifier si un nombre est une puissance de 2 avec une seule opération au niveau des bits
Étant donné un entier positif n, on vous demande de déterminer s’il s’agit d’une puissance de 2. Il est possible d’effectuer cette vérification grâce à une unique opération au niveau des bits. Pour comprendre pourquoi, il suffit d’observer que la représentation binaire d’une puissance de 2 contient un seul 1, le reste des bits étant à 0.
Nombre de la forme | Représentation binaire |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Nombre aléatoire | Représentation binaire |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Cela découle directement de la définition de la représentation binaire : chaque position où apparaît un 1 correspond à l’ajout de la valeur 2^k associée (par exemple, 67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). Ainsi, si un nombre binaire ne possède qu’un seul 1, cela signifie qu’aucune autre puissance de 2 n’est incluse dans la somme. Le problème revient donc à vérifier qu’un seul bit est égal à 1 dans la représentation binaire de n.
Une méthode simple pour le confirmer consiste à calculer l’opération n & (n-1). Si le résultat est 0 ⇒ n est une puissance de 2.
Pour tout nombre qui n’est pas une puissance de 2, le résultat de n & (n-1) est différent de 0 :
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
En revanche, pour les puissances de 2, le résultat est toujours 0 :
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
Entrée
La première ligne de l’entrée contient un unique entier n (2 ≤ n ≤ 10^9).
Sortie
Le programme doit afficher Yes si n est une puissance de 2, et No dans le cas contraire.
Exemples
Entrée | Sortie |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB