Как вы вычисляете базу данных 2 в Java для целых чисел?

Ответ 1

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

Обычно я стараюсь избегать вычислений FP, когда это возможно.

Операции с плавающей точкой не являются точными. Вы не можете точно знать, что будет оценивать (int)(Math.log(65536)/Math.log(2)). Например, Math.ceil(Math.log(1<<29) / Math.log(2)) - 30 на моем ПК, где математически это должно быть ровно 29. Я не нашел значение для x, где (int)(Math.log(x)/Math.log(2)) терпит неудачу (только потому, что существует только 32 "опасных" значения), но это не означает, что он будет работать одинаково на любом ПК.

Обычным трюком здесь является использование "эпсилон" при округлении. Как (int)(Math.log(x)/Math.log(2)+1e-10) никогда не терпеть неудачу. Выбор этого "эпсилон" не является тривиальной задачей.

Больше демонстрации, используя более общую задачу - пытаться реализовать int log(int x, int base):

Код тестирования:

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

Если мы используем наиболее прямолинейную реализацию логарифма,

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

это печатает:

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
...

Чтобы полностью избавиться от ошибок, мне пришлось добавить epsilon, который находится между 1e-11 и 1e-14. Не могли бы вы сказать это перед тестированием? Я определенно не мог.

Ответ 2

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

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), чем реализация на основе Math.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 );
}

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

Update: Сервер JIT Java 1.7 может заменить несколько статических математических функций альтернативными реализациями, основанными на внутреннем процессоре. Одна из этих функций - Integer.numberOfLeadingZeros(). Таким образом, с 1,7 или более новой виртуальной машиной VM реализация, подобная той, что находится в вопросе, на самом деле немного выше, чем 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 Бит клиентской виртуальной машины:

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

JDK 1.7 x64 сервер 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 );

Ответ 3

Попробуйте Math.log(x) / Math.log(2)

Ответ 4

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

            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

Ответ 5

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

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

Ответ 6

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

LongMath.log2()

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

Ответ 7

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

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

Ответ 8

пусть добавляет:

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

Ответ 9

Некоторые случаи просто работали, когда я использовал Math.log10:

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

Ответ 10

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

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