C++中的二进制求幂

Question

可以在下面找到我的二进制求幂实现

#include<iostream>
#include<cmath>
using namespace std;

int fast_exponentiation(int base, int pow) {
    unsigned int result; // variable to store intermediaries

    if (pow == 1) {
        return base;
    }
    else if (pow == 0) {
        return 1;
    }

    result = fast_exponentiation(base, floor(pow/2));

    // even power
    if (pow % 2 == 0) {
        return result * result; 
    }
    // odd power
    else {
        return result * base * result;
    }
}

int main() {
    int num, answer, p;
    cout <<  "Enter the base: ";
    cin >> num;

    cout << "Enter power: "; 
    cin >> p;

    answer = fast_exponentiation(num, p);
    cout << answer <<  endl;

    return 0;
}

问题是，当我对输入num= 3和pow = 20运行这个函数时，我得到了-808182895，一个负数。我似乎找不出代码出了什么问题？我能得到一些帮助吗？

Answer 1

3^20的值超过了最大可能的int值2^31，因此出现溢出。克服这一限制的最简单方法是使用long long数据类型为计算提供最高39次方(接近2^63)的可能性。

对于较大的功率，需要较长的数字运算- boost多精度，GMP等