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

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

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

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

• http://www.hackersdelight.org /

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.

return (i & -i) == i

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.

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

voici un simple c++ solution:

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

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

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.

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

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

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

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

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.

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.

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

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

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)

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)) où d est le nombre de chiffres binaires

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.

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

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