Алгоритм для нахождения самого маленького питания два это больше или равно данному значению [дубликат]

Моя версия того же:

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; 
 }

Я знаю, что это - 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;

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

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

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

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

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

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

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

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

Microsoft C ++ имеет _BitScanReverse (), и gcc обеспечивает __ builtin_clz (), чтобы сделать объем работы эффективно.

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

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

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

В духе 0x5f3759df II's Quake и версии IEEE Взломов Битового жонглирования - это решение достигает двойного для извлечения экспоненты как средства вычислить пол (lg2 (n)). Это немного быстрее, чем принятое решение и намного быстрее, чем версия IEEE Битового жонглирования, так как это избегает математических операций с плавающей точкой. Как кодировано, это предполагает, что двойным является real*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 
  }
} 

На аппаратных средствах Intel инструкция BSR близко к тому, что Вы хотите - это находит most-significant-set-bit. Если необходимо быть более точными, можно тогда задаться вопросом, являются ли остающиеся биты точно нулем или нет. Я склонен предполагать, что другой ЦП будет иметь что-то как BSR - это - вопрос, который Вы хотите, ответил для нормализации числа. Если бы Ваше число составляет больше чем 32 бита тогда, Вы сделали бы сканирование от своего most-significant-DWORD для нахождения первого DWORD с ЛЮБОЙ набор битов. Edsger Dijkstra, вероятно, отметил бы, что вышеупомянутые "алгоритмы" предполагают, что Ваш компьютер использует Двоичные единицы информации, в то время как от его вида высокой "алгоритмической" перспективы необходимо думать о Машинах Тьюринга или чем-то - очевидно, я имею более прагматический стиль.

ceil(log2(value))

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

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