Округление до следующей степени 2

Question

Я хочу написать функцию, которая возвращает ближайшую следующую степень 2 числа. Например, если мой ввод 789, вывод должен быть 1024. Есть ли способ достичь этого без использования циклов, а только с использованием некоторых побитовых операторов?

Answer 1

Проверьте Бит Twiddling Hacks . Вам нужно получить основание 2 логарифм, а затем добавить 1 к этому. Пример для 32-битного значения:

Округление до следующей наивысшей степени 2

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

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

Answer 2

next = pow(2, ceil(log(x)/log(2)));

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

Это более универсальный (то есть более медленный!) Метод, чем побитовые методы, связанные в других местах, но полезно знать математику, а?

Answer 3

unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}

Answer 4

Я думаю, что это тоже работает:

int power = 1;
while(power < x)
    power*=2;

И ответ power.

Answer 5

Если вы используете GCC, вы можете взглянуть на Оптимизация функции next_pow2 () от Lockless Inc .. На этой странице описан способ использования встроенной функции builtin_clz() ( считать начальный ноль), а затем использовать непосредственно команду ассемблера x86 (ia32) bsr (обратное сканирование битов), как это описано в другом ответе ссылка на сайт gamedev . Этот код может быть быстрее, чем те, которые описаны в предыдущий ответ .

Кстати, если вы не собираетесь использовать инструкцию на ассемблере и 64-битный тип данных, вы можете использовать это

/**
 * return the smallest power of two value
 * greater than x
 *
 * Input range:  [2..2147483648]
 * Output range: [2..2147483648]
 *
 */
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 1);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif

    return 1 << (32 - __builtin_clz (x - 1));
}

Answer 6

Еще один, хотя я использую цикл, но это намного быстрее, чем математические операнды

мощность двух «напольных» опций:

int power = 1;
while (x >>= 1) power <<= 1;

мощность двух «потолочных» опций:

int power = 2;
x--;    // <<-- UPDATED
while (x >>= 1) power <<= 1;

---

UPDATE

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

Вот полные функции:

unsigned power_floor(unsigned x) {
    int power = 1;
    while (x >>= 1) power <<= 1;
    return power;
}

unsigned power_ceil(unsigned x) {
    if (x <= 1) return 1;
    int power = 2;
    x--;
    while (x >>= 1) power <<= 1;
    return power;
}

Answer 7

Для любого неподписанного типа, основанного на бит-хедлингах:

#include <climits>
#include <type_traits>

template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
  static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
  v--;
  for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
  {
    v |= v >> i;
  }
  return ++v;
}

Там действительно нет цикла, так как компилятор знает во время компиляции количество итераций.

Answer 8

Для поплавков IEEE вы могли бы сделать что-то подобное.

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

Если вам нужно целочисленное решение и вы можете использовать встроенную сборку, BSR выдаст вам log2 целого числа на x86. Он подсчитывает, сколько правильных битов установлено, что в точности равно log2 этого числа. Другие процессоры имеют аналогичные инструкции (часто), такие как CLZ, и, в зависимости от вашего компилятора, может быть встроенная функция, которая сделает всю работу за вас.

Answer 9

Для полноты здесь приведена реализация с плавающей запятой в стандартном болоте C.

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}

Answer 10

/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000)         ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00)             ? (8  +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0)               ? (4  +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc)                ? (2  +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2)                ? (1)                  : (0))

#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8  __LOG2D

static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
    return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
    i =i -1;
    i =LOG2_UINT64(i);
    return 1UL <<(1 +i);
#endif
}

Если вы не хотите рисковать в сфере неопределенного поведения, входное значение должно быть между 1 и 2 ^ 63. Макрос также полезен для установки константы во время компиляции.