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. corriger pour toute valeur ulong .

j'ai trouvé 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 je me suis dit, Que dirais-tu de vérifier si log2 x est un nombre exactement rond? Mais quand j'ai vérifié 2^63+1, Math.Log est revenu exactement 63 à cause de l'arrondissement. Donc j'ai vérifié si 2 à la puissance 63 est égal au nombre d'origine - et il est, parce que le calcul est fait dans double s et non dans les 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;
}

ce retour true pour la valeur erronée donnée: 9223372036854775809 .

y a-t-il un meilleur algorithme?

496
demandé sur configurator 2009-03-01 22:01:29
la source

21 ответов

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

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

Note , Cette fonction indiquera true pour 0 , 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 binaire bitwise et l'opérateur de la définition MSDN:

binaire & les opérateurs sont prédéfinis pour le les types intégraux et bool. Pour integral types, & calcule la logique bitwise et de ses opérandes. Pour les opérandes de bool, & calcule la logique et de ses opérandes; que est, le résultat est vrai si et seulement si ses deux opérandes sont vrais.

voyons maintenant comment tout cela se joue:

la fonction renvoie booléen (true / false) et accepte un paramètre entrant de type non signé long (x, dans ce cas). Laissez-nous le par souci de simplicité, supposons que quelqu'un a dépassé la valeur 4 et a 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 savons déjà que 4 != 0 est évaluée comme vraie, c'est très bien. Mais qu'en est-il:

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

cela se traduit par ceci bien sûr:

((4 & 3) == 0)

mais qu'est-ce que 4&3 ?

La représentation binaire de 4 est de 100 et la représentation binaire de 3 est de 011 (rappelez-vous le & prend la représentation binaire de ces nombres). Nous avons donc:

100 = 4
011 = 3

Imaginez que ces valeurs soient empilées un peu comme une addition élémentaire. L'opérateur & dit que si les deux valeurs sont égales à 1 alors le résultat est 1, sinon il est 0. Donc 1 & 1 = 1 , 1 & 0 = 0 , 0 & 0 = 0 , et 0 & 1 = 0 . Donc nous faisons le calcul:

100
011
----
000

le résultat est simplement 0. Nous revenons donc en arrière et regardons ce que notre déclaration de retour se traduit maintenant par:

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

qui se traduit maintenant par:

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

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

1056
répondu Greg Hewgill 2018-05-16 15:49:26
la source

certains sites qui documentent et expliquent ceci et d'autres piratages sont:

Et le grand-père, le livre "Hacker s Delight" par Henry Warren, Jr :

comme la page de Sean Anderson explique, l'expression ((x & (x - 1)) == 0) indique incorrectement que 0 est une puissance de 2. Il suggère d' use:

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

pour corriger ce problème.

88
répondu Michael Burr 2016-02-28 17:12:38
la source

return (i & -i) == i

38
répondu Andreas Petersson 2009-06-17 17:25:25
la source

j'ai écrit un article à ce sujet récemment à 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 les logarithmes correctement, le classique " x&&!(x & (x - 1))" vérifier, et d'autres.

20
répondu Rick Regan 2009-03-02 23:54:00
la source
bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}
19
répondu Matt Howells 2009-11-26 19:37:51
la source

voici un simple c++ solution:

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}
14
répondu deft_code 2014-03-05 21:08:44
la source
    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

Et voici un algorithme général pour déterminer 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;
    }
10
répondu Raz Megrelidze 2014-02-28 16:03:38
la source

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

nous devons vérifier si exactement un des chiffres binaires est un. Il suffit donc de décaler le nombre à droite d'un chiffre à la fois, et de retourner true s'il est égal à 1. Si à un moment quelconque nous arrivons à un nombre impair ( (number & 1) == 1 ), nous savons que le résultat est false . Cela s'est avéré (à l'aide d'un benchmark) légèrement plus rapide que la méthode originale pour les valeurs vraies (grandes) et beaucoup plus rapide pour les 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.

