Power of Two
On te donne un entier n. Retourne true si n est une puissance de deux, c’est-à-dire n = 2^k pour un entier k ≥ 0, et false sinon. Ainsi, 1, 2, 4 et 8 sont acceptés, tandis que 0, 6 et tous les nombres négatifs ne le sont pas.
Fonction
- ninteger
- l’entier à tester, qui peut être nul ou négatif
- Renvoieboolean
- vrai si n est égal à 2^k pour un certain k ≥ 0, faux sinon
Contraintes
-231 ≤ n ≤ 231-1
Exemples
- Entrée
- n = 16
- Sortie
- true
- Explication
- 16 = 2 × 2 × 2 × 2 = 2^4. En binaire, cela s’écrit
10000, avec un seul bit à 1.
- Entrée
- n = 24
- Sortie
- false
- Explication
- 24 = 8 × 3. La moitié donne 12, 6 puis 3, qui est impair mais pas égal à 1. En binaire, 24 s’écrit
11000, avec deux bits à 1.
- Entrée
- n = 1
- Sortie
- true
- Explication
- 1 = 2^0, c'est donc une puissance de deux. Sa représentation binaire
1contient exactement un bit à 1.
+17 tests cachés à la soumission
Pour aller plus loin
Avec les mêmes astuces sur les bits, peux-tu tester si n est une puissance de quatre sans boucle ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Écrivez quelques puissances de deux en binaire :
1,10,100,1000. Quel point commun ont-elles que 6 (110) n’a pas ?Une puissance de deux possède exactement un bit à 1. Comparez
nàn-1en binaire : soustraire 1 transforme le bit à 1 le plus à droite en 0 et chaque 0 situé en dessous en 1.Ainsi,
nest une puissance de deux exactement lorsqu’il est positif et que l’opération AND entre lui etn-1donne 0. Vérifiez le signe avant les bits, car 0 et les nombres négatifs ne sont jamais des puissances de deux.
Solution
Une puissance de deux a une forme fixe en binaire : un bit 1 suivi de zéros, comme 10000 pour 16. Tu peux confirmer cette forme en divisant n par deux jusqu’à ce qu’il devienne impair, ce qui prend jusqu’à 31 étapes. Ou tu peux le confirmer en une seule étape avec n & (n-1), qui efface le bit 1 le moins significatif et ne laisse que 0 que lorsque ce bit était le seul. Dans les deux versions, la vérification du signe vient en premier, car les nombres zéro et négatifs perturbent le code évident.
Diviser par 2 tant que le nombre est pair
Intuition
Si n = 2^k, tu peux le diviser exactement par 2 k fois et obtenir 1, et toutes les valeurs obtenues en cours de route sont paires. Si n a un facteur impair supérieur à 1, les divisions par 2 s’arrêtent sur un nombre impair différent de 1. Pour 16 : 16, 8, 4, 2, 1, donc la réponse est true. Pour 24 : 24, 12, 6, 3, et 3 est impair mais différent de 1, donc la réponse est false.
Renvoie false pour n ≤ 0 avant la boucle. Aucune puissance de deux n’est nulle ou négative, et la boucle ne se terminera jamais pour 0, car 0 est pair et la moitié de 0 est toujours 0.
Chaque étape divise n par deux, donc une entrée sur 32 bits nécessite au plus 31 étapes : temps O(log n) et espace O(1).
Algorithme
- Si
n ≤ 0, renvoie false. - Tant que
nest pair, divise-le par 2. - Renvoie si
nvaut maintenant 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Effacez le bit de poids faible avec n & (n-1)
Intuition
Écrivez une puissance de deux en binaire : elle se compose d’un seul 1 suivi de zéros. 16 s’écrit 10000. La soustraction de 1 transforme ce 1 en 0 et tous les 0 qui le suivent en 1 : 15 s’écrit 01111. Les deux nombres n’ont aucun bit à 1 en commun, donc 16 & 15 vaut 0.
Tout autre nombre positif possède au moins deux bits à 1. La soustraction de 1 ne modifie que le bit à 1 le plus bas et les zéros qui le suivent. Chaque bit à 1 de rang supérieur apparaît donc dans les deux nombres, et le AND n’est pas égal à 0. Pour 24, qui s’écrit 11000, on obtient 23 = 10111, et 24 & 23 vaut 10000, soit 16.
Vérifiez d’abord n > 0. 0 & -1 vaut 0, et en arithmétique sur 32 bits, -2^31 est constitué d’un seul bit à 1 suivi de 31 zéros. Le AND seul considérerait donc que ces deux nombres sont des puissances de deux. Le test complet consiste en une comparaison, une soustraction et un AND : temps et espace en O(1). Lua 5.1 ne possède pas d’opérateur AND, donc le code Lua construit le AND bit par bit, en 31 étapes au maximum pour un n sur 32 bits ; le test reste le même.
Algorithme
- Si
n ≤ 0, renvoie false. - Calcule
n & (n-1), qui correspond ànavec son bit 1 de poids le plus faible effacé. - Renvoie si ce résultat est égal à 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
Pièges et cas limites
Le test de bits tient sur une ligne, et la plupart des erreurs concernent les entrées pour lesquelles il n’a pas été conçu.
- Omettre la vérification du signe.
0 & (0-1)vaut 0, donc 0 réussit le test AND. Avec des entiers de 32 bits,-2^31réussit aussi, car sa forme binaire comporte un seul bit à 1. Les deux doivent renvoyer false. - Exécuter la boucle de division par deux sur 0. Zéro est pair, et le diviser par deux donne encore 0 : la boucle ne se termine donc jamais.
- Omettre les parenthèses.
==a une priorité supérieure à&, donc, en C, C++ et JavaScript,n & n - 1 == 0est interprété commen & ((n - 1) == 0)et donne une réponse incorrecte sans générer d’erreur ; Java et C# le rejettent comme une erreur de type. Écrivez(n & (n - 1)) == 0. - Utiliser des logarithmes. En double précision,
log(536870912) / log(2)donne 29.000000000000004 au lieu de 29, donc une vérification du nombre entier considère que2^29est false.
Questions fréquentes4
Comment vérifier si un nombre est une puissance de deux ?
Renvoie true lorsque n > 0 et que n & (n-1) est égal à 0. Une puissance de deux possède exactement un bit à 1, et lui soustraire 1 le met à 0 tout en mettant à 1 uniquement les bits situés en dessous, donc le ET vaut 0. Sans opérations sur les bits, divise n par deux tant qu’il est pair et vérifie que tu obtiens 1 à la fin.
Pourquoi n & (n-1) efface-t-il le bit à 1 le moins significatif ?
Soustraire 1 emprunte au bit 1 de poids faible : ce bit devient 0 et chaque 0 situé en dessous devient 1, tandis que les bits de poids supérieur restent inchangés. Effectuer un ET avec la valeur d’origine ne conserve que les bits activés dans les deux valeurs, qui sont précisément les bits de poids supérieur. Pour une puissance de deux, il n’y a pas de bits de poids supérieur, donc le résultat est 0.
Quelle est la complexité temporelle de Power of Two ?
La vérification n & (n-1) s’exécute en temps et en espace O(1) : une comparaison, une soustraction et un AND. La boucle de division par deux s’exécute en O(log n) temps, en 31 étapes au maximum pour un entier de 32 bits.
1 est-il une puissance de deux ? Et 0 ?
1 est une puissance de deux, car 2^0 = 1, et sa forme binaire comporte un bit à 1. 0 n’en est pas une : aucun exposant entier ne donne 0, et il ne comporte aucun bit à 1. Les nombres négatifs ne sont jamais non plus des puissances de deux.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def isPowerOfTwo(n):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
n = 16
Attendu
true