c++ - 我执行幂函数有什么问题？

Question

我在 leetcode 中为一个简单的问题写了一段代码。它要求执行 pow(x,n)；它告诉我“运行时错误”，最后执行的输入:1.00000，-2147483648。我换了另一种方法，行得通。但我只想知道我在下面的代码中做错了什么。非常感谢!!

class Solution {
public:
    double pow(double x, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(n==0 && x==0) return 1.0;
        if(x==0) return 0;
        if(n==0) return 1.0;
        if(n<0) return 1/pow(x,-n);
        if(n==1) return x;

        double y=pow(x,n/2);
        if(n%2==1) return y*y*x;
        else return y*y;

}

};

Answer 1

假设int长度为 32 位，-2147483648是除 0 之外的唯一值，其中它的否定等于自身。所以行:

if(n<0) return 1/pow(x,-n);

使用相同的参数调用自身，并一直这样做直到出现堆栈溢出。

更详细地说，-2147483648 的二进制表示是:

10000000000000000000000000000000

那是 1其次是 31 0秒。根据two's complement取反是一个两步过程。 1)全部改0 s 至 1反之亦然:

01111111111111111111111111111111

然后 2) 添加 1:

10000000000000000000000000000000

所以我们得到相同的值。因此无限递归。

如果您必须处理这种情况，这里有一个想法。将其插入到 n<0 之前测试:

if (n==-2147483648) return 1/(x*pow(x,2147483647));

显然这是针对这个案例的黑客攻击。最终，您的问题域将决定最优雅/最通用的解决方案。