Вычислить быстрый потолок базы 2
Какой быстрый способ вычислить (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: эта техника выглядит многообещающе: /questions/36482084/vyichislit-byistryij-potolok-bazyi-2/36482106#36482106
15 ответов
Этот алгоритм уже был опубликован, но следующая реализация очень компактна и должна оптимизироваться в код без веток.
int ceil_log2(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
printf("%d\n", ceil_log2(atol(argv[1])));
return 0;
}
Если вы можете ограничить себя gcc, есть набор встроенных функций, которые возвращают количество начальных нулевых битов и могут использоваться для выполнения того, что вы хотите с небольшой работой:
int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
Если вы компилируете для 64-битных процессоров в Windows, я думаю, что это должно сработать. _BitScanReverse64 является встроенной функцией.
#include <intrin.h>
__int64 log2ceil( __int64 x )
{
unsigned long index;
if ( !_BitScanReverse64( &index, x ) )
return -1LL; //dummy return value for x==0
// add 1 if x is NOT a power of 2 (to do the ceil)
return index + (x&(x-1)?1:0);
}
Для 32-битных систем вы можете эмулировать _BitScanReverse64 с помощью одного или двух вызовов _BitScanReverse. Проверьте старшие 32 бита x, ((long*)&x)[1], затем младшие 32 бита, если необходимо, ((long*)&x)[0].
Самый быстрый подход, который я знаю, использует быстрый log2 округление, объединенная безусловная корректировка входного значения до и после для обработки случая округления, как в lg_down() показано ниже.
/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
return 63U - __builtin_clzl(x);
}
/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
return lg_down(x - 1) + 1;
}
По существу, добавление 1 к округленному результату уже корректно для всех значений, кроме точных степеней двойки (поскольку в этом случае floor а также ceil подходы должны возвращать один и тот же ответ), поэтому достаточно вычесть 1 из входного значения, чтобы обработать этот случай (он не меняет ответ для других случаев) и добавить один к результату.
Это обычно немного быстрее, чем подходы, которые корректируют значение, явно проверяя точные степени двух (например, добавляя !!(x & (x - 1)) срок). Он избегает любых сравнений и условных операций или переходов, более вероятен просто при встраивании, более поддается векторизации и т. Д.
Это основывается на функциональности "подсчитывать начальные биты", предлагаемой большинством процессоров, использующих встроенный модуль clang / icc / gcc __builtin_clzl, но другие платформы предлагают что-то подобное (например, BitScanReverse встроенный в Visual Studio).
К сожалению, это многие возвращают неправильный ответ для log(1), поскольку это приводит к __builtin_clzl(0) который является неопределенным поведением, основанным на документации gcc. Конечно, общая функция "считать ведущие нули" имеет совершенно определенное поведение в нуле, но встроенная функция gcc определяется таким образом, поскольку до расширения ISA BMI на x86 она использовала бы bsr инструкция, которая сама по себе имеет неопределенное поведение.
Вы можете обойти это, если вы знаете, что у вас есть lzcnt инструкция с помощью lzcnt свойственный непосредственно. Большинство платформ, кроме x86, никогда не проходили через bsr ошибка в первую очередь, и, вероятно, также предложить методы для доступа к их инструкции "считать ведущие нули", если они есть.
Используя встроенные в gcc встроенные функции @egosys, вы можете создать несколько полезных макросов. Для быстрого и грубого расчета пола (log2 (x)) вы можете использовать:
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
Для аналогичного ceil (log2 (x)) используйте:
#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
Последний может быть дополнительно оптимизирован с использованием большего числа особенностей gcc, чтобы избежать двойного вызова встроенного, но я не уверен, что вам это нужно здесь.
#include "stdafx.h"
#include "assert.h"
int getpos(unsigned __int64 value)
{
if (!value)
{
return -1; // no bits set
}
int pos = 0;
if (value & (value - 1ULL))
{
pos = 1;
}
if (value & 0xFFFFFFFF00000000ULL)
{
pos += 32;
value = value >> 32;
}
if (value & 0x00000000FFFF0000ULL)
{
pos += 16;
value = value >> 16;
}
if (value & 0x000000000000FF00ULL)
{
pos += 8;
value = value >> 8;
}
if (value & 0x00000000000000F0ULL)
{
pos += 4;
value = value >> 4;
}
if (value & 0x000000000000000CULL)
{
pos += 2;
value = value >> 2;
}
if (value & 0x0000000000000002ULL)
{
pos += 1;
value = value >> 1;
}
return pos;
}
int _tmain(int argc, _TCHAR* argv[])
{
assert(getpos(0ULL) == -1); // None bits set, return -1.
assert(getpos(1ULL) == 0);
assert(getpos(2ULL) == 1);
assert(getpos(3ULL) == 2);
assert(getpos(4ULL) == 2);
for (int k = 0; k < 64; ++k)
{
int pos = getpos(1ULL << k);
assert(pos == k);
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) - 1);
assert(pos == (k < 2 ? k - 1 : k) );
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) | 1);
assert(pos == (k < 1 ? k : k + 1) );
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) + 1);
assert(pos == k + 1);
}
return 0;
}
Следующий фрагмент кода является безопасным и переносимым способом расширения методов plain-C, таких как @dgobbi, для использования встроенных функций компилятора при компиляции с использованием поддерживающих компиляторов (Clang). Размещение этого в верхней части метода приведет к тому, что метод будет использовать встроенную функцию, когда она будет доступна. Когда встроенная функция недоступна, метод возвращается к стандартному C-коду.
#ifndef __has_builtin
#define __has_builtin(x) 0
#endif
#if __has_builtin(__builtin_clzll) //use compiler if possible
return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1)));
#endif
Истинное самое быстрое решение:
Двоичное дерево поиска из 63 записей. Это степени 2 от 0 до 63. Функция одноразовой генерации для создания дерева. Листья представляют лог-базу 2 степеней (в основном, числа 1-63).
Чтобы найти ответ, вы вводите число в дерево и переходите к конечному узлу, большему, чем элемент. Если узел листа в точности равен, результатом является значение листа. В противном случае результатом является значение листа + 1.
Сложность фиксируется на O(6).
Приведенный ниже код проще и будет работать до тех пор, пока вход x >= 1. вход clog2(0) получит неопределенный ответ (что имеет смысл, потому что log (0) бесконечность...). Вы можете добавить проверку ошибок для (х == 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;
}
Я протестировал несколько реализаций 64-битного "старшего бита". Самый "бесплатный" код на самом деле не самый быстрый.
Это мое highest-bit.c исходный файл:
int highest_bit_unrolled(unsigned long long n)
{
if (n & 0xFFFFFFFF00000000) {
if (n & 0xFFFF000000000000) {
if (n & 0xFF00000000000000) {
if (n & 0xF000000000000000) {
if (n & 0xC000000000000000)
return (n & 0x8000000000000000) ? 64 : 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit_bs(unsigned long long n)
{
const unsigned long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}
int highest_bit_shift(unsigned long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
static int count_ones(unsigned long long d)
{
d = ((d & 0xAAAAAAAAAAAAAAAA) >> 1) + (d & 0x5555555555555555);
d = ((d & 0xCCCCCCCCCCCCCCCC) >> 2) + (d & 0x3333333333333333);
d = ((d & 0xF0F0F0F0F0F0F0F0) >> 4) + (d & 0x0F0F0F0F0F0F0F0F);
d = ((d & 0xFF00FF00FF00FF00) >> 8) + (d & 0x00FF00FF00FF00FF);
d = ((d & 0xFFFF0000FFFF0000) >> 16) + (d & 0x0000FFFF0000FFFF);
d = ((d & 0xFFFFFFFF00000000) >> 32) + (d & 0x00000000FFFFFFFF);
return d;
}
int highest_bit_parallel(unsigned long long n)
{
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return count_ones(n);
}
int highest_bit_so(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
int highest_bit_so2(unsigned long long value)
{
int pos = 0;
if (value & (value - 1ULL))
{
pos = 1;
}
if (value & 0xFFFFFFFF00000000ULL)
{
pos += 32;
value = value >> 32;
}
if (value & 0x00000000FFFF0000ULL)
{
pos += 16;
value = value >> 16;
}
if (value & 0x000000000000FF00ULL)
{
pos += 8;
value = value >> 8;
}
if (value & 0x00000000000000F0ULL)
{
pos += 4;
value = value >> 4;
}
if (value & 0x000000000000000CULL)
{
pos += 2;
value = value >> 2;
}
if (value & 0x0000000000000002ULL)
{
pos += 1;
value = value >> 1;
}
return pos;
}
Это highest-bit.h:
int highest_bit_unrolled(unsigned long long n);
int highest_bit_bs(unsigned long long n);
int highest_bit_shift(unsigned long long n);
int highest_bit_parallel(unsigned long long n);
int highest_bit_so(unsigned long long n);
int highest_bit_so2(unsigned long long n);
И основная программа (извините за все скопировать и вставить):
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "highest-bit.h"
double timedelta(clock_t start, clock_t end)
{
return (end - start)*1.0/CLOCKS_PER_SEC;
}
int main(int argc, char **argv)
{
int i;
volatile unsigned long long v;
clock_t start, end;
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_unrolled(v);
}
end = clock();
printf("highest_bit_unrolled = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_parallel(v);
}
end = clock();
printf("highest_bit_parallel = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_bs(v);
}
end = clock();
printf("highest_bit_bs = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_shift(v);
}
end = clock();
printf("highest_bit_shift = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so(v);
}
end = clock();
printf("highest_bit_so = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so2(v);
}
end = clock();
printf("highest_bit_so2 = %6.3fs\n", timedelta(start, end));
return 0;
}
Я пробовал это различные Intel x86 коробки, старые и новые.
highest_bit_unrolled (развернутый бинарный поиск) значительно быстрее, чем highest_bit_parallel (Бит без операций). Это быстрее чем highest_bit_bs (бинарный цикл поиска), и это, в свою очередь, быстрее, чем highest_bit_shift (наивный сдвиг и счетная петля).
highest_bit_unrolled также быстрее, чем в принятом SO ответе (highest_bit_so) а также один дан в другом ответе (highest_bit_so2).
Тестирование циклически проходит по однобитовой маске, которая охватывает последовательные биты. Это делается для того, чтобы попытаться победить предсказание ветвлений в развернутом бинарном поиске, что является реалистичным: в реальной программе входные регистры вряд ли будут демонстрировать локальность позиции бита.
Вот результаты на старом Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20GHz:
$ ./highest-bit
highest_bit_unrolled = 6.090s
highest_bit_parallel = 9.260s
highest_bit_bs = 19.910s
highest_bit_shift = 21.130s
highest_bit_so = 8.230s
highest_bit_so2 = 6.960s
На более новой модели Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz:
highest_bit_unrolled = 1.555s
highest_bit_parallel = 3.420s
highest_bit_bs = 6.486s
highest_bit_shift = 9.505s
highest_bit_so = 4.127s
highest_bit_so2 = 1.645s
На более новом оборудовании highest_bit_so2 приближается к highest_bit_unrolled на более новом оборудовании. Порядок не совсем то же самое; сейчас highest_bit_so действительно отстает, и медленнее, чем highest_bit_parallel,
Самый быстрый, highest_bit_unrolled содержит наибольшее количество кода с наибольшим количеством ветвей. Каждое возвращаемое значение достигается различным набором условий со своим выделенным фрагментом кода.
Интуиция "избегать всех ветвей" (из-за опасений по поводу неправильных предсказаний ветвей) не всегда верна. Современные (и даже не очень современные) процессоры содержат значительные хитрости, чтобы не препятствовать ветвлению.
PS highest_bit_unrolled была введена на языке TXR в декабре 2011 года (с ошибками, так как отлажена).
Недавно я начал задумываться о том, не может ли какой-нибудь более приятный, более компактный код без веток работать быстрее.
Я несколько удивлен результатами.
Возможно, код действительно должен быть #ifdef-ing для GNU C и использование некоторых примитивов компилятора, но что касается переносимости, эта версия остается.
Нахождение логической базы 2 целого числа (64-битного или любого другого бита) с целочисленным выводом эквивалентно нахождению старшего значащего установленного бита. Зачем? Поскольку основание журнала 2 - это сколько раз вы можете разделить число на 2, чтобы достичь 1.
Один из способов найти установленный MSB - просто сдвигать бит вправо на 1 каждый раз, пока у вас не будет 0. Еще один более эффективный способ - выполнить какой-либо двоичный поиск с помощью битовых масок.
Часть ceil легко определяется путем проверки, установлены ли какие-либо другие биты, кроме MSB.
Я дам вам самый быстрый способ для x86-64 на момент написания и общую технику, если у вас есть быстрый пол, который работает для аргументов <2 ^ 63, если вы заботитесь о полном диапазоне, то смотрите ниже.
Я удивлен низким качеством других ответов, потому что они говорят вам, как получить пол, но преобразуют пол очень дорогим способом (используя условные обозначения и все!) В потолок.
Если вы можете получить пол логарифма быстро, например, с помощью __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 используются четыре инструкции по сравнению с тремя выше.
Наивный линейный поиск может быть опцией для равномерно распределенных целых чисел, поскольку в среднем требуется чуть менее 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 \
)
Если у вас есть 80-битные или 128-битные числа с плавающей запятой, приведите к этому типу, а затем считайте показательные биты. Эта ссылка содержит подробности (для целых чисел до 52 бит) и несколько других методов:
http://graphics.stanford.edu/~seander/bithacks.html
Также проверьте источник ffmpeg. Я знаю, что у них очень быстрый алгоритм. Даже если он не может быть напрямую расширен на большие размеры, вы можете легко сделать что-то вроде if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);
Я придумал что-то вроде двоичного поиска бита самого высокого порядка. Вероятно, аналогично другим опубликованным ответам. Производительность верхнего алгоритма почти такая же, как и у более простого алгоритма в последнем примере. Но в любом случае это хороший пример того, чего ожидать от подобных попыток «оптимизации»: ничего .
Хорошая ссылка на хаки побитовых операций, размещенная на stanford.edu: Bit Twiddling Hacks . В этом справочнике есть много примеров для многих вещей, включая несколько алгоритмов для вычисления значений log2. Это включает аналогичные - а может быть, и лучшие - подходы к этому.
У меня была идея, что своего рода двоичный поиск наиболее значимого бита будет быстрее, чем максимум 60+ циклов простого решения. Алгоритм сдвигает половину своего последнего значения сдвига на каждой итерации до нуля на старшем разряде.
Требуется 6 итераций для определения позиции самого значимого бита, который является нижним логарифмом2
// floor log2 in 6 max iterations for unsigned 64-bit values.
//
int floor_log2(unsigned long long n)
{
int shval = 32;
int msb = 0;
while (shval) {
if (n >> shval) {
msb += shval;
n >>= shval;
}
shval >>= 1;
}
return msb;
}
int ceil_log2(unsigned long long n)
{
return floor_log2(2 * n - 1);
}
Простой алгоритм - такой же быстрый, как и "оптимизированный" подход, описанный выше:
int floor_log2_simple(unsigned long long n)
{
int c = 0;
while (n) {
n >>= 1;
c++;
}
return c - 1;
}
Те же самые алгоритмы, реализованные в Rust, работают почти одинаково. Верхний подход показал себя немного лучше, но в среднем всего на пару наносекунд. Никакие изменения алгоритма не дали лучшей производительности.
мэ ...