Алгоритм для нахождения наименьшей степени, равной 2, большей или равной заданному значению

Ответ 1

Здесь мой любимый. Помимо первоначальной проверки того, является ли она недействительной (< 0, которую вы могли бы пропустить, если бы вы знали, что у вас есть только число = = 0), она не имеет циклов или условных выражений и, таким образом, будет превосходить большинство других методов. Это похоже на ответ erickson, но я думаю, что мой декрементинг x в начале и добавление 1 в конце немного менее неудобный, чем его ответ (а также избегает условного в конце).

/// Round up to next higher power of 2 (return x if it already a power
/// of 2).
inline int
pow2roundup (int x)
{
    if (x < 0)
        return 0;
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x+1;
}

Ответ 2

ceil(log2(value))

ilog2() может быть рассчитан в трех инструкциях asm, например http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html

Ответ 3

В духе Quake II 0x5f3759df и версии IEEE для бит Twiddling Hacks это решение достигает удвоения, чтобы извлечь экспоненту в качестве средства вычисления уровня пола (lg2 ​​(n)). Это немного быстрее, чем принятое решение и намного быстрее, чем версия Bit Twiddling IEEE, поскольку она позволяет избежать математики с плавающей запятой. Как указано в кодировке, предполагается, что double является реальным поплавком * 8 IEEE на маленькой конечной машине.

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d = n-1; 
    return 1 << ((((int*)&d)[1]>>20)-1022); 
} 

Изменить: добавить оптимизированную версию сборки x86 с помощью сотрудника. 4% -ное увеличение скорости, но все же примерно на 50% медленнее, чем версия bsr (6 секунд против 4 на моем ноутбуке для n = 1..2 ^ 31-2).

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d;
    n--;
    __asm {
      fild    n 
      mov     eax,4
      fstp    d 
      mov     ecx, dword ptr d[eax]
      sar     ecx,14h 
      rol     eax,cl 
  }
} 

Ответ 4

На оборудовании Intel инструкция BSR близка к тому, что вы хотите - она ​​находит бит наиболее значимого набора. Если вам нужно быть более точным, вы можете задаться вопросом, являются ли оставшиеся бит точно нулевыми или нет. Я склонен предположить, что у другого процессора будет что-то вроде BSR - это вопрос, на который вы хотите ответить, чтобы нормализовать число. Если ваш номер больше 32 бит, вы можете выполнить сканирование с самого важного DWORD, чтобы найти первый бит DWORD с ANY битами. Edsger Dijkstra, скорее всего, замечает, что вышеупомянутые "алгоритмы" предполагают, что ваш компьютер использует двоичные разряды, в то время как из своего рода "алгоритмической" перспективы вы должны думать о машинах Тьюринга или что-то в этом роде, очевидно, я более прагматичный.

Ответ 5

Ваша реализация не наивна, она на самом деле логическая, за исключением того, что она неправильна - она ​​возвращает отрицание для чисел, большее, чем 1/2 максимального целочисленного размера.

Предполагая, что вы можете ограничить числа диапазоном от 0 до 2 ^ 30 (для 32-битных ints), он будет работать очень хорошо и намного быстрее, чем любые математические функции, связанные с логарифмами.

Unsigned ints будет работать лучше, но вы закончите бесконечный цикл (для чисел больше 2 ^ 31), так как вы никогда не сможете достичь 2 ^ 32 с < Оператор.

Ответ 6

Изучение возможных решений тесно связанной проблемы (то есть округление вниз, а не вверх), многие из которых значительно быстрее, чем наивный подход, доступно на "Бит Tweedling Hacks" , страница, отличный ресурс для тех видов оптимизации, которые вы ищете. Самое быстрое решение - использовать таблицу поиска с 256 записями, что уменьшает общее количество операций до 7, начиная с среднего значения 62 (по аналогичной методологии подсчета операций) для наивного подхода. Адаптация этих решений к вашей проблеме заключается в одном сравнении и приращении.

Ответ 7

Здесь находится шаблонная версия метода смещения бит.

template<typename T> T next_power2(T value)
{
    --value;
    for(size_t i = 1; i < sizeof(T) * CHAR_BIT; i*=2)
        value |= value >> i;
    return value+1;
}

Поскольку цикл использует только константы, он сглаживается компилятором. (Я проверил) Функция также является будущим доказательством.

Здесь используется тот, который использует __builtin_clz. (Также будущее доказательство)

template<typename T> T next_power2(T value)
{
    return 1 << ((sizeof(T) * CHAR_BIT) - __builtin_clz(value-1));
}

Ответ 8

