这是《剑指Offer》的第十六题：

实现 pow(x, n)，即计算 x 的 n 次幂函数（即 x^n）。不得使用库函数，同时不需要考虑大数问题。

我想通过这道题来整理如下的知识点：

  1. 对特殊情况的考虑以增加程序的鲁棒性
  2. 符点数的相互比较
  3. 快速求幂的递归方法
  4. 快速求幂的循环方法
  5. 位运算的一些技巧

下面，我们来逐一介绍它们。

这道题要我们求 x^n，那么我们首先应该想到针对 x 和 n 的取值不同进行分情况讨论：

  • x == 0 && n < 0，这种是除 0 的情况，属于非法输入，应该返回一个指示错误的值
  • x == 0 && n = 0，这种情况是 0^0，数学上无意义，可以返回 1 或 0
  • n < 0，我们可以先求 x^(-n)，最后返回 1.0 / x^(-n)
  • x == -1.0，则我们可以返回 n & 0x01 ? -1.0 : 1.0
  • x == 1.0，因为 1.0 的幂次永远等于 1.0，所以我们直接返回 1.0

除此之外，我们可以用一些小 trick 来加快程序的运行速度，如当在循环计算 x^n 的值 res 的时候，如果 res 非常接近于 0.0，那么我们直接返回 0.0。

在考虑到这些特殊情况之后，我想我们就可以一次性通过 Leetcode 上关于这道题的所有测试 用例。这是我想总结的第一点。

另外，题目中 x 实际上是一个 double 类型的数，我们在上述讨论中需要用 x 和 0.0，1.0 等 常数符点数进行相等判断。符点数的相等和整数的略有不同，因为精度的原因，符点数不能直接用运算符 “==” 进行判断，而是要借助库函数 fabs() 进行判断。如我们想判断 x 和 0.0 是否相等， 我们可以这样做：

#include <math.h> /* for fabs() */
#define EPSILON 0.000001

fabs(x - 0.0) < EPSILON

你也可以写一个宏定义，更加方便的比较两个符点数：

#include <math.h> /* for fabs() */
#define EPSILON 0.000001
#define compareDouble(x, y) fabs((x) - (y)) < EPSILON

if (compareDouble(x, 0.0)) {
    ... ...
}

这是我们要说的第二点，符点数的比较。

接下来，我们来看第三点，快速求幂的递归方法。一想到递归，我们首先应该想到 得有一个递归公式。那么如何得到递归公式呢？一般是采用找规律的方法。我们可以把 x^n 这样表示：

      (x^2)^(n/2), n & 0x01 == 0
    /
x^n
    \
      x * (x^2)^(n/2), n & 0x01 == 1

那么我们把上述公式看成是 n 的函数，令 f(n) = x^n，就有：

      [f(n/2)]^2, n & 0x01 == 0
    /
f(n)
    \
      [f(n/2)]^2 * x, n & 0x01 == 1

哎，你看我们想要的递归公式就有了。接着我们就可以轻松的写出递归代码：

double myPowCore(double x, long n)
{
    if (n == 0)
        return 1.0;
    double y = myPowCore(x, n / 2);
    return n & 0x01 ? y * y * x : y * y;
}

我们常规方法求 x^n，通常是写一个循环，每次循环乘一个 x，最终 循环 n 次，时间复杂度为 O(n)。而上述的递归方法，每次都将 n 变为 n / 2，所以时间复杂度为 O(logn)；又因为递归会产生 logn 个子函数， 它们会占用内存栈空间，所以空间复杂度为 O(logn)。这是我们要说的 第三点。这是我 的提交记录。

另外，递归是自上而下的解决问题，你看，对于这道题，我们的目标是 求 f(n)，为了求 f(n)，我们需要求 f(n / 2)；然后我们为了求 f(n / 2)， 我们又得去求 f(n / 4)……因此它是一个自上而下的过程。而一个自上而下的 递归算法，往往也可以用自下而上的动态规划来解决，斐波那契数列就是一个 很好的例子。这道题，我们已经有了递归函数来填满动态规划的数组 array，而且 我们还知道 array[0] = 1.0，接下来 就是用一个循环，把大小为 n + 1 的数组填满，array[n] 就是最终的结果。 当然，对于这道题，动态规划的方法时间复杂度和空间复杂度都是 O(n)，是所有 方法中效率最低的，但是我认为这依旧是一个很好的练习，它可以帮助我们更好 地理解递归和动态规划背后蕴含的自上而下和自下而上的思想。这是我的动态规划的提交记录。

接下来我们再来看第四点，快速求幂的循环方法。我们可以把 n 写成它的二进制表示：

n = 2^0*b0 + 2^1*b1 + 2^2*b2 + ... + 2^m*bm

那么，x^n 就可以表示为：

x^n = x^(2^0*b0 + 2^1*b1 + 2^2*b2 + ... + 2^m*bm)

b0，b1，... ，bm 其实就是 n 的二进制表示的各个位，它们的值是 0 或 1。只有 bi (i ∈ [0, m]) 为 1 时， x^(2^i*bi) 才有意义。所以我们可以利用这一点写出如下代码：

double res = 1.0
while (n) {
    if (n & 0x01)
        res *= x;
    n >>= 1;
    x *= x;
}

这个方法的时间复杂度为 O(logn)，空间复杂度为 O(1)。这是我的提交记录。这是我们要说的第四点。

最后，我们看到第四点的方法中有两个位操作，第一个，n & 0x01，用来判断 n 的最低位是 0 还是 1， 同时也可以用来判断 n 是偶数还是奇数，等价于 n % 2，但是比直接用运算符 % 更快。第二个，n >>= 1， 这个用来对 n 进行右移一位操作，并把结果再赋值给 n。这个等价于 n /= 2，但是要比用运算符 / 来得 更快。这些位操作可以加快你程序的运行速度，一开始可能用不习惯，但是坚持用下去就可能使你的程序 显得更加的简单和高效，namely，更加优雅。这是我们要讲的第五点。

以上。