Controlla se il numero è divisibile per una potenza di due [duplicato]

Aug 25 2020

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

6 harold Aug 25 2020 at 00:24

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;
3 gkab Aug 25 2020 at 00:28

un algoritmo può essere: (pseudocodice)

usa un contatore impostato su zero, metti il ​​numero in un var intvar do{

  1. spostamento a destra (intero diviso per due) ->dividedvar
  2. se vardivisa*2 != intvar allora vardivisa = 0 / condizione di uscita /
  3. else (intvar = sharedvar e counter ++) } mentre sharedvar !=0

Provalo

0x476f72616e Aug 25 2020 at 00:19

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.