求解一个数的 N 次幂，通常使用 pow 函数。要求 a^N，最最显而易见的方法是用 N 个 a 连续做乘法，幸运的是，我们有更快的算法。

最常见的一种方法是采用递归的求解方式，如下：

递归解法：

long int pow(int x, unsigned int N){
    if (N == 0){
        return 1;
    }
    if (N == 1){
        return x;
    }
    if (N & 1 == 0){
        return pow(x * x, N / 2);
    } else {
        return pow(x * x, N / 2) * x;
    }
}

这个算法的复杂度无疑是 O(logN) 的。

下面不采用递归来求解：

非递归解法：

long int pow(int x, unsigned int N){
    int ans, n;
    ans = 1;
    n = x;
    while (N != 0){
        if (N & 1 == 1){
            ans = ans * n;
        }
        n = n * n;
        N >> 1;
    }
    return ans;
}

下面来分析一下以上算法的原理：

先举个例子，假如希望求 5^62，也就是 5 的 62 次方。为了算法高效，一个原则就是不做重复的计算。

5^62 = 5^(32+16+8+4+2) = 5^32 * 5^16 * 5^8 * 5^4 * 5^2

不管指数是多少，都可以将其分解为 2 的倍数的和，因为任何整数都能够写成 2 进制的形式，比如 62 = 00111110B。

以上算法中，随着迭代 n 会变成 x, x^2, x^4, x^8,…，我们只需要在合适的时候让它和 ans 相乘即可。合适的时刻就是 N 的二进制表示的相应位上为 1 的时候，这里使用了右移，只需要判断最低位是不是 1 就好了。

这个算法也是 O(logN) 的，但是没有使用递归。