Ex16 数值的整数次方

题目描述

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

解题思路

在解这道题的时候，我总共经历过以下的修改：

1. 我的主逻辑写成了以下这个样子，结果报了错误，“error: control reaches end of non-void function [-Werror=return-type]”，这是gcc的一个编译选项-Werror=return-type。当一个函数的返回值不是void，但最后一句话不是return的时候，一般会报一个warning，但是这个编译选项把它作为error。实际上，理论上这个代码是没有问题的，但是因为编译选项比较严格，所以这就导致了我的第一个错误：编译出错。

double
myPow (double x, int n)
{
  if (n > 0)
    {
      return positive_pow (x, n);
    }
  else if (n < 0)
    {
      return 1 / positive_pow (x, -1 * (long)n);
    }
  else
    {
      return 1;
    }
}

1. 第二个错误是当case为“0.00001 2147483647”时，时间超出了限制。我原来的代码虽然区分了exponent为0、正数、负数的时候，但是没有再做进一步的优化。这边可以使用将指数除以2的方式，再将得到的结果相乘，以提升时间效率。当然，指数除以2、3、4……都应该是没问题的。
2. 第三个错误是当case中的指数为“-2147483648”时，这又是一个比较tricky的地方。当辅助函数的指数的类型为int或unsigned的时候，由于int（32位）的表示范围是-2147483648到2147483647，所以int是表示不了-2147483648的相反数2147483648的。所以，出了一个下策将辅助函数的指数的类型改为long。另外，这边还有一个小问题，即-1*n时，根据计算时的隐式数据类型转换，-1*n得到的结果的类型是int的，然后才根据调用函数的数据类型转为long，所以，必须提前将n做一下强制类型转换。

代码

double positive_pow (double x, long n);

double
myPow (double x, int n)
{
  if (n > 0)
    {
      return positive_pow (x, n);
    }
  else if (n < 0)
    {
      return 1 / positive_pow (x, -1 * (long)n);
    }
  return 1;
}

double
positive_pow (double x, long n)
{
  if (n == 0)
    return 1;
  if (n == 1)
    return x;
  double res = positive_pow (x, n / 2);
  res *= res;
  if (n & 1)
    res *= x;
  return res;
}

结果

执行结果：通过

执行用时：4 ms, 在所有 C 提交中击败了41.76%的用户

内存消耗：5.4 MB, 在所有 C 提交中击败了14.63%的用户

备注