Каков правильный способ поднять целое число до положительной целочисленной мощности в С++?

Ответ 1

В стандартном быстром экспонировании используется повторное возведение в квадрат:

uint_t power(uint_t base, uint_t exponent)
{
    uint_t result = 1;

    for (uint_t term = base; exponent != 0; term = term * term)
    {
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
    }

    return result;
}

Количество шагов логарифмическое в значении exponent. Этот алгоритм может быть тривиально расширен до модульного возведения в степень.

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

uint_t power_modified(uint_t base, uint_t exponent)
{
    if (exponent == 0) { return 1;    }
    if (base < 2)      { return base; }

    uint_t result = 1;

    for (uint_t term = base; ; term = term * term)
    { 
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
        if (exponent == 0)     { break; }
    }

    return result;
}

Ответ 2

Вы можете использовать std::pow(double a, double b). Не будет никаких неточностей, если оба a, b и результат поместится в 32-битное целое!

Причина в том, что 64-битная двойная точность полностью охватывает диапазон 32-разрядных целых чисел.

Ответ 3

В то время как ответ Kerrek верен, в g++ есть также "секретная" функция, чтобы сделать это эффективно. Если вы посмотрите на функцию мощности SGI, ее можно легко адаптировать для выполнения того, что вы хотите:

http://www.sgi.com/tech/stl/power.html

В g++ это реализовано как __ gnu_cxx:: power. Вы, вероятно, не должны использовать эти вещи в производственном коде, хотя...

Ответ 4

В дополнение к другим ответам здесь есть также хорошая статья о Википедии, объясняющая различные различные реализации здесь → LINK