Как найти ближайшее значение 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.

в то время как x

затем просто верните 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

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

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

Answer 8

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

Answer 9

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