¿Cómo encontrar el valor más cercano de 2^N a una entrada determinada?

Question

De alguna manera tengo que mantener mi programa ejecutándose hasta que la salida de la función exponente exceda el valor de entrada, y luego compararlo con la salida anterior de la función exponente.¿Cómo haría algo así, aunque sea solo en pseudocódigo?

Answer 1

1. Encuentre logaritmo a base 2 a partir del número dado=> x:= log (2, entrada)
2. redondeando el valor adquirido en el paso 1 tanto arriba como hacia abajo=> y:= redondo (x), z:= redondo (x) + 1
3. Encuentra 2 ^ y, 2 ^ Z, compáralos ambos con entrada y elija el que se adapte mejor a

Answer 2

Dependiendo de qué idioma está usando, puede hacerlo fácilmente usando las operaciones de bits.Usted desea que el valor con un solo 1 bit se configure más que el más alto que se establece en el valor de entrada, o el valor con el ajuste de un bit más alto en el valor de entrada.

Si establece todos los bits por debajo del bits de ajuste más alto a 1, luego agregue uno que termine con la siguiente mayor potencia de dos.Puede cambiar correctamente esto para obtener la siguiente potencia más baja de dos y elija el más cercano a los dos.

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

Consulte bit twiddling hacks para otros trucos similares.

Answer 3

Aparte del bucle, también hay una solución que puede ser más rápida dependiendo de cómo el compilador asigne la instrucción nlz:

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

Sin bucles explícitos y ciertamente más eficientes que las soluciones que utilizan Math.pow.Es difícil decir más sin mirar para qué código genera el compilador numberOfLeadingZeros.

Con eso, podemos obtener fácilmente la potencia más baja de 2 y luego comparar cuál está más cerca; me parece que la última parte debe hacerse para cada solución.

Answer 4

establecido x a 1.

Mientras X

Luego, simplemente devuelva x o x / 2, lo que esté más cerca del objetivo.

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

Usaré 5 como entrada para un ejemplo fácil en lugar de 50.

• Convierte la entrada a bits / bytes, en este caso 101
• Dado que está buscando poderes de dos, su respuesta será del formulario 10000 ... 00 (una con una cierta cantidad de ceros).Usted toma el valor de entrada (3 bits) y calcula el valor entero de 100 (3 bits) y 1000 (4 bits).El entero 100 será más pequeño que la entrada, el entero 1000 será más grande.
• Calcula la diferencia entre la entrada y los dos valores posibles y use la más pequeña.En este caso 100= 4 (diferencia de 1) mientras 1000= 8 (diferencia de 3), por lo que la respuesta buscada es 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