c# opérateur - Comment vérifier si un nombre est une puissance de 2





x² vb (18)


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.

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. Corriger 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 << 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 log 2 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. 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 s 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;
}

Cela est retourné true pour la valeur erronée donnée: 9223372036854775809 .

Y a-t-il un meilleur algorithme?




Voici une solution C++ simple:

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



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 http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 explique la http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 , l'expression ((x & (x - 1)) == 0) indique incorrectement que 0 est une puissance de 2. Il suggère d'utiliser:

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

pour corriger ce problème.




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

Une puissance de deux, exprimée en binaire, 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 types de nombres, ils deviennent 0 suivis de n et encore n est comme 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 AND binaire 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 s'alignent avec ceux de x - 1 , ce qui fait que le bit AND se termine par 0. Et c'est ainsi que nous avons la réponse de ligne unique mentionnée ci-dessus droite.

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

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

Quand 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 que 1 le plus à droite devienne 1

Une utilisation géniale de cette propriété est de trouver - 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 x donné 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 "Est-ce que chaque nombre positif peut être représenté comme la somme des puissances de 2?" .

Oui, tout 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 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



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

n & (- n) == n

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




Il y a une astuce 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

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 les types entiers, & calcule le bit logique AND de ses opérandes. Pour les opérandes booléens, & calcule l'AND 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 joue:

La fonction renvoie boolean (true / false) et accepte un paramètre entrant de type unsigned long (x, dans ce cas). Laissez-nous pour simplifier supposer 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 évalue à vrai, si loin si bon. Mais qu'en est-il de:

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

Cela se traduit bien sûr par:

((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 & prend la représentation binaire de ces nombres.

100 = 4
011 = 3

Imaginez ces valeurs empilées comme une addition élémentaire. L'opérateur & dit que si les deux valeurs sont égales à 1 alors le résultat est 1, sinon c'est 0. So 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.




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



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



Exemple

0000 0001    Yes
0001 0001    No

Algorithme

  1. En utilisant 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 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 binaires




Amélioration de la réponse de @ user134548, sans arithmétique des 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)



bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 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;
}



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



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



Ce programme en java renvoie "true" si nombre 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(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



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 voir pourquoi, rappelez-vous comment fonctionne une soustraction binaire. En soustrayant 1 de x , l'emprunt se propage tout le long de 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) vaut 0, et !(x & (x – 1)) est vrai.




return (i & -i) == i




Depuis que je suis le détenteur du record du monde actuel pour le plus de chiffres de pi, je vais ajouter mes deux cents :

À moins que vous définissiez réellement un nouveau record du monde, la pratique courante consiste simplement à vérifier les chiffres calculés par rapport aux valeurs connues. C'est assez simple.

En fait, j'ai une page Web qui liste des extraits de chiffres dans le but de vérifier les calculs à leur encontre: http://www.numberworld.org/digits/Pi/

Mais quand vous entrez dans un territoire de record du monde, il n'y a rien à comparer.

Historiquement, l'approche standard pour vérifier que les chiffres calculés sont corrects est de recalculer les chiffres en utilisant un second algorithme. Donc, si l'un ou l'autre calcul est mauvais, les chiffres à la fin ne correspondront pas.

Cela fait généralement plus que doubler le temps nécessaire (puisque le second algorithme est généralement plus lent). Mais c'est la seule façon de vérifier les chiffres calculés une fois que vous avez erré dans le territoire inexploré de chiffres jamais-avant-calculés et un nouveau record du monde.

À l'époque où les supercalculateurs établissaient les records, deux algorithmes AGM différents étaient couramment utilisés:

Ce sont tous deux des algorithmes O(N log(N)^2) qui ont été assez faciles à implémenter.

Cependant, de nos jours, les choses sont un peu différentes. Dans les trois derniers records du monde, au lieu d'effectuer deux calculs, nous avons effectué un seul calcul en utilisant la formule la plus rapide connue (formule Chudnovsky ):

Cet algorithme est beaucoup plus difficile à implémenter, mais il est beaucoup plus rapide que les algorithmes AGM.

Ensuite, nous vérifions les chiffres binaires en utilisant les formules BBP pour l'extraction des chiffres .

Cette formule vous permet de calculer des nombres binaires arbitraires sans calculer tous les chiffres avant. Il est donc utilisé pour vérifier les derniers chiffres binaires calculés. Par conséquent, il est beaucoup plus rapide qu'un calcul complet.

L'avantage de ceci est:

  1. Un seul calcul coûteux est nécessaire.

L'inconvénient est:

  1. Une mise en œuvre de la formule Bailey-Borwein-Plouffe (BBP) est nécessaire.
  2. Une étape supplémentaire est nécessaire pour vérifier la conversion de la base de données binaires en décimales.

J'ai passé en revue certains détails de pourquoi la vérification des derniers chiffres implique que tous les chiffres sont corrects. Mais il est facile de voir cela puisque toute erreur de calcul se propagera aux derniers chiffres.

Maintenant, cette dernière étape (vérification de la conversion) est en fait assez importante. L'un des précédents détenteurs de records du monde nous a effectivement appelés parce que, dans un premier temps, je n'ai pas donné une description suffisante de la façon dont cela fonctionnait.

J'ai donc extrait cet extrait de mon blog:

N = # of decimal digits desired
p = 64-bit prime number

Calculer A en utilisant l'arithmétique de base 10 et B en utilisant l'arithmétique binaire.

Si A = B , alors avec une "probabilité extrêmement élevée", la conversion est correcte.

Pour plus de lecture, voir mon blog post Pi - 5 Trillion Digits .





c# algorithm math