Come trovare il valore più vicino di 2 ^ N a un dato input?

Question

In qualche modo dovuto mantenere il mio programma in esecuzione fino a quando l'uscita della funzione Exponent supera il valore di ingresso, quindi confrontalo con l'uscita precedente della funzione Exponent.Come farei qualcosa del genere, anche se in pseudocodice solo?

Answer 1

.
1. Trova logaritmo da base 2 dal numero dato=> x:= log (2, ingresso)
2. Arrotonda il valore acquisito nel passaggio 1 sia su e giù=> y:= round (x), z:= round (x) + 1
3. Trova 2 ^ y, 2 ^ z, confrontali entrambi con input e scegli quello che si adatta meglio a

Answer 2

A seconda della lingua che stai utilizzando, puoi farlo facilmente usando le operazioni bit a bit.Volete il valore con un singolo set a 1 bit maggiore rispetto a un bit più alto impostato nel valore di ingresso o sul valore con un bit più alto impostato nel valore di ingresso.

Se si imposta tutti i bit al di sotto del bit di set più alto su 1, quindi aggiungi uno finisci con la successiva potenza maggiore di due.È possibile spostare questo per ottenere la successiva potenza inferiore di due e scegliere la più vicina dei due.

unsigned closest_power_of_two(unsigned value)
{
    unsigned above = (value - 1); // handle case where input is a power of two
    above |= above >> 1;          // set all of the bits below the highest bit
    above |= above >> 2;
    above |= above >> 4;
    above |= above >> 8;
    above |= above >> 16;
    ++above;                      // add one, carrying all the way through
                                  // leaving only one bit set.

    unsigned below = above >> 1;  // find the next lower power of two.

    return (above - value) < (value - below) ? above : below;
}

.

Vedi Bit Twidddling Hacks per altri trucchi simili.

Answer 3

Oltre al looping c'è anche una soluzione che potrebbe essere più veloce a seconda di come il compilatore mapisce l'istruzione NLZ:

public int nextPowerOfTwo(int val) {
   return 1 << (32 - Integer.numberOfLeadingZeros(val - 1)); 
}

.

Nessun ciclo esplicito e certamente più efficiente delle soluzioni che utilizzano Math.pow.Difficile dire di più senza guardare quale codice il compilatore genera per numberOfLeadingZeros.

Con che possiamo quindi facilmente ottenere la potenza inferiore di 2 e quindi confrontare quale è più vicino - l'ultima parte deve essere fatta per ogni soluzione che mi sembra.

Answer 4

Imposta X a 1.

while x

Quindi restituire X o X / 2, a seconda di quale sia più vicino al bersaglio.

Answer 5

public static int neareastPower2(int in) {
    if (in <= 1) {
        return 1;
    }
    int result = 2;

    while (in > 3) {
        in = in >> 1;
        result = result << 1;
    }

    if (in == 3) {
        return result << 1;
    } else {
        return result;
    }
}

.

Answer 6

Userò 5 come input per un esempio facile invece di 50.

.
• Converti l'ingresso per bit / byte, in questo caso 101
• Dal momento che stai cercando poteri di due, la tua risposta sarà tutto del modulo 10000 ... 00 (uno con una certa quantità di zeri).Si prende il valore di input (3 bit) e calcola il valore intero di 100 (3 bit) e 1000 (4 bit).L'intero 100 sarà più piccolo quindi l'input, il numero intero 1000 sarà maggiore.
• Si calcola la differenza tra l'input e i due valori possibili e usa la più piccola.In questo caso 100= 4 (differenza di 1) mentre 1000= 8 (differenza di 3), quindi la risposta cercata è 4

Answer 7

public static int neareastPower2(int in) {
    return (int) Math.pow(2, Math.round(Math.log(in) / Math.log(2)));
}

Answer 8

Here's the pseudo code for a function that takes the input number and returns your answer.

int findit( int x) {
  int a = int(log(x)/log(2));
  if(x >= 2^a + 2^(a-1))
    return 2^(a+1)
  else
    return 2^a
}

Answer 9

Here's a bitwise solution--it will return the lessor of 2^N and 2^(N+1) in case of a tie. This should be very fast compare to invoking the log() function

let mask = (~0 >> 1) + 1

while ( mask > value )
    mask >> 1

return ( mask & value == 0 ) ? mask : mask << 1