Comment vérifier si un nombre est une puissance de 2

Aujourd’hui, j’ai besoin d’un algorithme simple pour vérifier si un nombre est une puissance de 2.

L’algorithme doit être:

  1. Simple
  2. Corrigez pour toute valeur ulong .

Je suis venu avec cet algorithme simple:

 private bool IsPowerOfTwo(ulong number) { if (number == 0) return false; for (ulong power = 1; power > 0; power = power < number) return false; } return false; } 

Mais alors j’ai pensé, que diriez-vous de vérifier si log 2 x est un nombre exactement rond? Mais quand j’ai vérifié 2 ^ 63 + 1, Math.Log retourné exactement 63 à cause de l’arrondissement. J’ai donc vérifié si 2 à la puissance 63 est égal au nombre d’origine – et c’est parce que le calcul est fait en double et non en nombres exacts:

 private bool IsPowerOfTwo_2(ulong number) { double log = Math.Log(number, 2); double pow = Math.Pow(2, Math.Round(log)); return pow == number; } 

Cela a renvoyé true pour la mauvaise valeur donnée: 9223372036854775809 .

Y a-t-il un meilleur algorithme?

Il y a un truc simple pour ce problème:

 bool IsPowerOfTwo(ulong x) { return (x & (x - 1)) == 0; } 

Notez que cette fonction indiquera true pour 0 , ce qui n’est pas une puissance de 2 . Si vous voulez exclure cela, voici comment:

 bool IsPowerOfTwo(ulong x) { return (x != 0) && ((x & (x - 1)) == 0); } 

Explication

D’abord et avant tout le binary et l’opérateur binary de la définition MSDN:

Les binarys et les opérateurs sont prédéfinis pour les types intégraux et bool. Pour les types intégraux, & calcule le bit logique ET de ses opérandes. Pour les opérandes bool, & calcule le ET logique de ses opérandes; c’est-à-dire que le résultat est vrai si et seulement si ses deux opérandes sont vrais.

Voyons maintenant comment cela se passe:

La fonction retourne booléen (true / false) et accepte un paramètre entrant de type unsigned long (x dans ce cas). Par souci de simplicité, supposons que quelqu’un ait dépassé la valeur 4 et appelé la fonction ainsi:

 bool b = IsPowerOfTwo(4) 

Maintenant, nous remplaçons chaque occurrence de x par 4:

 return (4 != 0) && ((4 & (4-1)) == 0); 

Eh bien, nous soaps déjà que 4! = 0 évalue à vrai, jusqu’ici tout va bien. Mais qu’en est-il de:

 ((4 & (4-1)) == 0) 

Cela se traduit bien sûr par ceci:

 ((4 & 3) == 0) 

Mais qu’est-ce que c’est exactement 4&3 ?

La représentation binary de 4 est 100 et la représentation binary de 3 est 011 (rappelez-vous la & prend la représentation binary de ces nombres). Donc nous avons:

 100 = 4 011 = 3 

Imaginez que ces valeurs soient empilées comme un ajout élémentaire. L’opérateur & dit que si les deux valeurs sont égales à 1, le résultat est 1, sinon il vaut 0. So 1 & 1 = 1 , 1 & 0 = 0 , 0 & 0 = 0 et 0 & 1 = 0 . Alors on fait le calcul:

 100 011 ---- 000 

Le résultat est simplement 0. Nous revenons donc à ce que notre déclaration de retour se traduit maintenant par:

 return (4 != 0) && ((4 & 3) == 0); 

Ce qui se traduit maintenant par:

 return true && (0 == 0); 
 return true && true; 

Nous soaps tous que true && true est simplement true , et cela montre que pour notre exemple, 4 est une puissance de 2.

Certains sites qui documentent et expliquent ce piratage ainsi que d’autres sont:

Et le grand-père d’entre eux, le livre “Hacker’s Delight” d’Henry Warren, Jr .:

Comme l’ explique la page de Sean Anderson , l’expression ((x & (x - 1)) == 0) indique à tort que 0 est une puissance de 2. Il suggère d’utiliser:

 (!(x & (x - 1)) && x) 

pour corriger ce problème.

return (i & -i) == i

J’ai écrit un article à ce sujet récemment sur http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Il traite du comptage de bits, de l’utilisation correcte des logarithmes, de la vérification classique “x &&! (X & (x – 1))”, etc.

 bool IsPowerOfTwo(ulong x) { return x > 0 && (x & (x - 1)) == 0; } 

