2011-03-09 19 views
19

Si tengo un número un, quiero que el valor de x en b = 2^x, donde b es la siguiente potencia de 2 mayor que a.Una manera rápida de encontrar exponente de la más cercana poder superior de 2

En caso de que haya perdido la etiqueta, esto es Java, y a es un int. Estoy buscando la manera más rápida de hacer esto. Mi solución hasta el momento es utilizar bit-twiddling para obtener b, luego hacer (int) (log (b)/log (2)), pero creo que tiene que haber un método más rápido que no involucre dividiendo dos números de coma flotante.

+0

¿Cuál es la gama de valores de 'x'? ¿Cuál es el tipo de 'a'? –

+0

Como dije en la pregunta, _a_ es un int. _x_ es estrictamente no negativo. –

+0

@Andy: ¿Dónde lo dijiste en la pregunta? Dijiste que tienes un * número * 'a'. Podría haber sido un 'short', un' long' o incluso 'BigInteger'. ¿Puede ser 'Integer.MAX_VALUE', en cuyo caso' x' puede ser 32, pero no más? –

Respuesta

30

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

+0

Sé que _a_ no es cero, entonces puedo simplemente vaya con '32 - Integer.numberOfLeadingZeros (a - 1)'. Esto se ve perfecto. Nunca supo que ese método existía. ¡Gracias! –

+0

¿Qué tal por mucho tiempo? –

+1

También esto no funciona para los números negativos –

0

Si necesita una respuesta que funciona para números enteros o de punto flotante, ambos deben trabajar:

Me gustaría pensar que Math.floor(Math.log(a) * 1.4426950408889634073599246810019) + 1 sería la mejor opción si no quiere hacer cambio de bit.

Si quiere hacer un twiddle, puede usar Double.doubleToLongBits(a) y luego simplemente extraer el exponente. Estoy pensando que ((Double.doubleRawToLongBits(a) >>> 52) & 0x7ff) - 1022 debería hacer el truco.

0

¿Qué tal divide y vencerás? 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 a no tiene signo, las divisiones debe ser sólo de bits turnos.

Un IF-árbol binario con 32 hojas debe ser aún más rápido, obteniendo la respuesta en 5 comparaciones. Algo así 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. 
0

simplemente haga lo siguiente:

extraer el bit más alto mediante el uso de este método (modificado de 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; 
} 

combinar ambas funciones en esta función para obtener un número 'b', ese es el próximo poder 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; 
} 

kind regar ds, de Dave

+0

Voto a la baja. No responde la pregunta. La pregunta es: "Quiero el valor de x en b = 2^x, donde b es la siguiente potencia de 2 mayor o igual a a". (Consulte el comentario de OP para la parte "mayor que o igual a"). Esta respuesta produce b, no x. –

8

Si alguien está buscando un poco de código "bit-jugueteando" que Andy menciona, que podría ser algo como esto: (si la gente tiene mejores formas, debe compartir!)

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

Votación reducida. No responde la pregunta. La pregunta es: "Quiero el valor de x en b = 2^x, donde b es la siguiente potencia de 2 mayor o igual a a". (Consulte el comentario de OP para la parte "mayor que o igual a"). Esta respuesta produce b, no x. –

+0

@jona Eso ' es cierto, si quieres x solo puedes contar el número de iteraciones del ciclo while y devolverlo. No conozco ' lo que ' d nombre ese método :-) – xbakesx

-1

para añadir a la respuesta de Jeremías Willcock, si quieres el valor de la potencia de 2 en sí, entonces usted tendrá que:

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

Aquí es 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); 
1
No

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

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

Voto a la baja. No responde la pregunta. La pregunta es: "Quiero el valor de x en b = 2^x, donde b es la siguiente potencia de 2 mayor o igual a a". (Consulte el comentario de OP para la parte "mayor que o igual a"). Esta respuesta produce b, no x. –

Cuestiones relacionadas