实施pow(x,n)

Question

当我尝试这个时,为什么这个功能给出了错误的答案-1而不是正确的答案1？myPow(-1.00000, -2147483648)

double QuickPower(double x, int n) 
{
    if(n==0){
        return 1;
    }

    if(n==1){
        return x;
    }

    if(n>=2){
        int res=n%2;
        double half=QuickPower(x,n/2);
        return res? Half*half*x: half*half;
    }
}

double myPow(double x, int n) {
    return n>=0? QuickPower(x,n):(1/QuickPower(x,-n));
}

我只是尝试运行下面的代码.打印出"Hello World".这里我没有指定数据类型,但它仍然传递if语句.为什么？
if (-1 > 2147483648) { cout << "Hello World"; }

Answer 1

该错误是整数溢出的结果.

myPow当n为负时,你在内部否定n.

否定-2147483648给出2147483648,这比最大正有符号32位整数值多1,即2147483647.使用更大的整数数据类型来修复错误.

Answer 2

您的问题是由于计算 -n 时整数溢出造成的。在你的系统（和我的本地系统）上INT_MIN=-2147483648 和INT_MAX=2147483647。

所以问题是-(INT_MIN)不能用整数表示。但是，您可以避免此问题，而无需使用更高精度的整数类型：

自从

x ⁿ = x ⁿ⁺¹ / x = (1/x) / x ^-(n+1)

我们可以重写myPow为

double myPow(double x, int n) {
    return n>=0? QuickPower(x,n):(1/x)/QuickPower(x,-(n+1));
}

这个功能是可以的，因为-(INT_MIN+1)=INT_MAX。

值得注意的是，这将myPow(0,-k)返回 +/- Infinity (n=-1) 或 NaN (n<-1)。如果您需要该情况保持一致，那么需要做更多的工作。一般来说，对于 pow 来说，处理无限 / nan 值是很棘手的（在这个或原始实现中不是“正确的”）——值得C pow 函数的手册页来获取所有边缘情况。