java - sirve - Forma rápida de encontrar exponente de la potencia superior más cercana de 2.

potencia java codigo

Question

Si tengo un número a , quiero el valor de x en b = 2 ^ x , donde b es la siguiente potencia de 2 mayor que a .

En caso de que se haya perdido la etiqueta, esta es Java, y a es un int. Estoy buscando la manera más rápida de hacer esto. Por lo tanto, mi solución es utilizar twiddling de bits para obtener b , luego hacer (int) (log ( b ) / log (2)), pero siento que debe haber un método más rápido que no implique dividir dos números de punto.

Answer 1

¿Qué hay de a == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(a - 1) a == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(a - 1) ? Eso evita por completo el punto flotante. Si sabe que a nunca es 0, puede omitir la primera parte.

Answer 2

¿Qué tal dividir y conquistar? Como en:

b = 0;
if (a >= 65536){a /= 65536; b += 16;}
if (a >= 256){a /= 256; b += 8;}
if (a >= 16){a /= 16; b += 4;}
if (a >= 4){a /= 4; b += 2;}
if (a >= 2){a /= 2; b += 1;}

Suponiendo que a no está firmado, las divisiones deben ser simplemente cambios de bits.

Un IF-tree binario con 32 hojas debería ser aún más rápido, obteniendo la respuesta en 5 comparaciones. Algo como:

if (a >= (1<<0x10)){
  if (a >= (1<<0x18)){
    if (a >= (1<<0x1C)){
      if (a >= (1<<0x1E)){
        if (a >= (1<<0x1F)){
          b = 0x1F;
        } else {
          b = 0x1E;
        }
      } else {
        if (a >= (1<<0x1D)){
          b = 0x1D;
        } else {
          b = 0x1C;
        }
      }
   etc. etc.

Answer 3

Aquí está mi código para el mismo. ¿Será esto más rápido?

 int a,b,x,y;
    Scanner inp = new Scanner(System.in);
    a = inp.nextInt();
    y = (int) (Math.log(a)/Math.log(2));
    x = y +1;
    System.out.println(x);

Answer 4

Java proporciona una función que se redondea a la potencia más cercana de 2. Por lo tanto, a!=Integer.highestOneBit(a)?2*Integer.highestOneBit(a):a es una solución ligeramente más bonita, suponiendo que a es positiva.

El almacenamiento de Integer.highestOneBit(a) en una variable puede mejorar aún más el rendimiento y la legibilidad.

Answer 5

No necesariamente más rápido, sino un trazador de líneas:

int nextPowerOf2(int num)
{
    return num == 1 ? 1 : Integer.highestOneBit(num - 1) * 2;
}

Answer 6

Para agregar a la respuesta de Jeremiah Willcock, si desea el valor del poder de 2 en sí, entonces querrá:

(int) Math.pow(2, (a == 0) ? 0 : 32 - Integer.numberOfLeadingZeros(numWorkers));

Answer 7

Si alguien está buscando un código de "twiddling de bits" que Andy menciona, podría ser algo como esto: (si la gente tiene mejores maneras, ¡debería compartir!)

    public static int nextPowerOf2(final int a)
    {
        int b = 1;
        while (b < a)
        {
            b = b << 1;
        }
        return b;
    }

Answer 8

Si necesita una respuesta que funcione para enteros o punto flotante, ambos deberían funcionar:

Math.floor(Math.log(a) * 1.4426950408889634073599246810019) + 1 que Math.floor(Math.log(a) * 1.4426950408889634073599246810019) + 1 sería su mejor apuesta si no quiere hacer un poco de twiddling.

Si desea dividir en bits, puede usar Double.doubleToLongBits(a) y luego simplemente extraer el exponente. Estoy pensando ((Double.doubleRawToLongBits(a) >>> 52) & 0x7ff) - 1022 debería hacer el truco.

Answer 9

solo haz lo siguiente:

extraiga el bit más alto utilizando este método (modificado desde hdcode):

int msb(int x) {
   if (pow2(x)) return x;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >> 16);
   x = x | (x >> 24);
   return x - (x >> 1);
}

int pow2(int n) {
   return (n) & (n-1) == 0;
}

combinando ambas funciones en esta función para obtener un número ''b'', que es la siguiente potencia de 2 de un número dado ''a'':

int log2(int x) {
    int pow = 0;
    if(x >= (1 << 16)) { x >>= 16; pow +=  16;}
    if(x >= (1 << 8 )) { x >>=  8; pow +=   8;}
    if(x >= (1 << 4 )) { x >>=  4; pow +=   4;}
    if(x >= (1 << 2 )) { x >>=  2; pow +=   2;}
    if(x >= (1 << 1 )) { x >>=  1; pow +=   1;}
    return pow;
}

Saludos cordiales, Dave