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

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

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

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

Ответы

Ответ 2

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

Ответ 3

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

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

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

  • Оцените 32*i+b.

Ответ 4

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

Ответ 5

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

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

Ответ 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). Журнал основан на двух.