Как рассчитать ближайшую степень 2 или 10, из которой состоит число?

Question

Какой самый эффективный способ вычислить ближайшую степень от 2 или 10 до другого числа? например,

3,5 вернет 4 для мощности 2 и 1 для мощности 10

123 вернет 128 для мощности 2 и 100 для мощности 10

0,24 вернет 0,25 для мощности 2 и 0,1 для мощности 10

Я просто ищу алгоритм и не обращаю внимания на язык.

Answer 1

n^round(log_n(x))

где log_n - логарифм по основанию n. Возможно, вам придется изменить round () в зависимости от того, как вы определяете «ближайший».

Обратите внимание, что log_n(x) может быть реализовано как:

log_n(x) = log(x) / log(n)

где log - логарифм для любой удобной базы.

Answer 2

Для степени 2 на целых числах есть умный трюк, который состоит в том, чтобы копировать последний бит снова и снова вправо. Тогда вам нужно только увеличить свой номер, и ваша сила равна 2.

int NextPowerOf2(int n)
{
   n |= (n >> 16);
   n |= (n >> 8);
   n |= (n >> 4);
   n |= (n >> 2);
   n |= (n >> 1);
   ++n;
   return n;
}

Answer 3

Для степеней 2 и> = 1 вы можете видеть, сколько раз вы можете сдвигать бит вправо. За каждый раз это 1 дополнительная сила из 2, которую вы забираете. Как только вы опуститесь до 0, у вас будет свой номер.

Answer 4

Возможно, вам придется изменить round () в зависимости от того, как вы определяете «ближайший».

@ Ответ Грега Хьюгилла верен, за исключением того, что он слишком рано округляется для приведенных вами примеров. Например, 10 ^ round (log_10 (3.5)) == 10, а не 1. Я предполагаю, что он имеет в виду «как вы определяете« ближайший »».

Вероятно, самый простой способ использовать формулу Грега, и если она слишком высока (или слишком мала для x <1), используйте следующую меньшую степень, равную двум: </p>

closest = n ^ round(log_n(x))

if (closest > x) {
    other = closest / n
} else {
    other = closest * n
}

if (abs(other - x) < abs(closest - x)) {
    return other
} else {
    return closest
}

Answer 5

Я думаю, что мог бы подойти к проблеме, но используя базу журнала 2 и базу журнала 10.

log10 из (123) - это 2. что-то. взять слово затем поднимите 10 до этой силы, и это должно приблизить вас.

То же самое должно работать с базой журналов 2.

log2 из (9) - 3. что-то взять слово затем поднимитесь до этой силы

Вы можете играть с округлением журнала.