¿Cómo se calcula log base 2 en Java para enteros?

Esta es la función que uso para este cálculo:

public static int binlog( int bits ) // returns 0 for bits=0
{
    int log = 0;
    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
    if( bits >= 256 ) { bits >>>= 8; log += 8; }
    if( bits >= 16  ) { bits >>>= 4; log += 4; }
    if( bits >= 4   ) { bits >>>= 2; log += 2; }
    return log + ( bits >>> 1 );
}

Es ligeramente más rápido que Integer.numberOfLeadingZeros() (20-30%) y casi 10 veces más rápido (jdk 1.6 x64) que una Matemática.implementación basada en log() como esta:

private static final double log2div = 1.000000000001 / Math.log( 2 );
public static int log2fp0( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return (int) ( Math.log( bits & 0xffffffffL ) * log2div );
}

Ambas funciones devuelven los mismos resultados para todos los valores de entrada posibles.

Actualización: El Java 1.7 server JIT es capaz de reemplazar algunas funciones matemáticas estáticas con implementaciones alternativas basadas en los intrínsecos de la CPU. Uno de esas funciones es Entero.numberOfLeadingZeros(). Por lo tanto, con una máquina virtual de servidor 1.7 o más reciente, una implementación como la de la pregunta es en realidad un poco más rápida que la binlog anterior. Desafortunadamente el JIT del cliente no parece tener esta optimización.

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

Esta implementación también devuelve los mismos resultados para todos los 2^32 posibles valores de entrada que las otras dos implementaciones que publiqué anteriormente.

Aquí están los tiempos de ejecución reales en mi PC (Sandy Bridge i7):

JDK 1.7 VM cliente de 32 Bits:

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

JDK 1.7 x64 server VM:

binlog:          5.8s
log2nlz:         5.1s
log2fp:         89.5s
log(x)/log(2): 108.1s

Este es el código de prueba:

int sum = 0, x = 0;
long time = System.nanoTime();
do sum += log2nlz( x ); while( ++x != 0 );
time = System.nanoTime() - time;
System.out.println( "time=" + time / 1000000L / 1000.0 + "s -> " + sum );

Intenta Math.log(x) / Math.log(2)

Puede usar la identidad

            log[a]x
 log[b]x = ---------
            log[a]b

Así que esto sería aplicable para log2.

            log[10]x
 log[2]x = ----------
            log[10]2

Simplemente conecte esto al método java Math log10....

Http://mathforum.org/library/drmath/view/55565.html

Por qué no:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}

Existe la función en las bibliotecas de guayaba:

LongMath.log2()

Así que sugiero usarlo.

Para agregar a la respuesta x4u, que le da el piso del registro binario de un número, esta función devuelve el techo del registro binario de un número:

public static int ceilbinlog(int number) // returns 0 for bits=0
{
    int log = 0;
    int bits = number;
    if ((bits & 0xffff0000) != 0) {
        bits >>>= 16;
        log = 16;
    }
    if (bits >= 256) {
        bits >>>= 8;
        log += 8;
    }
    if (bits >= 16) {
        bits >>>= 4;
        log += 4;
    }
    if (bits >= 4) {
        bits >>>= 2;
        log += 2;
    }
    if (1 << log < number)
        log++;
    return log + (bits >>> 1);
}

Vamos a añadir:

int[] fastLogs;

private void populateFastLogs(int length) {
    fastLogs = new int[length + 1];
    int counter = 0;
    int log = 0;
    int num = 1;
    fastLogs[0] = 0;
    for (int i = 1; i < fastLogs.length; i++) {
        counter++;
        fastLogs[i] = log;
        if (counter == num) {
            log++;
            num *= 2;
            counter = 0;
        }
    }
}

Fuente: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

Para calcular la base logarítmica 2 de n, se puede usar la siguiente expresión:

double res = log10(n)/log10(2);