Controlla se il numero è divisibile per una potenza di due [duplicato]
Trova la massima potenza di due che divide x, un numero intero a 64 bit o restituisci -1.
Il caso zero non è definito, poiché si immerge in qualsiasi potenza di due, quindi il tuo metodo può restituire qualsiasi numero.
Ho provato a utilizzare BigInteger.getLowestSetBit()per questo, restituisce la risposta giusta ma è lungi dall'essere ottimale.
Esempio: ingresso -> uscita
- 3 -> -1
- 6 -> 1
- 4256 -> 5
Risposte
Nella Longclasse c'è una comoda funzione statica numberOfTrailingZeros, che fa quasi quello che vuoi, tranne per il fatto che restituisce zero (invece di -1) quando l'input non è divisibile per 2. Puoi gestire questo caso in diversi modi. Ad esempio, estendendo la risposta di @ 0x476f72616e
if ((num & 0x1) == 0)
return Long.numberOfTrailingZeros(num);
else
return -1;
un algoritmo può essere: (pseudocodice)
usa un contatore impostato su zero, metti il numero in un var intvar do{
- spostamento a destra (intero diviso per due) ->dividedvar
- se vardivisa*2 != intvar allora vardivisa = 0 / condizione di uscita /
- else (intvar = sharedvar e counter ++) } mentre sharedvar !=0
Provalo
questo è il modo più semplice:
if ((num & 0x1) == 0)
// it is even
else
// it is odd
sta usando l'aritmetica dei bit. Per fare in modo che questo trovi la potenza più alta puoi usare la ricorsione o il ciclo:
int powerOf2 (int a) {
if ((a & 0x1) == 1)
return 0;
powerOf2 (a >> 1) + 1;
}
o ciclo:
int powerOf2 (int a) {
int pow = 1;
while ((a & 1) != 1) {
pow += 1;
a >>= 1;
}
return pow
}
o per ciclo:
int powerOf2 (int a) {
int pow = 1;
for (;(a & 1) != 1; a >>= 1) {
pow *= 2;
}
}
Funzionerà per un numero positivo, se il numero è negativo (e hai bisogno di quella funzionalità), moltiplica aper -1se è minore di 0.