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

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

L'algorithme doit être:

1. Facile
2. Corrigez pour n'importe quelle ulongvaleur.

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 << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

Mais alors j'ai pensé, que diriez-vous de vérifier si c'est un nombre exactement rond? Mais quand j'ai vérifié 2 ^ 63 + 1, je suis 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 se fait en s et non en nombres exacts:log2 xMath.Logdouble

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

Ce retour trueà la valeur donnée erronée: 9223372036854775809.

Existe-t-il un meilleur algorithme?

Il existe une astuce simple pour ce problème:

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

Notez que cette fonction rendra compte truede 0, ce qui n'est pas une puissance de 2. Si vous souhaitez exclure cela, voici comment:

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

Explication

D'abord et avant tout, l'opérateur binaire au niveau du bit de la définition MSDN:

Les opérateurs binaires et sont prédéfinis pour les types intégraux et booléens. Pour les types intégraux, & calcule le ET logique au niveau du bit de ses opérandes. Pour les opérandes booléens, & 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 tout cela se déroule:

La fonction retourne un booléen (true / false) et accepte un paramètre entrant de type unsigned long (x, dans ce cas). Supposons pour des raisons de simplicité que quelqu'un a passé la valeur 4 et a appelé la fonction comme ceci:

bool b = IsPowerOfTwo(4)

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

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

Eh bien, nous savons déjà que 4! = 0 est vrai, jusqu'à présent tout va bien. Mais qu'en est-il:

((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 binaire de 4 est 100 et la représentation binaire de 3 est 011 (rappelez-vous que le & prend la représentation binaire 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 , alors le résultat est 1, sinon il est égal à 0. Donc 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0et 0 & 1 = 0. Nous faisons donc le calcul:

100
011
----
000

Le résultat est simplement 0. Nous allons donc revenir en arrière et voir ce que notre déclaration de retour se traduit maintenant:

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

Ce qui se traduit maintenant par:

return true && (0 == 0);

return true && true;

Nous savons tous que true && truec'est simple true, et cela montre que pour notre exemple, 4 est une puissance de 2.

Certains sites qui documentent et expliquent cela et d'autres hacks de twiddling sont:

• http://graphics.stanford.edu/~seander/bithacks.html
  ( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
• http://bits.stephan-brumme.com/
  ( http://bits.stephan-brumme.com/isPowerOfTwo.html )

Et leur grand-père, le livre "Hacker's Delight" de Henry Warren, Jr .:

• http://www.hackersdelight.org/

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

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

J'ai récemment écrit un article à ce sujet sur http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Il couvre le comptage de bits, comment utiliser correctement les logarithmes, la vérification classique "x &&! (X & (x - 1))" et bien d'autres.

Voici une solution C ++ simple :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

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

Une puissance de deux, exprimée en binaire, ressemblera toujours à 1 suivi 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 1de ce type de nombres, ils deviennent 0 suivi de n uns et encore n est le même que 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 à l'essentiel

Que se passe-t-il lorsque nous faisons un ET au niveau du bit d'un nombre x, qui est une puissance de 2, et x - 1?

L'un de xs'aligne avec le zéro de x - 1et tous les zéros de xs'alignent avec ceux de x - 1, ce qui fait que l'ET au niveau du bit donne 0. Et c'est ainsi que la réponse sur une seule ligne mentionnée ci-dessus est correcte.

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

Donc, nous avons maintenant une propriété à notre disposition:

Lorsque nous soustrayons 1 de n'importe quel nombre, alors dans la représentation binaire le 1 le plus à droite deviendra 0 et tous les zéros avant ce 1 le plus à droite deviendront maintenant 1

Une utilisation impressionnante de cette propriété est de savoir - Combien de 1 sont présents dans la représentation binaire d'un nombre donné? Le code court et doux pour le faire pour un entier donné xest:

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é comme la somme des puissances de 2?" .

Oui, chaque nombre positif peut être représenté comme la somme des puissances de 2. Pour tout nombre, prenez sa représentation binaire. Ex: Prenez le numéro 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

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

Nous devons vérifier si exactement l'un des chiffres binaires en est un. Donc, nous décalons simplement le chiffre d'un chiffre à la fois, et retournons trues'il est égal à 1. Si à tout moment nous arrivons par un nombre impair ( (number & 1) == 1), nous savons que le résultat est false. Cela s'est avéré (en utilisant une référence) légèrement plus rapide que la méthode originale pour les (grandes) vraies valeurs et beaucoup plus rapide pour les fausses ou les petites valeurs.

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.

    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 nombre.

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

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

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

#include <math.h>

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. Il faut environ 6 minutes et 43 secondes pour vérifier tous les 2 ^ 32 entiers.

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

Si xest une puissance de deux, son seul bit 1 est en position n. Cela signifie qu'il x – 1a un 0 en position n. Pour voir pourquoi, rappelez-vous comment fonctionne une soustraction binaire. En soustrayant 1 de x, l'emprunt se propage jusqu'à la position n; bit ndevient 0 et tous les bits inférieurs deviennent 1. Maintenant, puisqu'il xn'a pas de 1 bit en commun avec x – 1, x & (x – 1)est 0 et !(x & (x – 1))est vrai.

Un nombre est une puissance de 2 s'il ne contient qu'un seul bit défini. Nous pouvons utiliser cette propriété et la fonction générique countSetBitspour trouver si un nombre est une puissance 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<sizeof(val)/sizeof(val[0]); i++)
        printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
    return 0;
}

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

PRODUCTION

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));
}

