Предыдущая мощность 2

Ответ 1

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

Эта реализация предназначена для Ruby.

class Integer

  def power_of_two?
    (self & (self - 1) == 0)
  end

  def next_power_of_two
    return 1 if self <= 0
    val = self
    val = val - 1
    val = (val >> 1) | val
    val = (val >> 2) | val
    val = (val >> 4) | val
    val = (val >> 8) | val
    val = (val >> 16) | val
    val = (val >> 32) | val if self.class == Bignum
    val = val + 1
  end

  def prev_power_of_two
   return 1 if self <= 0
   val = self
   val = val - 1
   val = (val >> 1) | val
   val = (val >> 2) | val
   val = (val >> 4) | val
   val = (val >> 8) | val
   val = (val >> 16) | val
   val = (val >> 32) | val if self.class == Bignum
   val = val - (val >> 1)
  end
end

Пример использования:

10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8

Для предыдущей степени из двух, поиск следующего и деления на два немного медленнее, чем метод выше.

Я не уверен, как это работает с Bignums.

Ответ 2

Из Hacker Delight, приятное безветровое решение:

uint32_t flp2 (uint32_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}

Обычно требуется 12 инструкций. Вы можете сделать это меньше, если ваш процессор имеет инструкцию "count leading zeroes".

Ответ 3

Вероятно, самый простой подход (для положительных чисел):

// find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;

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

Ответ 4

uint32_t previous_power_of_two( uint32_t x ) {
    if (x == 0) {
        return 0;
    }
    // x--; Uncomment this, if you want a strictly less than 'x' result.
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}

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

Ответ 5

Вот один лайнер для потомков (ruby):

2**Math.log(input, 2).floor(0)

Ответ 6

Если вы можете получить следующую мощность выше 2, следующая мощность ниже 2 равна либо следующей, либо более высокой. Это зависит от того, что вы считаете "следующим выше" для любой силы 2 (и того, что вы считаете следующей степенью ниже 2).

Ответ 7

Что насчет

if (tt = v >> 16)
{
   r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt];
}
else 
{
  r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v];
}

Это просто измененный метод из http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup. Для этого требуется как 7 операций, и, возможно, быстрее заменить умножения на сдвиг.

Ответ 8

Когда вы работаете в базе 2, вы можете перейти от двух до следующего, просто добавив или удалив цифру справа.

Например, предыдущей степенью двух из числа 8 является число 4. В двоичном формате:

01000 → 0100 (мы удаляем конечный ноль, чтобы получить номер 4)

Таким образом, алгоритм решения исчисления предыдущей степени двух равен:

previousPower: = number shr 1

previousPower = number → 1

(или любой другой синтаксис)

Ответ 9

Это можно сделать в одной строке.

int nextLowerPowerOf2 = i <= 0
                        ? 0
                        : ((i & (~i + 1)) == i)
                            ? i >> 1
                            : (1 << (int)Math.Log(i, 2));

результат

i    power_of_2
-2    0
-1    0
0    0
1    0
2    1
3    2
4    2
5    4
6    4
7    4
8    4
9    8

Здесь более читаемая версия в С#, где предложение <= 0 guard распространяется на методы утилиты.

int nextLowerPowerOf2 = IsPowerOfTwo(i) 
    ? i >> 1 // shift it right
    : GetPowerOfTwoLessThanOrEqualTo(i);

public static int GetPowerOfTwoLessThanOrEqualTo(int x)
{
    return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2)));
}

public static bool IsPowerOfTwo(int x)
{
    return (((x & (~x + 1)) == x) && (x > 0));
}

Ответ 10

Ниже код найдет предыдущую мощность 2:

int n = 100;
    n /= 2;//commenting this will gives the next power of 2
    n |= n>>1;
    n |= n>>2;
    n |= n>>4;
    n |= n>>16;

System.out.println(n+1);

Ответ 11

Попробуйте следующее: ~((x + ~x)>>1) Это короткий и очень простой.