如何编写一个计算功率的循环？

Question

我正在尝试编写一个无需使用pow（）函数即可计算功率的循环。我坚持如何做到这一点。进行base *= base运算甚至可以放大到4的幂，因此有些东西似乎很奇怪，我似乎无法弄清楚。

int Fast_Power(int base, int exp){
    int i = 2;
    int result;

    if(exp == 0){
        result = 1;
        }
    if(exp == 1){
        result = base;
        }
    else{
        for(i = 2; i < exp; i++){
            base *= base; 
            result = base;
        }
    }
    return result;
}

Answer 1

您正在寻找的基本但天真的算法非常容易受到整数溢出的影响：

int Fast_Power (int base, int exp)
{
    int result = base;

    if (exp == 0)
        return 1;

    for (int i = 1; i < exp; i++) {
        result *= base;
    }

    return result;
}

注意： result很容易溢出。您需要进行一些基本检查，以防止integer-overflow和Undefined Behavior。

最小支票（请参阅：Catch and compute overflow during multiplication of two large integers），可以如下合并。您必须在此处使用更广泛的类型进行临时计算：

int Fast_Power (int base, int exp)
{
    int result = base;

    if (exp == 0)
        return 1;

    for (int i = 1; i < exp; i++) {
        long long int tmp = result * base;      /* tmp of wider type */
        if (result && tmp / result != base) {   /* check for overflow */
            fputs ("error: overflow occurred.\n", stderr);
            return 0;
        }
        result = tmp;
    }

    return result;
}

[现在，如果您尝试Fast_Power (2, 31);生成错误并返回零。

Answer 2

您做错的是每次循环都base *= base，每次迭代都会更改基数本身。

相反，您希望基数保持不变，并将最终结果乘以原始基数“ exp”倍。

int Fast_Power(int base, int exp){
    int result=1;

    if(exp == 0){
        result = 1;
    }
    if(exp == 1){
        result = base;
    }
    else{
        for(int i = 0; i < exp; i++){
            result *= base;
        }
    }
    return result;
}