Mi viene dato un numero n, che è sempre una potenza di 2. Voglio verificare se n è dispari potenza di 2 o anche potenza di 2.
Ad esempio: n = 4, ans = even n = 8, ans = dispari (perché 8 è 2 ^ 3) n = 1024, ans = even.
Posso farlo usando operazioni bit a bit / o un metodo più veloce.
Iniziamo con l'istruzione 'operazioni bit a bit su numeri interi non associati senza significato'. Non testerai se il numero 2 128 ha un esponente pari o no. L'area del problema è vincolata, diciamo, a 32 bit senza segno. Questo potrebbe anche essere facilmente 64 (il tipo di dati long ), ma è più facile digitare numeri a 32 bit.
Il numero 2 n , quando scritto in binario ha esattamente un 1 in esso:
2 0 = 0...0001
2 1 = 0...0010
2 2 = 0...0100
2 3 = 0...1000
e così via. La domanda quindi è "quale operazione bit a bit avrà un valore che è 0 o non 0 quando viene eseguito rispetto a tale numero?"
Il valore sarebbe 2 2 + 2 0 che ci dà 5. Questo pattern si ripete per tutti gli esponenti pari.
Quindi, l'operazione bit a bit è & 5 (o & A ). Il valore di 5 2 è 0101 con i valori dispari come 0 , mentre 10 2 è 1010 con i valori pari come 0 . Questo valore viene quindi eseguito per ogni nyble (mezzo byte) nel numero: il valore a cui siamo interessati è 0101 0101 0101 0101 0101 0101 0101 0101 o 0x55555555
n & 0x55555555 darà un valore di 0 quando la potenza di 2 è dispari e qualche altro valore quando la potenza di 2 è pari. n & 0xAAAAAAAA farà l'opposto ( 0 quando la potenza di 2 è pari e qualche altro valore quando è dispari).
n & 0x55555555 è in effetti n & (2 0 + 2 2 + 2 4 + 2 6 + ... + 2 30 ) che, di nuovo, ci dà la risposta che cerchiamo.
Supponendo che n sia un intero a 32 bit:
Se n e hai con x55555555 > 0 allora anche altro dispari
Supponendo che n sia un intero a 64 bit:
Se n e sei con x5555555555555555 > 0 allora anche altro dispari
Se metti la maschera nella calcolatrice esadecimale, che mostra anche i binari, vedrai che la maschera ha tutti i bit pari impostati:
0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 - 64 bits
or
0101 0101 0101 0101 0101 0101 0101 0101 - 32 bits
Se è noto che n è effettivamente una potenza di 2, allora solo un bit nel numero intero può essere acceso.
Se l'indice di quel bit è pari, la tua risposta è pari (supponendo che gli indici di bit siano basati su 0).
Per i numeri negativi, potresti voler utilizzare il valore assoluto.
E ovviamente, l'assunto è che abbiamo a che fare con numeri interi a 32 o 64 bit, non con numeri in virgola mobile.
È possibile utilizzare il passaggio a destra invece di bit a bit? qualcosa di simile (nessun controllo di input per semplicità):
public bool IsEvenPower(int n)
{
int count = 0;
int remaining = n;
do
{
remaining = remaining >> 1;
count++;
}
while(remaining > 1);
return count % 2 == 0;
}
Trasformerò il mio commento in una risposta, forse otterrò un +1 o due.
L'esponente di una potenza di 2 è anche quando il numero è una potenza di 4.
Cioè, se l'esponente è pari, puoi dividerlo per 2, quindi
2 ^ n = 2 ^ (2 * m) = 4 ^ m
Quindi (pseudocodice)
function isEvenExponent(int n)
return (n % 4) == 0
... o se ti piacciono le operazioni bit a bit
function isEvenExponent(int n)
return (n & 3) == 0
Leggi altre domande sui tag math