Предыдущая сила 2

Question

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

Единственный способ, которым я пока что нахожу, - это сохранить стол со всей силой от двух до 2 ^ 64 и сделать простой поиск.

• Отрывки Ация
• Gamedev
• Битовые трюки
• Переполнение стека

Answer 1

От Восторг Хакера , приятное решение без ответвления :

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 инструкций. Вы можете сделать это за меньшее количество времени, если ваш ЦП имеет инструкцию «считать лидирующие нули».

Answer 2

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

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

Answer 3

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

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

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

Answer 4

Вот один вкладыш для потомков (рубин): ​​

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

Answer 5

Ниже код найдет предыдущую степень 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);

Answer 6

А как же

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 операций, и может быть быстрее заменить умножения на сдвиг.

Answer 7

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

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

Вот более читаемая версия на c #, с защитным предложением <= 0, распространяемым среди служебных методов. </p>

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

Answer 8

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

Answer 9

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

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

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

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

previousPower: = число shr 1

previousPower = число >> 1

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

Answer 10

Это мое текущее решение, чтобы найти следующую и предыдущую степени двух любого заданного положительного целого числа 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.