pour toute puissance de 2, ce qui suit est également valable.

n & (- n) == n

REMARQUE: échoue pour n = 0, donc besoin de le vérifier
Raison pour laquelle cela fonctionne est:
-n est le complément 2s de n. -n aura chaque 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.

Exemple

0000 0001    Yes
0001 0001    No

Algorithme

1. À l'aide d'un masque de bits, divisez NUMla variable en binaire

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

3. Sinon, NUMdevient celui qui est non nul

4. IF NUM = 1: Return TRUE

5. Sinon, passez à l'étape 1

Complexité

Heure ~ O(log(d))où dest le nombre de chiffres binaires

Amélioration de 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)

Mark Gravell a suggéré ce si vous avez .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Instruction unique, plus rapide (x != 0) && ((x & (x - 1)) == 0)mais moins portable.

En C, j'ai testé l' i && !(i & (i - 1)astuce et l' ai comparée avec __builtin_popcount(i), en utilisant gcc sous Linux, avec l'indicateur -mpopcnt pour être sûr d'utiliser l'instruction POPCNT du CPU. Mon programme de test a compté le nombre d'entiers compris entre 0 et 2 ^ 31 qui étaient une puissance de deux.

Au début, je pensais que i && !(i & (i - 1)c'était 10% plus rapide, même si j'ai vérifié que POPCNT était utilisé dans le démontage où je l'ai utilisé __builtin_popcount.

Cependant, j'ai réalisé que j'avais inclus une instruction if, et la prédiction de branche faisait probablement mieux sur la version bit twiddling. J'ai supprimé l'if et POPCNT s'est retrouvé plus rapidement, comme prévu.

Résultats:

Processeur Intel (R) Core (TM) i7-4771 max 3,90 GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

Processeur AMD Ryzen Threadripper 2950X 16 cœurs max 3,50 GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Notez qu'ici, le processeur Intel semble légèrement plus lent que AMD avec le bit twiddling, mais a un POPCNT beaucoup plus rapide; l'AMD POPCNT ne fournit pas autant de boost.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Exécutez les tests:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Je vois que de nombreuses réponses suggèrent de renvoyer n &&! (N & (n - 1)) mais d'après mon expérience, si les valeurs d'entrée sont négatives, elles renvoient de fausses valeurs. Je partagerai ici une autre approche simple car nous savons qu'une puissance de deux nombres n'a qu'un seul bit défini, donc simplement nous compterons le nombre de bits définis, cela prendra du temps O (log N).

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Consultez cet article pour ne pas compter. de bits définis

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

Ce programme en java renvoie "vrai" si le nombre est une puissance de 2 et renvoie "faux" 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(String[] 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