LeetCode Pow(x,n)迭代解法：右移运算符致超时，普通除法正常

我在用迭代法实现LeetCode的Pow(x,n)问题时，遇到了一个奇怪的问题：用右移运算符>>更新循环变量时代码超时（TLE），但换成普通除法/=后就能正常运行。

超时的代码 #

double poww(double x, int n)
{
    if (n == 0)
        return 1;
    double ans = 1;
    double temp = x;
    while (n)
    {
        if (n & 1)
        {
            ans *= temp;
        }
        temp *= temp;
        n = (n >> 1);
    }
    return ans;
}
double myPow(double x, int n)
{
    if (n == 0)
        return 1.0;
    if (n < 0)
        return 1 / poww(x, abs(n));
    return poww(x, n);
}

正常运行的代码 #

double poww(double x, int n)
{
    if (n == 0)
        return 1;
    double ans = 1;
    double temp = x;
    while (n)
    {
        if (n & 1)
        {
            ans *= temp;
        }
        temp *= temp;
        n /= 2;
    }
    return ans;
}
double myPow(double x, int n)
{
    if (n == 0)
        return 1.0;
    if (n < 0)
        return 1 / poww(x, abs(n));
    return poww(x, n);
}

问题原因 #

核心问题出在有符号整数的溢出与算术右移特性：

• 当输入的n是INT_MIN（即-2^31，int类型的最小值）时，abs(n)会因为int类型的范围限制发生溢出，结果仍然是INT_MIN（负数）。
• 此时poww函数接收的n是负数：
  • 使用n = n >> 1时，C/C++中对有符号整数执行的是算术右移——右移时会保留符号位（高位补1），因此n会一直是负数，永远不会变为0，导致循环无限执行，最终超时。
  • 使用n /= 2时，整数除法会逐步将n向0逼近，即使n是INT_MIN，经过多次除法后最终会变为0，循环能正常结束。

解决思路 #

要避免这个问题，可以：

• 将poww函数的参数n改为unsigned int类型，这样右移会变成逻辑右移，不会保留符号位。
• 先将n转换为long long类型，避免abs(n)时的溢出问题，比如：

  double myPow(double x, int n)
  {
      long long N = n;
      if (N < 0) {
          x = 1 / x;
          N = -N;
      }
      return poww(x, N);
  }
  

内容的提问来源于stack exchange，提问作者Hemang Kinra