Voici une solution simple C ++ :

 bool IsPowerOfTwo( unsigned int i ) { return std::bitset<32>(i).count() == 1; } 
  bool IsPowerOfTwo(int n) { if (n > 1) { while (n%2 == 0) { n >>= 1; } } return n == 1; } 

Et voici un algorithme général pour savoir si un nombre est une puissance d’un autre numéro.

  bool IsPowerOf(int n,int b) { if (n > 1) { while (n % b == 0) { n /= b; } } return n == 1; } 

Après avoir posté la question, j’ai pensé à la solution suivante:

Nous devons vérifier si exactement l’un des chiffres binarys est un. Donc, il suffit de décaler le nombre d’un chiffre à la fois et de retourner true s’il est égal à 1. Si nous arrivons à un moment quelconque avec un nombre impair ( (number & 1) == 1 ), nous soaps que le résultat est false . Ceci a prouvé (en utilisant un benchmark) un peu plus rapide que la méthode originale pour des valeurs vraies (grandes) et beaucoup plus rapide pour des valeurs fausses ou petites.

 private static bool IsPowerOfTwo(ulong number) { while (number != 0) { if (number == 1) return true; if ((number & 1) == 1) // number is an odd number and not 1 - so it's not a power of two. return false; number = number >> 1; } return false; } 

Bien sûr, la solution de Greg est bien meilleure.

L’addendum suivant à la réponse acceptée peut être utile pour certaines personnes:

Une puissance de deux, lorsqu’elle est exprimée en binary, ressemblera toujours à 1 suivie de n zéros où n est supérieur ou égal à 0. Ex:

 Decimal Binary 1 1 (1 followed by 0 zero) 2 10 (1 followed by 1 zero) 4 100 (1 followed by 2 zeroes) 8 1000 (1 followed by 3 zeroes) . . . . . . 

etc.

Lorsque nous soustrayons 1 de ces nombres, ils deviennent 0 suivis de n et de nouveau n est identique à ci-dessus. Ex:

 Decimal Binary 1 - 1 = 0 0 (0 followed by 0 one) 2 - 1 = 1 01 (0 followed by 1 one) 4 - 1 = 3 011 (0 followed by 2 ones) 8 - 1 = 7 0111 (0 followed by 3 ones) . . . . . . 

etc.

Venir au crux

Que se passe-t-il quand on fait un ET binary d’un nombre x , qui est une puissance de 2, et x - 1 ?

Celui de x s’aligne avec le zéro de x - 1 et tous les zéros de x sont alignés avec ceux de x - 1 , causant le bit AND et 0 comme résultat. droite.


Ajoutant à la beauté de la réponse acceptée ci-dessus –

Nous avons donc une propriété à notre disposition maintenant:

Quand on soustrait 1 de n’importe quel nombre, alors dans la représentation binary, le 1 le plus à droite deviendra 0 et tous les zéros avant celui le plus à droite 1 deviendront 1

Un des avantages de cette propriété est de savoir – Combien de 1 sont présents dans la représentation binary d’un nombre donné? Le code court et doux pour faire cela pour un entier x est:

 byte count = 0; for ( ; x != 0; x &= (x - 1)) count++; Console.Write("Total ones in the binary representation of x = {0}", count); 

Un autre aspect des nombres qui peut être prouvé par le concept expliqué ci-dessus est “Chaque nombre positif peut-il être représenté par la sum des puissances de 2?” .

Oui, chaque nombre positif peut être représenté par la sum des puissances de 2. Pour tout nombre, prenez sa représentation binary. Ex: Prenez le numéro 501 .

 The binary of 501 is 111110101 Because 111110101 = 100000000 + 10000000 + 1000000 + 100000 + 1000 + 000 + 100 + 00 + 1 we have 501 = 256 + 128 + 64 + 32 + 16 + 0 + 4 + 0 + 1 
 bool isPow2 = ((x & ~(x-1))==x)? !!x : 0; 

Trouvez si le nombre donné est une puissance de 2.

 #include  int main(void) { int n,logval,powval; printf("Enter a number to find whether it is s power of 2\n"); scanf("%d",&n); logval=log(n)/log(2); powval=pow(2,logval); if(powval==n) printf("The number is a power of 2"); else printf("The number is not a power of 2"); getch(); return 0; } 
 bool isPowerOfTwo(int x_) { register int bitpos, bitpos2; asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_)); asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_)); return bitpos > 0 && bitpos == bitpos2; } 
 int isPowerOfTwo(unsigned int x) { return ((x != 0) && ((x & (~x + 1)) == x)); } 

