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

Question

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

Проблема, кажется, действительно проста. Все, что требуется, - найти положение наиболее значимого 1 бита. Есть известный метод PlaseLog, но он не очень быстро, особенно для очень длинных многочисленных слов целых чисел.

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

Answer 1

Является Bit Twiddling Hacks. Что вы ищете?

Answer 2

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

Answer 3

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

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

2. Применить Bit Twiddling Hacks. Чтобы найти двоичный журнал b принадлежащий uint32_t стоимость a[i] Вы нашли на шаге 1.

3. Оценивать 32*i+b.

Answer 4

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

Answer 5

Лучший вариант на верхней части моей головы будет подход 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;
}

Этот алгоритм в основном принесет меня с наибольшим количеством 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 и т. Д.) И выполняют некоторые умножения (которые в этом случае не относятся к (1)).

Answer 6

Вы можете создать массив логарифмов заранее. Это найдет логарифмические значения до журнала (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

Это использует двоичный поиск нахождения ближайшей мощности 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;
}