9
répondu configurator 2009-03-01 22:06:50
la source

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

Une puissance de deux, quand il est exprimé 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)
.        .
.        .
.        .

et ainsi de suite.

quand nous soustrayons 1 de ce genre de nombres, ils deviennent 0 suivi de n uns et encore n est 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)
.          .
.          .
.          .

et ainsi de suite.

Venir à l'essentiel

ce qui se passe quand nous faisons un bitwise et d'un nombre x , qui est un puissance 2, et x - 1 ?

celui de x est aligné avec le zéro de x - 1 et tous les zéros de x sont alignés avec ceux de x - 1 , provoquant la au niveau du bit ET le résultat en 0. et c'est ainsi que nous avons la réponse en une seule ligne mentionnée ci-dessus étant juste.


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

donc, nous avons un bien à notre disposition maintenant:

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

Un génial utilisation de cette propriété est de trouver Combien de 1s sont présents dans la représentation binaire d'un nombre donné? le code court et doux pour faire cela pour un entier donné 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é à partir du concept expliqué ci-dessus est " peut chaque nombre positif ê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 un certain nombre, prenez sa représentation binaire. Ex: prendre 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
7
répondu displayName 2017-12-27 23:24:21
la source
bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;
6
répondu abelenky 2015-08-24 16:57:38
la source

trouver 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;
}
4
répondu udhaya 2010-03-31 17:34:15
la source
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;
}
4
répondu bugs king 2012-02-15 19:53:24
la source
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 entiers 2^32.

4
répondu sudeepdino008 2013-06-27 14:09:30
la source
return ((x != 0) && !(x & (x - 1)));

si x est une puissance de deux, son seul 1 bit est en position n . Cela signifie que x – 1 a un 0 en position n . Pour voir pourquoi, rappelez-vous comment une soustraction binaire fonctionne. 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, puisque x n'a pas 1 bits en commun avec x – 1 , x & (x – 1) est 0, et !(x & (x – 1)) est vrai.

4
répondu Prakash Jat 2014-03-05 21:10:10
la source

un nombre est une puissance de 2 s'il contient seulement 1 Bit set. Nous pouvons utiliser cette propriété et la fonction générique countSetBits pour trouver si un nombre est une puissance de 2 ou non.

C'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 pour 0 étant une puissance de 2, car il retourne False pour 0 aussi bien.

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
3
répondu jerrymouse 2012-01-13 14:19:28
la source

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));
}
3
répondu Chethan 2013-04-26 13:16:56
la source

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

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 très bien pour:

IsPowerOfTwo(9223372036854775809)
3
répondu rhodan 2017-07-05 22:18:58
la source

exemple

0000 0001    Yes
0001 0001    No

algorithme

  1. à l'aide d'un masque de bits, divisez NUM la variable en binaire

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

  3. sinon, NUM devient celui qui n'est pas zéro

  4. IF NUM = 1: Return TRUE

  5. sinon, passez à L'Étape 1

complexité

Temps ~ O(log(d))d est le nombre de chiffres binaires

2
répondu Khaled.K 2015-07-28 09:03:04
la source

pour une puissance de 2, la suite est également titulaire.

n & (- n)==n

NOTE: Échec pour n=0, donc besoin de vérifier pour elle

Raison pourquoi cela fonctionne est:

-n est le complément 2s de N. -n aura tout à la gauche de l'ensemble le plus à droite de n inversé par rapport à N. Pour des puissances de 2, il n'y a qu'un bit fixe.

2
répondu FReeze FRancis 2016-05-29 20:45:11
la source

Ce programme en java retourne "true" si le nombre est une puissance de 2 et renvoie "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(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
1
répondu Kaushik Holla 2017-10-24 10:21:07
la source
private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}
0
répondu user134548 2009-07-22 00:29:18
la source

Autres questions sur c# algorithm math