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
💡
Intuition
Lorsque l’on compare
n et n-1, le bit le plus significatif (celui qui est à 1 dans n) ne reste identique que si la représentation de n comporte d’autres 1 en plus du bit le plus significatif. Si n est une puissance de 2 ⇒ sa représentation binaire ne contient qu’un seul 1. Ainsi, quand on soustrait 1, le bit le plus significatif devient 0 et tous les bits moins importants passent à 1, rendant l’opération n & (n-1) égale à 0.
Pour les autres nombres (6, 67, 144, etc.), leur représentation binaire comporte plusieurs 1. Dans ce cas, en soustrayant 1, ils ne perdent pas tous leur bit le plus significatif.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