Trova se un numero è una potenza di due senza funzione matematica o funzione di registro

Voglio scoprire se un utente inserito numero è un potere di due o meno.

Il mio codice non funziona.

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

Fammi sapere come posso trovare la potenza di due numeri.
Ad esempio 8 è un potere di 2.
22 non è una potenza di 2, ecc.

Puoi verificare se un intero positivo n è una potenza di 2 con qualcosa di simile

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

Se n può essere non positivo (cioè negativo o pari a zero), devi usare

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

Se n è veramente una potenza di 2, allora in binario sembrerà:

 10000000... 

così n - 1 sembra

 01111111... 

e quando abbiamo bitwise-AND loro:

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

Ora, se n non è una potenza di 2, la sua rappresentazione binaria avrà altri 1 in aggiunta alla prima 1, il che significa che sia n che n - 1 avranno lo stesso 1 bit iniziale (poiché la sottrazione di 1 non può distriggersre questo bit se c’è un altro 1 nella rappresentazione binaria da qualche parte). Quindi l’operazione & non può produrre 0 se n non è una potenza di 2, poiché & i due bit iniziali di n e n - 1 produrranno 1 in e di se stesso. Questo ovviamente presuppone che n sia positivo.

Questo è anche spiegato in “Algoritmo rapido per verificare se un numero positivo è una potenza di due” su Wikipedia.


Controllo di sanità mentale rapido:

 for (int i = 1; i <= 100; i++) { if ((i & (i - 1)) == 0) System.out.println(i); } 
 1
 2
 4
 8
 16
 32
 64

È ansible utilizzare l’ bitwise AND (&) operator :

 return (num & -num) == num 

Perché funziona?

Considera il numero 8, che cosa è in binario (supponendo 32 bit)?

 0000 0000 0000 0000 0000 0000 0000 1000 

Ora vediamo come viene rappresentato -8? 1

 1111 1111 1111 1111 1111 1111 1111 1000 

Finalmente .. calcoliamo 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 ¯\_(ツ)_/¯ 

Ora facciamo un altro esempio, diciamo 7 , che non è potenza di due.

 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 ¯\_(ة_ة)_/¯ 

Come menzionato da @arshajii, pensa cosa succederà se num è zero .. Lascerò la soluzione per te 🙂

1 Un buon modo per ricordare come calcolare che: Iniziare dal bit più a destra, per ogni 0 che vedi, non cambiarlo, quando vedi 1, lasciarlo e procedere, ma d’ora in poi, inverti tutti i bit. Ho provato a spiegarlo di più qui .

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

Continua a dividerlo per 2 finché non raggiungi 1 o un numero dispari. Se raggiunge 1 è una potenza di 2, altrimenti non lo è.

La soluzione semplice:

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

Naturalmente, questo non è ottimale come alcune delle altre soluzioni di bit-trick (che sono davvero abbastanza intelligenti), ma è molto facile vedere come funziona e verificare che funzioni nella tua testa.

Per l’input 4 , otteniamo:

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

Per un input non valido, come 5 , otteniamo:

 n = 5 (0x101) return false (0x101 & 0x1 => 0x1, which is truthy) 
  public boolean isPowerOfTwo(int n){ boolean isPower=false; int temp=n; while(temp>=2){ if(temp%2==0){ isPower=true; }else{ isPower=false; break; } temp=temp/2; } if(isPower){ System.out.println("power of 2"); }else{ System.out.println("not power of 2"); } return isPower; } 

Una soluzione molto semplice.

 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")