Como você calcula a base de log 2 em Java para números inteiros?

Eu uso a seguinte função para calcular a base de log 2 para números inteiros:

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

Tem desempenho ideal?

Alguém sabe a função pronta da API J2SE para esse fim?

UPD1 Surpreendentemente para mim, a aritmética de ponto flutuante parece ser mais rápida que a aritmética de número inteiro.

UPD2 Devido a comentários, conduzirei uma investigação mais detalhada.

UPD3 Minha função aritmética inteira é 10 vezes mais rápida que Math.log (n) /Math.log (2).

Se você estiver pensando em usar ponto flutuante para ajudar na aritmética de números inteiros, tenha cuidado.

Eu costumo tentar evitar cálculos de FP sempre que possível.

As operações de ponto flutuante não são exatas. Você nunca pode ter certeza do que (int)(Math.log(65536)/Math.log(2))avaliará. Por exemplo, Math.ceil(Math.log(1<<29) / Math.log(2))é 30 no meu PC, onde matematicamente deveria ser exatamente 29. Não encontrei um valor para x em que (int)(Math.log(x)/Math.log(2))falha (apenas porque existem apenas 32 valores "perigosos"), mas isso não significa que funcionará da mesma maneira. da mesma maneira em qualquer PC.

O truque usual aqui é usar "epsilon" ao arredondar. Como (int)(Math.log(x)/Math.log(2)+1e-10)nunca deve falhar. A escolha deste "epsilon" não é uma tarefa trivial.

Mais demonstração, usando uma tarefa mais geral - tentando implementar int log(int x, int base):

O código de teste:

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

Se usarmos a implementação mais direta do logaritmo,

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

isto 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 me livrar completamente dos erros, tive que adicionar o epsilon, que fica entre 1e-11 e 1e-14. Você poderia ter dito isso antes do teste? Eu definitivamente não podia.

Esta é a função que eu 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 );
}

É um pouco mais rápido que Integer.numberOfLeadingZeros () (20-30%) e quase 10 vezes mais rápido (jdk 1.6 x64) que uma implementação baseada em 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 as funções retornam os mesmos resultados para todos os possíveis valores de entrada.

Atualização: O servidor Java 1.7 JIT é capaz de substituir algumas funções matemáticas estáticas por implementações alternativas baseadas em intrínsecas da CPU. Uma dessas funções é Integer.numberOfLeadingZeros (). Portanto, com uma VM de servidor 1.7 ou mais recente, uma implementação como a da pergunta é realmente um pouco mais rápida que a binloganterior. Infelizmente, o JIT do cliente não parece ter essa otimização.

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

Essa implementação também retorna os mesmos resultados para todos os 2 ^ 32 possíveis valores de entrada que as outras duas implementações postadas acima.

Aqui estão os tempos de execução reais no meu PC (Sandy Bridge i7):

VM do cliente JDK 1.7 32 bits:

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

VM do servidor JDK 1.7 x64:

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

Este é o código de teste:

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

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

você pode usar a identidade

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

portanto, isso seria aplicável ao log2.

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

basta conectar isso ao método java Math log10 ....

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

Por que não:

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

Existe a função nas bibliotecas da goiaba:

LongMath.log2()

Então eu sugiro usá-lo.

Para adicionar à resposta x4u, que fornece o piso do log binário de um número, essa função retorna o teto do log binário de um 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);
}

Alguns casos funcionaram quando usei o Math.log10:

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

vamos adicionar:

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

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

Para calcular a base de log 2 de n, a seguinte expressão pode ser usada:

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