Как найти двоичный логарифм очень быстро? (O (1) в лучшем случае)

Question

Есть ли какой-нибудь очень быстрый способ найти двоичный логарифм целого числа? Например, учитывая номер x = 52656145834278593348959013841835216159447547700274555627155488768 такой алгоритм должен найти y = log (x, 2), равный 215. x всегда является степенью 2.

Проблема кажется очень простой. Все, что требуется, это найти позицию старшего значащего 1 бита. Существует хорошо известный метод FloorLog, но он не очень быстрый, особенно для очень длинных целых чисел из нескольких слов.

Какой самый быстрый метод?

Answer 1

Является ли Bit Twiddling Hacks тем, что вы ищете?

Answer 2

Быстрый взлом: Большинство представлений чисел с плавающей точкой автоматически нормализуют значения, что означает, что они эффективно выполняют цикл Christoffer Hammarström упомянул в аппаратном обеспечении. Так что простое преобразование целого числа в FP и извлечение показателя степени должно помочь, если числа находятся в пределах диапазона показателей представления FP! (В вашем случае ваш целочисленный ввод требует нескольких машинных слов, поэтому при преобразовании нужно будет выполнить несколько «сдвигов».)

Answer 3

Если целые числа хранятся в uint32_t a[], то мое очевидное решение будет следующим:

1. Запустите линейный поиск по a[], чтобы найти самое высокое ненулевое uint32_t значение a[i] в a[] (проверьте, используя uint64_t для этого поиска, если у вашей машины есть собственный uint64_t поддержка)

2. Примените битовый трюк , чтобы найти двоичный журнал b значения uint32_t a[i], найденного на шаге 1.

3. Оценка 32*i+b.

Answer 4

Ответ зависит от реализации или языка. Любая реализация может хранить количество значащих бит вместе с данными, что часто бывает полезно. Если он должен быть рассчитан, то найдите в этом слове самое старшее слово / конечный элемент и самый старший бит.

Answer 5

Используется двоичный поиск для нахождения ближайшей степени 2.

public static int binLog(int x,boolean shouldRoundResult){
    // assuming 32-bit integer
    int lo=0;
    int hi=31;
    int rangeDelta=hi-lo;
    int expGuess=0;
    int guess;
    while(rangeDelta>1){
        expGuess=(lo+hi)/2; // or (loGuess+hiGuess)>>1
        guess=1<<expGuess;
        if(guess<x){
            lo=expGuess;
        } else if(guess>x){
            hi=expGuess;            
        } else {
            lo=hi=expGuess;
        }
        rangeDelta=hi-lo;
    }
    if(shouldRoundResult && hi>lo){
        int loGuess=1<<lo;
        int hiGuess=1<<hi;
        int loDelta=Math.abs(x-loGuess);
        int hiDelta=Math.abs(hiGuess-x);
        if(loDelta<hiDelta)
            expGuess=lo;
        else
            expGuess=hi;
    } else {
        expGuess=lo;
    }
    int result=expGuess;
    return result;
}

Answer 6

Вы можете заранее создать массив логарифмов. Это позволит найти логарифмические значения до log (N):

#define N 100000
int naj[N];

naj[2] = 1;
for ( int i = 3; i <= N; i++ )
{
    naj[i] = naj[i-1];
    if ( (1 << (naj[i]+1)) <= i )
        naj[i]++;

}

Массив naj - это ваши логарифмические значения. Где naj [k] = log (k). Журнал основан на двух.

Answer 7

Лучшим вариантом на моей голове был бы подход O (log (logn)), использующий бинарный поиск. Вот пример для 64-битного (<= 2^63 - 1) числа (в C ++):

int log2(int64_t num) {
    int res = 0, pw = 0;    
    for(int i = 32; i > 0; i --) {
        res += i;
        if(((1LL << res) - 1) & num)
            res -= i;
    }
    return res;
}

Этот алгоритм в основном предоставит мне наибольшее число разрешений, например (2^res - 1 & num) == 0. Конечно, для любого числа вы можете решить это в аналогичном вопросе:

int log2_better(int64_t num) {
    var res = 0;
    for(i = 32; i > 0; i >>= 1) {
        if( (1LL << (res + i)) <= num )
            res += i;
    }
    return res;
}

Обратите внимание, что этот метод основан на том факте, что операция "сдвиг битов" более или менее равна O (1). Если это не так, вам придется предварительно вычислить либо все степени 2, либо числа вида 2^2^i (2 ^ 1, 2 ^ 2, 2 ^ 4, 2 ^ 8 и т. Д.) И выполнить некоторые умножения (которые в этом случае больше не O (1)).