Вычислите быструю основу журнала 2 потолка
Что быстрый путь состоит в том, чтобы вычислить (long int) ceiling(log_2(i)), где ввод и вывод является 64-разрядными целыми числами? Решения для целых чисел со знаком или целых чисел без знака приемлемы. Я подозреваю, что лучшим способом будет метод битового жонглирования, подобный найденным здесь, а скорее, чем попытка мое собственное я хотел бы использовать что-то, что уже хорошо тестируется. Общее решение будет работать на все положительные значения.
Например, значения для 2,3,4,5,6,7,8 1,2,2,3,3,3,3
Править: До сих пор оптимальный маршрут, кажется, чтобы вычислить основу журнала целого числа/пола 2 (положение MSB) использующий любое количество быстрого существующего bithacks или методов регистра, и затем добавить тот, если вход не является питанием два. Быстрая поразрядная проверка на полномочия два (n&(n-1)).
Редактирование 2: хороший источник на целочисленных логарифмах и продвижении обнуляет методы, Разделы 5-3 и 11-4 в Восхищении Хакера Henry S. Warren. Это - самая полная обработка, которую я нашел.
Редактирование 3: Эта техника выглядит многообещающей: https://stackoverflow.com/a/51351885/365478
6 ответов
Если вы компилируете для 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 с 1 или 2 вызовами _BitScanReverse. Проверьте верхние 32 бита x, ((long *) & x) [1], затем нижние 32 бита, если необходимо, ((long *) & x) [0].
Нахождение логарифмического основания 2 целого числа (64-битного или любого другого) с целочисленным выводом эквивалентно нахождению старшего установленного бита. Почему? Потому что log base 2 - это то, сколько раз можно разделить число на 2, чтобы получить 1.
Один из способов найти младший старший бит, который установлен, - это просто сдвигать биты вправо на 1 каждый раз, пока не получится 0. Другой, более эффективный способ - это двоичный поиск с помощью битмасок.
Часть ceil легко решается проверкой, установлены ли другие биты, кроме MSB.
истинное самое быстрое решение:
двоичное дерево поиска из 63 записей. Это степени двойки от 0 до 63. Функция одноразовой генерации для создания дерева. Листы представляют собой логарифмическую основу 2 степеней (в основном, числа 1-63).
Чтобы найти ответ, вы вводите число в дерево и переходите к листу, большему, чем элемент. Если конечный узел точно равен, результатом будет конечное значение. В противном случае результатом будет листовое значение +1.
Сложность зафиксирована на O (6).
Если у вас есть 80-битные или 128-битные числа с плавающей запятой, приведите к этому типу и затем считайте биты экспоненты. Эта ссылка содержит подробную информацию (для целых чисел до 52 бит) и несколько других методов:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float
Также проверьте исходный код ffmpeg. Я знаю, что у них очень быстрый алгоритм. Даже если он не расширяется напрямую до больших размеров, вы можете легко сделать что-то вроде if (x> INT32_MAX) return fastlog2 (x >> 32) +32; иначе return fastlog2 (x);
Если вы можете ограничиться gcc, есть набор встроенных функций, которые возвращают количество ведущих нулевых битов и могут быть использованы для того, чтобы сделать то, что вы хотите с небольшой работой:
int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
#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;
}