在C++中将整数提升为正整数幂的正确方法是什么？

Question

我们知道由于各种原因,C++中没有标准的整数幂函数.我用相当小的整数执行精确算术,计算能力的正确方法是什么？

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

Answer 2

你可以用std::pow(double a, double b).如果两者都没有不准确a,b并且结果适合32位整数!

原因是64位双精度完全覆盖了32位整数的范围.