Как найти ближайшее значение 2 ^ N для данного входа?

Question

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

Answer 1

1. Найти логарифм по основанию 2 по заданному числу => x: = log (2, вход)
2. Округлить значение, полученное на шаге 1, как вверх, так и вниз => y: = round (x), z: = round (x) + 1
3. Найдите 2 ^ y, 2 ^ z, сравните их оба с входными данными и выберите тот, который подходит лучше

Answer 2

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

Если вы установите все биты ниже самого высокого установленного бита на 1, то добавьте один, и в результате вы получите следующую большую степень двух. Вы можете сдвинуть вправо, чтобы получить следующую более низкую степень двух и выбрать более близкую из двух.

unsigned closest_power_of_two(unsigned value)
{
    unsigned above = (value - 1); // handle case where input is a power of two
    above |= above >> 1;          // set all of the bits below the highest bit
    above |= above >> 2;
    above |= above >> 4;
    above |= above >> 8;
    above |= above >> 16;
    ++above;                      // add one, carrying all the way through
                                  // leaving only one bit set.

    unsigned below = above >> 1;  // find the next lower power of two.

    return (above - value) < (value - below) ? above : below;
}

См. Bit Twiddling Hacks для других подобных трюков.

Answer 3

Помимо цикла, есть еще одно решение, которое может быть быстрее в зависимости от того, как компилятор отображает инструкцию nlz:

public int nextPowerOfTwo(int val) {
   return 1 << (32 - Integer.numberOfLeadingZeros(val - 1)); 
}

Нет явного цикла и, безусловно, более эффективно, чем в решениях, использующих Math.pow.Трудно сказать больше, не смотря, какой код генерирует компилятор для numberOfLeadingZeros.

С этим мы можем легко получить меньшую степень 2 и затем сравнить, какая из них ближе - последняя часть должна быть сделана для каждого решения, которое мне кажется.

Answer 4

установить х в 1.

пока х <цель, установите х = 2 * х </p>

, затем просто верните x или x / 2, в зависимости от того, что ближе к цели.

Answer 5

Вот побитовое решение - оно вернет арендодателю 2 ^ N и 2 ^ (N + 1) в случае ничьей.Это должно быть очень быстро по сравнению с вызовом функции log ()

let mask = (~0 >> 1) + 1

while ( mask > value )
    mask >> 1

return ( mask & value == 0 ) ? mask : mask << 1 

Answer 6

Вот псевдокод для функции, которая принимает введенный номер и возвращает ваш ответ.

int findit( int x) {
  int a = int(log(x)/log(2));
  if(x >= 2^a + 2^(a-1))
    return 2^(a+1)
  else
    return 2^a
}

Answer 7

public static int neareastPower2(int in) {
    return (int) Math.pow(2, Math.round(Math.log(in) / Math.log(2)));
}

Answer 8

Я буду использовать 5 в качестве ввода для простого примера вместо 50.

• Преобразование ввода в биты / байты, в данном случае 101
• Поскольку вы ищете степени двойки, ваш ответ будет иметь форму 10000 ... 00 (один с определенным количеством нулей). Вы берете входное значение (3 бита) и вычисляете целочисленное значение 100 (3 бита) и 1000 (4 бита). Целое число 100 будет меньше входного значения, целое число 1000 будет больше.
• Вы рассчитываете разницу между входным значением и двумя возможными значениями и используете наименьшее. В этом случае 100 = 4 (разница 1), а 1000 = 8 (разница 3), поэтому искомый ответ 4

Answer 9

public static int neareastPower2(int in) {
    if (in <= 1) {
        return 1;
    }
    int result = 2;

    while (in > 3) {
        in = in >> 1;
        result = result << 1;
    }

    if (in == 3) {
        return result << 1;
    } else {
        return result;
    }
}