Вычислить быстрый потолок базы 2 - PullRequest
Новая
       51

Вычислить быстрый потолок базы 2

38 голосов
/ 17 июля 2010

Что такое быстрый способ вычисления (long int) ceiling(log_2(i)), где входные и выходные данные представляют собой 64-разрядные целые числа? Решения для целых чисел со знаком или без знака являются приемлемыми. Я подозреваю, что лучшим способом будет метод «немного перепутать», подобный найденным здесь , но вместо того, чтобы пытаться самостоятельно, я хотел бы использовать что-то, что уже хорошо протестировано. Общее решение будет работать для всех положительных значений.

Например, значения для 2,3,4,5,6,7,8: 1,2,2,3,3,3,3

Редактировать: Пока что наилучшим маршрутом, по-видимому, является вычисление целочисленной / минимальной базы 2 (позиция MSB) с использованием любого количества быстрых существующих битхаков или методов регистров, а затем добавление одного, если вход не сила двух. Быстрая битовая проверка для степеней двойки - (n&(n-1)).

Редактировать 2: Хороший источник по целочисленным логарифмам и методам начальных нулей - разделы 5-3 и 11-4 в Восторг Хакера Генри Уоррена. Это самое полное лечение, которое я нашел.

Редактировать 3: эта техника выглядит многообещающе: https://stackoverflow.com/a/51351885/365478

Ответы [ 14 ]

1 голос
/ 17 октября 2018

Я дам вам самый быстрый способ для x86-64 на момент написания и общую технику, если у вас есть быстрый пол, который работает для аргументов <2 ^ 63 </strong>, если вы заботитесь ополный диапазон, затем см. ниже.

Я удивлен низким качеством других ответов, потому что они говорят вам, как получить слово, но преобразуют пол очень дорогим способом (используя условные выражения и все!), чтобыпотолок.

Если вы можете быстро получить пол логарифма, например, с помощью __builtin_clzll, то пол очень легко получить следующим образом: 

unsigned long long log2Floor(unsigned long long x) {
    return 63 - __builtin_clzll(x);
}

unsigned long long log2Ceiling(unsigned long long x) {
    return log2Floor(2*x - 1);
}

Это работает, потому чтоон добавляет 1 к результату , если x не является степенью 2 .

См. разницу в ассемблере x86-64 в проводнике компилятора для другой реализации потолка, подобногоэто: 

auto log2CeilingDumb(unsigned long x) {
    return log2Floor(x) + (!!(x & (x - 1)));
}

Дает: 

log2Floor(unsigned long): # @log2Floor(unsigned long)
  bsr rax, rdi
  ret
log2CeilingDumb(unsigned long): # @log2CeilingDumb(unsigned long)
  bsr rax, rdi
  lea rcx, [rdi - 1]
  and rcx, rdi
  cmp rcx, 1
  sbb eax, -1
  ret
log2Ceiling(unsigned long): # @log2Ceiling(unsigned long)
  lea rax, [rdi + rdi]
  add rax, -1
  bsr rax, rax
  ret

Для полного диапазона, это в предыдущем ответе: return log2Floor(x - 1) + 1, это значительно медленнее, так как он использует в x86-64 четыреинструкции по сравнению с тремяБова.

1 голос
/ 03 апреля 2015

Наивный линейный поиск может быть опцией для равномерно распределенных целых чисел, поскольку в среднем требуется чуть менее 2 сравнений (для любого целого размера). 

/* between 1 and 64 comparisons, ~2 on average */
#define u64_size(c) (              \
    0x8000000000000000 < (c) ? 64  \
  : 0x4000000000000000 < (c) ? 63  \
  : 0x2000000000000000 < (c) ? 62  \
  : 0x1000000000000000 < (c) ? 61  \
...
  : 0x0000000000000002 < (c) ?  2  \
  : 0x0000000000000001 < (c) ?  1  \
  :                             0  \
)
1 голос
/ 17 июля 2010

Если у вас есть 80-битные или 128-битные числа с плавающей запятой, приведите к этому типу и затем прочитайте показательные биты. Эта ссылка содержит детали (для целых чисел до 52 бит) и несколько других методов:

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float

Также проверьте источник ffmpeg. Я знаю, что у них очень быстрый алгоритм. Даже если он не может быть напрямую расширен на большие размеры, вы можете легко сделать что-то вроде if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);

0 голосов
/ 28 марта 2014

Код ниже проще и будет работать до тех пор, пока вход x> = 1. вход clog2 (0) получит неопределенный ответ (что имеет смысл, потому что log (0) бесконечность ...) Вы можете добавить ошибку проверка (x == 0), если вы хотите: 

unsigned int clog2 (unsigned int x)
{
    unsigned int result = 0;
    --x;
    while (x > 0) {
        ++result;
        x >>= 1;
    }

    return result;
}

Кстати, код для пола log2 похож: (Опять же, при условии x> = 1) 

unsigned int flog2 (unsigned int x)
{
    unsigned int result = 0;
    while (x > 1) {
        ++result;
        x >>= 1;
    }

    return result;
}
Страница:
...