在C++中取反INT_MIN

Question

我要解决的问题是：

实现pow(x,n)，用于计算x的n次方（Leetcode问题50）

我有以下代码：

class Solution {
 public:
  double myPow(double x, int n) {
    if (n == 0) {
      cout << "in last";
      return 1;
    } else if (n < 0) {
      x = 1 / x;

      return myPow(x, -n);
    } else if (n % 2 == 0) {
      double y;
      cout << "in even";
      y = myPow(x, n / 2);
      cout << "y is ";
      cout << y;
      return (y * y);

    }

    else {
      cout << "in odd";
      double j = myPow(x, n - 1);
      cout << "j is ";
      cout << x * j;
      return (x * j);
    }
  }
};

当运行测试用例x=1.00000和n = -2147483648时，出现错误：

runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)

为什么我会遇到这个问题，如何解决？谢谢提前帮忙。

- hydra123

---

对于一个典型的二进制补码有符号整数类型，最小值的相反数无法在该类型的正数范围内表示。 - Shawn

Answer 1

如果您想支持-2147483648，则需要使用long long类型，而不是int。

如果int是32位2的补码类型，则2147483648实际上是long或long long类型。

在C++中不存在负文字（-2147483648是由字面值2147483648取反组成的编译时可求值常量表达式），因此-2147483648也是long或long long类型。这就是为什么您经常会看到INT_MIN被定义为-2147483647 - 1。

如果以上情况在您的平台上成立，则您的代码对该输入的行为是未定义的，因为您正在溢出int类型。

- Bathsheba

Answer 2

• 一个4字节(或32位)int的范围是-2,147,483,648到2,147,483,647，因此如果你对-2,147,483,648取反，就无法表示为int。
• 您可以尝试使用unsigned int(其范围为0到4,294,967,295)或long long int(其范围为-(2^63)到(2^63)-1)来进行这种否定并将正值放在那里。

我选择了另一种方法，单独处理这种情况，因为它是唯一会给我们带来麻烦的值。

• 在否定之前将该负值加1。
• 为了补偿这一点，我单独再次乘以基数。

if (n == -2,147,483,648)
{
    return (1.0/x) * myPow(1.0/x, -(n + 1));
}

完整解决方案

double myPow(double x, int n)
{
    if (n == 0) return 1.0;

    if (n < 0)
    {
        if (n == -2,147,483,648)
        {
            return (1.0/x) * myPow(1.0/x, -(n + 1));
        }

        return myPow(1.0/x, -n);
        }
        
    return (n % 2 == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
}

- Dalton Lima