Question 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. Simple
  2. Correct pour tout ulong valeur.

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 je pensais, que diriez-vous de vérifier si log2 x est un nombre exactement rond? Mais quand j'ai vérifié 2 ^ 63 + 1, Math.Log retourné exactement 63 en raison 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 doubles et non en chiffres 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 retourné true pour la mauvaise valeur donnée: 9223372036854775809.

Y a-t-il un meilleur algorithme?


485
2018-03-01 19:01


origine


Réponses:


Il y a une astuce simple pour ce problème:

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

Remarque, cette fonction signalera true pour 0, qui n'est pas un pouvoir de 2. Si vous voulez exclure cela, voici comment:

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

Explication

Tout d'abord l'opérateur binaire bit à bit et l'opérateur de la définition MSDN:

Les opérateurs binaires et les opérateurs binaires sont prédéfinis pour les types entiers et bool. Pour   types intégraux, & calcule le bit logique AND de ses opérandes.   Pour les opérandes booléens, & calcule l'AND logique de ses opérandes; cette   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 boolean (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 savons déjà que 4! = 0 évalue à vrai, si loin si bon. 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 binaire de 4 est 100 et la représentation binaire de 3 est 011 (rappelez-vous la & 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. le & 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. Nous faisons donc le calcul:

100
011
----
000

Le résultat est simplement 0. Nous revenons donc et regardons 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 savons tous que true && true est simplement true, et cela montre que pour notre exemple, 4 est une puissance de 2.


1040
2018-03-01 19:06



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

Et le grand-père d'entre eux, le livre "Hacker's Delight" par Henry Warren, Jr.:

Comme La page de Sean Anderson explique, 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.


88
2018-03-01 20:52



return (i & -i) == i


37
2018-06-17 13:25



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 des bits, comment utiliser correctement les logarithmes, le classique "x &&! (X & (x - 1))", et d'autres.


20
2018-03-02 20:54



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

18
2017-11-26 16:37



Voici un simple C ++ Solution:

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

14
2017-08-25 19:53



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

10
2018-02-14 02:37



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

Nous devons vérifier si exactement l'un des chiffres binaires est un. Donc, il suffit de décaler le chiffre d'un chiffre à la fois et de retourner true si elle est égale à 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 un benchmark) légèrement plus rapide que la méthode originale pour les (vraies) vraies valeurs et beaucoup plus rapide pour les fausses ou 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.


9
2018-03-01 19:06



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.

Quand on soustrait 1 de ce genre de nombres, ils deviennent 0 suivi de n 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 au crux

Que se passe-t-il lorsque nous faisons un AND bit à bit d'un nombre x, qui est un   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 aligner avec ceux de x - 1, entraînant le bit ET à aboutir à 0. Et c'est comme ça que la réponse à une seule ligne mentionnée ci-dessus est correcte.


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

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

Quand on soustrait 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 que le plus à droite   1 va maintenant devenir 1

Une utilisation géniale de cette propriété est de trouver - Combien y a-t-il de 1 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 chiffres qui peut être prouvé par le concept expliqué ci-dessus est "Est-ce que chaque nombre positif peut être représenté comme la somme des puissances de 2?".

Oui, chaque nombre positif peut être représenté par la somme des puissances de 2. Pour tout nombre, prenez sa représentation binaire. 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

7
2017-09-03 21:23



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

6
2017-09-03 18:36