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

Question

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.

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 ensuite j'ai pensé, comment vérifier si log_{<code>2</code>}x est un nombre exactement rond ? Mais quand j'ai vérifié pour 2^63+1, Math.Log a donné exactement 63 à cause de l'arrondi. J'ai donc vérifié si 2 à la puissance 63 est égal au nombre d'origine - et c'est le cas, car le calcul est fait en double et non en nombre exact :

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 .

Existe-t-il un meilleur algorithme ?

Answer 1

Il existe une astuce simple pour résoudre ce problème :

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

Pour être complet, le zéro n'est pas une puissance de deux. Si vous voulez prendre en compte ce cas limite, voici comment :

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

Explication

Tout d'abord l'opérateur binaire & bitwise de la définition MSDN :

Les opérateurs binaires & sont prédéfinis pour les types intégraux et bool. Pour types intégraux, & calcule le ET logique binaire 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 les deux opérandes sont vrais. 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 passe :

La fonction renvoie un booléen (vrai / faux) et accepte un paramètre entrant de type unsigned long (x, dans ce cas). Pour simplifier, supposons que quelqu'un a passé la valeur 4 et a appelé la fonction comme suit :

bool b = IsPowerOfTwo(4)

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

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

Nous savons déjà que 4 != 0 correspond à true, jusque là 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. Nous avons donc :

100 = 4
011 = 3

Imaginez que ces valeurs s'empilent comme une addition élémentaire. Le site & signifie que si les deux valeurs sont égales à 1, le résultat est 1, sinon il est 0. 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 en arrière et regardons ce que notre déclaration de retour 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 && true est simplement true et cela montre que pour notre exemple, 4 est une puissance de 2.

Answer 2

Voici quelques sites qui documentent et expliquent cette méthode et d'autres astuces de manipulation des bits :

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

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

• http://www.hackersdelight.org/

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

Answer 3

return (i & -i) == i

Answer 4

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

Answer 5

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, la manière d'utiliser correctement les logarithmes, la vérification classique "x && !(x & (x - 1))", et d'autres encore.