pow (2, ceil (log2 (значение));

log2 (значение) = журнал (значение)/log (2);

Ответ 9

Как насчет рекурсивной версии шаблона для генерации константы компиляции:

template<uint32_t A, uint8_t B = 16>
struct Pow2RoundDown { enum{ value = Pow2RoundDown<(A | (A >> B)), B/2>::value }; };
template<uint32_t A>
struct Pow2RoundDown<A, 1> { enum{ value = (A | (A >> 1)) - ((A | (A >> 1)) >> 1) }; };

template<uint32_t A, uint8_t B = 16>
struct Pow2RoundUp { enum{ value = Pow2RoundUp<((B == 16 ? (A-1) : A) | ((B == 16 ? (A-1) : A) >> B)), B/2>::value }; };
template<uint32_t A >
struct Pow2RoundUp<A, 1> { enum{ value = ((A | (A >> 1)) + 1) }; };

Можно использовать так:

Pow2RoundDown<3221>::value, Pow2RoundUp<3221>::value

Ответ 10

Вы действительно не говорите, что вы подразумеваете под "лучшим алгоритмом", но поскольку тот, который вы представляете, совершенно ясен (если несколько испорчен), я предполагаю, что вы после более эффективного алгоритма.

Ларри Гритц дал, пожалуй, самый эффективный алгоритм c/С++ без накладных расходов таблицы поиска, и этого было бы достаточно в большинстве случаев (см. http://www.hackersdelight.org для аналогичных алгоритмов).

Как упоминалось ранее, большинство процессоров в наши дни имеют машинные инструкции для подсчета количества ведущих нулей (или эквивалентно возврата порога ms), однако их использование не переносится и - в большинстве случаев - не стоит усилий.

Однако большинство компиляторов имеют "внутренние" функции, которые позволяют использовать машинные инструкции, но более переносимым образом.

Microsoft С++ имеет _BitScanReverse(), а gcc обеспечивает __builtin_clz(), чтобы эффективно выполнять основную часть работы.

Ответ 11

Приведенный ниже код повторно разбивает младший бит до тех пор, пока номер не станет равным двум, а затем удвоит результат, если только число не будет состоять из двух. Преимущество состоит в том, что он работает в течение времени, пропорционального количеству установленных битов. К сожалению, у него есть недостаток, требующий больше инструкций почти во всех случаях, чем код в вопросе или предложения сборки. Я включаю его только для полноты.

int nextPow(int x) {
  int y = x
  while (x &= (x^(~x+1))) 
    y = x << 1;
  return y
}

Ответ 12

Я знаю, что это приманка с downvote, но если число достаточно мало (например, 8 или 16 бит), прямой поиск может быть самым быстрым.

// fill in the table
unsigned short tab[65536];
unsigned short bit = tab[i];

Возможно, его можно будет увеличить до 32 бит, сначала сделав высокое слово, а затем низкое.

//
unsigned long bitHigh = ((unsigned long)tab[(unsigned short)(i >> 16)]) << 16;
unsigned long bitLow = 0;
if (bitHigh == 0){
    bitLow = tab[(unsigned short)(i & 0xffff)];
}
unsigned long answer = bitHigh | bitLow;

Вероятно, не лучше, чем сдвиг или методы, но, возможно, может быть расширен до больших размеров слов.

(На самом деле это дает самый высокий 1-бит. Вам придется сдвинуть его налево, чтобы получить следующую более высокую мощность 2.)

Ответ 13

Моя версия:

int pwr2Test(size_t x) {
    return (x & (x - 1))? 0 : 1; 
}

size_t pwr2Floor(size_t x) {
    // A lookup table for rounding up 4 bit numbers to
    // the nearest power of 2.
    static const unsigned char pwr2lut[] = {
        0x00, 0x01, 0x02, 0x02,     //  0,  1,  2,  3
        0x04, 0x04, 0x04, 0x04,     //  4,  5,  6,  7
        0x08, 0x08, 0x08, 0x08,     //  8,  9, 10, 11
        0x08, 0x08, 0x08, 0x08      // 12, 13, 14, 15
    };

    size_t pwr2 = 0;                // The return value
    unsigned int i = 0;             // The nybble interator

    for( i = 0; x != 0; ++i ) {     // Iterate through nybbles
        pwr2 = pwr2lut[x & 0x0f];   // rounding up to powers of 2.
        x >>= 4;                    // (i - 1) will contain the
    }                               // highest non-zero nybble index.

    i = i? (i - 1) : i;
    pwr2 <<= (i * 4);
    return pwr2; 
}

size_t pwr2Size(size_t x) {
    if( pwr2Test(x) ) { return x; }
    return pwr2Floor(x) * 2; 
 }

Ответ 14

Мне нравится смена.

Я соглашусь на

    int bufferPow = 1;
    while ( bufferPow<bufferSize && bufferPow>0) bufferPow <<= 1;

таким образом цикл всегда завершается, а часть после && оценивается почти никогда. И я не думаю, что две строки стоят вызова функции. Также вы можете сделать длинный или короткий, в зависимости от вашего суждения, и это очень читаемо. (если bufferPow становится отрицательным, надеюсь, ваш основной код быстро выйдет.)

Обычно вы вычисляете 2-мощь только один раз в начале алгоритма, поэтому оптимизация в любом случае будет глупой. Однако было бы интересно, если бы кто-то достаточно скучал, он бы позаботился о конкурсе скорости... используя приведенные выше примеры и 255 256 257.. 4195 4196 4197

Ответ 15

Любая функция журнала может быть преобразована в базу блогов 2 путем деления на журнал 2:

$ /usr/local/pypy-1.9/bin/pypy
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48)
[PyPy 1.9.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``<arigato> yes but there is not
much sense if I explain all about today greatest idea if tomorrow it's
completely outdated''
>>>> import math
>>>> print math.log(65535)/math.log(2)
15.9999779861
>>>> print math.log(65536)/math.log(2)
16.0
>>>>

Это, конечно, не будет на 100% точным, так как имеется арифметика с плавающей запятой.

Ответ 16

Это работает и очень быстро (на моем 64-разрядном процессоре Intel Core 2 Duo с частотой 2,66 ГГц).

#include <iostream>
int main(void) {
    int testinput,counter;
    std::cin >> testinput;
    while (testinput > 1) {
        testinput = testinput >> 1;
        counter++;
    }
    int finalnum = testinput << counter+1;
    printf("Is %i\n",finalnum);
    return 0;
}

Я тестировал его на 3, 6 и 65496, и были даны правильные ответы (4, 8 и 65536).

Извините, если это кажется немного тайным, я был под влиянием пары часов Doom перед тем, как писать.:)