Как вычислить логарифм с основанием 2 в Java для целых чисел?

это функция, которую я использую для такого расчета:

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

это немного быстрее, чем integer.numberOfLeadingZeros () (20-30%) и почти в 10 раз быстрее (jdk 1.6 x64), чем математика.log () на основе реализации, как этот:

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

обе функции возвращают одинаковые результаты для всех возможных входных значений.

обновление: Java 1.7 server JIT способен заменить несколько статических математических функций альтернативными реализациями на основе встроенных процессоров. Одна из этих функций является целочисленной.numberOfLeadingZeros (). Таким образом, с 1.7 или более новой серверной виртуальной машиной реализация, подобная той, о которой идет речь, на самом деле немного быстрее, чем binlog выше. К сожалению, клиент JIT, похоже, не имеет этой оптимизации.

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

эта реализация также возвращает те же результаты для всех 2^32 возможных входных значений, что и две другие реализации, которые я опубликовал выше.

вот фактическое время выполнения на мой компьютер (Sandy Bridge i7):

JDK 1.7 32 бит клиент VM:

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

это тестовый код:

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

попробовать Math.log(x) / Math.log(2)

вы можете использовать удостоверение

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

Так что это будет применимо для log2.

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

просто подключите это к методу java Math log10....

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

почему бы и нет:

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

есть функция в библиотеках guava:

LongMath.log2()

поэтому я предлагаю использовать его.

чтобы добавить к ответу x4u, который дает вам пол двоичного журнала числа, эта функция возвращает ceil двоичного журнала числа:

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

добавим:

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

Источник:https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

для вычисления логарифмической базы 2 из n можно использовать следующее выражение:

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