Comment calculez-vous la base de log 2 en Java pour les entiers?

C'est la fonction que j'utilise pour ce calcul:

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

Il est légèrement plus rapide que Entier.numberOfLeadingZeros () (20-30%) et presque 10 fois plus rapide (jdk 1.6 x64) qu'un Math.implémentation basée sur log() comme celle-ci:

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

Les Deux fonctions renvoient les mêmes résultats pour toutes les valeurs d'entrée possibles.

Mise à Jour: Le serveur Java 1.7 JIT est capable de remplacer quelques fonctions mathématiques statiques par des implémentations alternatives basées sur des intrinsèques CPU. L'un des ces fonctions est de type Entier.numberOfLeadingZeros (). Donc, avec une machine virtuelle de serveur 1.7 ou plus récente, une implémentation comme celle de la question est en fait légèrement plus rapide que binlog ci-dessus. Malheureusement, le client JIT ne semble pas avoir cette optimisation.

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

Cette implémentation renvoie également les mêmes résultats pour toutes les 2^32 valeurs d'entrée possibles que les deux autres implémentations que j'ai postées ci-dessus.

Voici les temps d'exécution réels sur mon PC (Sandy Bridge i7):

JDK 1.7 Machine virtuelle client 32 bits:

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

J'ai besoin d'une machine virtuelle de serveur JDK 1.7 x64:

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

Ceci est le code de test:

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

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

Vous pouvez utiliser l'identité

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

Cela serait donc applicable pour log2.

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

Il suffit de brancher ceci dans la méthode java Math log10....

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

Pourquoi pas:

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

Il y a la fonction dans les bibliothèques de goyave:

LongMath.log2()

Donc je suggère de l'utiliser.

Pour ajouter à la réponse x4u, qui vous donne le plancher du journal binaire d'un nombre, cette fonction renvoie le plafond du journal binaire d'un nombre :

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

Ajoutons:

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

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

Pour calculer la base log 2 de n, l'expression suivante peut être utilisée:

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