Trouver si un nombre est une puissance de deux sans fonction mathématique ou fonction log

Question

Je veux savoir si un numéro entré par l'utilisateur est une puissance de deux ou non.

Mon code ne fonctionne pas.

 public class power_of_two
{  
    public static void main(String args[])  
    {  

        Scanner in=new Scanner(System.in);
        System.out.println("Enter the number : ");
        int num = in.nextInt();

        int other = 1;  
        if(((~num) & 1) == 1)  
        {  
            System.out.println("The number is a power of two");  
        }  
        else  
        {
            System.out.println("The number is a  NOT A power of two");  
        }
    }  
} 
 

Faites-moi savoir comment puis-je trouver la puissance de deux nombres.
Par exemple 8 est une puissance de 2.
22 n'est pas une puissance de 2, etc.

Answer 1

Vous pouvez tester si un entier positif n est une puissance de 2 avec quelque chose comme

(n & (n - 1)) == 0

Si n peut être non-positif (négatif ou égal à zéro), vous devez utiliser

(n > 0) && ((n & (n - 1)) == 0)

---

Si n est vraiment une puissance de 2, puis en binaire, il ressemblera à:

10000000...

donc, n - 1 ressemble

01111111...

et quand nous sommes au niveau du bit ET eux:

  10000000...
& 01111111...
  -----------
  00000000...

Maintenant, si n n'est pas une puissance de 2, alors sa représentation binaire aura quelques autres 1s en plus le leader de 1, ce qui signifie que les deux n et n - 1 auront le même leader de 1 bit (depuis soustrayant 1 ne peut pas désactiver ce peu si il y a un autre 1 dans la représentation binaire quelque part). D'où l' & opération ne peut pas produire de l' 0 si n n'est pas une puissance de 2, &ing les deux bits de n et n - 1 produira 1 dans et de lui-même. Cela suppose bien sûr que l' n est positif.

C'est aussi expliqué dans "algorithme Rapide pour vérifier si un nombre positif est une puissance de deux" sur Wikipédia.

---

Rapide sanity check:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1
2
4
8
16
32
64

Answer 2

Vous pouvez utiliser l' & operator et simplement:

if(num & -num == num) {
    return true;
}

Pourquoi cela fonctionne?

Considérons le nombre 8.
Ce qu'il est en binaire?

0000 0000 0000 0000 0000 0000 0000 1000 (32 bits)

Maintenant, qu'est-ce que -8? (Pourquoi?)^*

1111 1111 1111 1111 1111 1111 1111 1000

Maintenant, ce qu' 8 & -8?

0000 0000 0000 0000 0000 0000 0000 1000   8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &
1111 1111 1111 1111 1111 1111 1111 1000  -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000   8    ¯\_(ツ)_/¯

Considérons maintenant le nombre 7, ce qui est pas une puissance de deux.

0000 0000 0000 0000 0000 0000 0000 0111   7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &                       
1111 1111 1111 1111 1111 1111 1111 1001  -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  != 7  ¯\_(ة_ة)_/¯

Comme mentionné par @arshajii, pensez à ce qui va se passer si num est égal à zéro.. je vais laisser la solution pour vous :)

^{* Une bonne façon de se souvenir de la façon de calculer que: Commencer à partir de la droite bits, pour chaque 0 vous voir, ne pas la changer, quand vous voyez 1, le quitter et de procéder, mais à partir de maintenant, inverser tous les bits.}

Answer 3

 double input = 22;

while(((input != 2) && input % 2 == 0) || input == 1) {
 input = input /2;
}

return input == 2;
 

Continuez à diviser par 2 jusqu'à ce que vous atteigniez 1 ou un nombre impair. S'il atteint 1, c'est une puissance de 2, sinon ce n'est pas le cas.

Answer 4

La solution simple:

 bool isPowerOfTwo(int n) {
    // All values < 1 cannot be (positive, at least) powers of two.
    if (n < 1) return false;

    // Keep shifting bits.
    while (n > 1) {
        // Since n > 1, the low bit set means at least two bits must
        // be set, making n no longer a power of two.
        if (n & 0x1) return false;
        // Throw away the bottom (zero) bit.
        n >>= 1;
    }
    // Only one bit was set, therefore, n is a power of two.
    return true;
}
 

Bien sûr, ce n’est pas aussi optimal que certaines des solutions de trucage de bits (qui sont en effet très intelligentes), mais il est très facile de voir comment cela fonctionne, et de vérifier que cela fonctionne dans votre tête.

Pour l'entrée 4 , on obtient:

 n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true
 

Pour une entrée invalide, comme 5 , on obtient:

 n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)
 

Answer 5

Une solution très simple.

 int n = 8; // any integer and you can take it from user also
for(;n>0;n++){

if(n%2 != 0) {

System.out.println("not a power of two")
return;
} // if ends here

n = n/2;
}// for ends here

System.out.println("power of two")