C’est vraiment rapide. Cela prend environ 6 minutes et 43 secondes pour vérifier tous les 2 ^ 32 entiers.

 return ((x != 0) && !(x & (x - 1))); 

Si x est une puissance de deux, son seul bit 1 est en position n . Cela signifie que x – 1 a un 0 en position n . Pour savoir pourquoi, rappelez-vous comment fonctionne une soustraction binary. En soustrayant 1 de x , l’emprunt se propage jusqu’à la position n ; le bit n devient 0 et tous les bits inférieurs deviennent 1. Maintenant que x n’a pas 1 bit en commun avec x – 1 , x & (x – 1) est égal à 0 et !(x & (x – 1)) est vrai.

Un nombre est une puissance de 2 s’il ne contient que 1 bit défini. Nous pouvons utiliser cette propriété et la fonction générique countSetBits pour déterminer si un nombre est de 2 ou non.

Ceci est un programme C ++:

 int countSetBits(int n) { int c = 0; while(n) { c += 1; n = n & (n-1); } return c; } bool isPowerOfTwo(int n) { return (countSetBits(n)==1); } int main() { int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70}; for(i=0; i 

Nous n'avons pas besoin de vérifier explicitement que 0 est une puissance de 2, car il renvoie également False pour 0.

SORTIE

 Num:0 Set Bits:0 is power of two: 0 Num:1 Set Bits:1 is power of two: 1 Num:2 Set Bits:1 is power of two: 1 Num:3 Set Bits:2 is power of two: 0 Num:4 Set Bits:1 is power of two: 1 Num:5 Set Bits:2 is power of two: 0 Num:15 Set Bits:4 is power of two: 0 Num:16 Set Bits:1 is power of two: 1 Num:22 Set Bits:3 is power of two: 0 Num:32 Set Bits:1 is power of two: 1 Num:38 Set Bits:3 is power of two: 0 Num:64 Set Bits:1 is power of two: 1 Num:70 Set Bits:3 is power of two: 0 

Voici une autre méthode que j’ai conçue, dans ce cas, en utilisant | au lieu de & :

 bool is_power_of_2(ulong x) { if(x == (1 << (sizeof(ulong)*8 -1) ) return true; return (x > 0) && (x<<1 == (x|(x-1)) +1)); } 

Améliorer la réponse de @ user134548, sans arithmétique de bits:

 public static bool IsPowerOfTwo(ulong n) { if (n % 2 != 0) return false; // is odd (can't be power of 2) double exp = Math.Log(n, 2); if (exp != Math.Floor(exp)) return false; // if exp is not integer, n can't be power return Math.Pow(2, exp) == n; } 

Cela fonctionne bien pour:

 IsPowerOfTwo(9223372036854775809) 

Exemple

 0000 0001 Yes 0001 0001 No 

Algorithme

  1. En utilisant un masque de bits, divisez NUM la variable en binary

  2. IF R > 0 AND L > 0: Return FALSE

  3. Sinon, NUM devient celui qui est non nul

  4. IF NUM = 1: Return TRUE

  5. Sinon, passez à l’étape 1

Complexité

Time ~ O(log(d))d est le nombre de chiffres binarys

pour tout pouvoir de 2, ce qui suit est également valable.

n & (- n) == n

REMARQUE: échoue pour n = 0, il faut donc le vérifier
Raison pour laquelle cela fonctionne est:
-n est le complément à 2s de n. -n aura tout le bit à gauche du bit le plus à droite de n inversé par rapport à n. Pour les puissances de 2, il n’y a qu’un seul bit défini.

Ce programme en Java retourne “true” si number est une puissance de 2 et retourne “false” si ce n’est pas une puissance de 2

 // To check if the given number is power of 2 import java.util.Scanner; public class PowerOfTwo { int n; void solve() { while(true) { // To eleminate the odd numbers if((n%2)!= 0){ System.out.println("false"); break; } // Tracing the number back till 2 n = n/2; // 2/2 gives one so condition should be 1 if(n == 1) { System.out.println("true"); break; } } } public static void main(Ssortingng[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); PowerOfTwo obj = new PowerOfTwo(); obj.n = in.nextInt(); obj.solve(); } } OUTPUT : 34 false 16 true 
 private static bool IsPowerOfTwo(ulong x) { var l = Math.Log(x, 2); return (l == Math.Floor(l)); }