¿Cómo se calcula la base de registro 2 en Java para enteros?

Utilizo la siguiente función para calcular la base de registro 2 para enteros:

public static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

¿Tiene un rendimiento óptimo?

¿Alguien sabe la función API J2SE lista para ese propósito?

UPD1 Sorprendentemente para mí, la aritmética de coma flotante parece ser más rápida que la aritmética de enteros.

UPD2 Debido a los comentarios, realizaré una investigación más detallada.

UPD3 Mi función aritmética de enteros es 10 veces más rápida que Math.log (n) /Math.log (2).

Si está pensando en usar coma flotante para ayudar con la aritmética de enteros, debe tener cuidado.

Por lo general, trato de evitar los cálculos de FP siempre que sea posible.

Las operaciones de punto flotante no son exactas. Nunca se puede saber con certeza qué (int)(Math.log(65536)/Math.log(2))evaluará. Por ejemplo, Math.ceil(Math.log(1<<29) / Math.log(2))es 30 en mi PC donde matemáticamente debería ser exactamente 29. No encontré un valor para x donde (int)(Math.log(x)/Math.log(2))falla (solo porque solo hay 32 valores "peligrosos"), pero eso no significa que funcionará de la misma manera en cualquier PC.

El truco habitual aquí es usar "epsilon" al redondear. Como (int)(Math.log(x)/Math.log(2)+1e-10)nunca debería fallar. La elección de este "épsilon" no es una tarea trivial.

Más demostración, utilizando una tarea más general: tratar de implementar int log(int x, int base):

El código de prueba:

static int pow(int base, int power) {
    int result = 1;
    for (int i = 0; i < power; i++)
        result *= base;
    return result;
}

private static void test(int base, int pow) {
    int x = pow(base, pow);
    if (pow != log(x, base))
        System.out.println(String.format("error at %d^%d", base, pow));
    if(pow!=0 && (pow-1) != log(x-1, base))
        System.out.println(String.format("error at %d^%d-1", base, pow));
}

public static void main(String[] args) {
    for (int base = 2; base < 500; base++) {
        int maxPow = (int) (Math.log(Integer.MAX_VALUE) / Math.log(base));
        for (int pow = 0; pow <= maxPow; pow++) {
            test(base, pow);
        }
    }
}

Si usamos la implementación más directa de logaritmo,

static int log(int x, int base)
{
    return (int) (Math.log(x) / Math.log(base));
}

esto imprime:

error at 3^5
error at 3^10
error at 3^13
error at 3^15
error at 3^17
error at 9^5
error at 10^3
error at 10^6
error at 10^9
error at 11^7
error at 12^7
...

Para deshacerme completamente de los errores, tuve que agregar epsilon, que está entre 1e-11 y 1e-14. ¿Podría haber dicho esto antes de la prueba? Definitivamente no pude.

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 implementación basada en Math.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 JIT del servidor Java 1.7 puede reemplazar algunas funciones matemáticas estáticas con implementaciones alternativas basadas en intrínsecos de la CPU. Una de esas funciones es Integer.numberOfLeadingZeros (). Entonces, con una VM 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 binloganterior. Desafortunadamente, el cliente JIT 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 los 2 ^ 32 valores de entrada posibles que las otras dos implementaciones que publiqué anteriormente.

Estos son los tiempos de ejecución reales en mi PC (Sandy Bridge i7):

JDK 1.7 VM de cliente de 32 bits:

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

VM de servidor JDK 1.7 x64:

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

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

puedes usar la identidad

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

entonces 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()

Entonces 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 límite máximo 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);
}

Algunos casos simplemente funcionaron cuando usé Math.log10:

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

agreguemos:

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 de registro 2 de n, se puede usar la siguiente expresión:

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