[c#] Comment vérifier si un nombre est une puissance de 2


Answers

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.

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




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



Voici une solution C++ simple:

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






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, nous décalons simplement le nombre à droite un chiffre à la fois, et renvoyons true s'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 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.




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.




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




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



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



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





Related