递归训练三：剑指 Offer 16. 数值的整数次方
题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104
原题链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
题解
这道题是典型的快速幂算法，但这道题坑比较多，除了要区别 n 是正数还是负数，还要考虑 n 取反溢出的问题。
思路：假设求 7 ^ 11
若将 n 用二进制来表示，则有 11 = 1011
那么 7 ^ 11 可以看成是 7 ^ 11 = 7^1 * 7^2 * 7^0 * 7^8 = 7^1 * 7^2 * 7^8
故我们可以每次判断 n 的二进制数中的最后一位数字是否是 1
是的话结果就必须乘 x，若不是的话，就不处理。
不过不管是不是，x 每一轮都要翻倍。
解决快速幂后，就解决正负数的问题。
一开始没有考虑到 2^31 次方的问题（取相反数后也是 2^31 次方）
故需要用一个 long 类型来接收 n，然后再去取相反数。
先判断 n
（1）正数，不用做操作
（2）0，直接返回 0
（3）负数，转为正数并将 x 倒过来。
递归版本的代码如下
class Solution {
public double myPow(double x, int n) {
if (x == 0) // 若是 0，直接返回
return 0;
double res = 1.0; // 存放结果
long b = n; // 用 long 来存储 n
if (n < 0){ // 考虑负数情况
x = 1/x;
b = -b;
}
return quitPow(x, b);
}
public double quitPow(double x, long n){
if (n == 0)
return 1;
// 位运算，& 是 与 运算，可以用来判断 n 的二进制数的最后一位是否为 1
if ((n & 1) == 1)
return x * quitPow(x*x, n >>1 );
return quitPow(x*x, n >> 1);
}
}
这里也顺便提供一下非递归版本的代码
class Solution {
public double myPow(double x, int n) {
if (x == 0) // 若是 0，直接返回
return 0;
double res = 1.0; // 结果
long b = n; // 用 long 来存储 n
if (n < 0){ // 考虑负数情况
x = 1/x;
b = -b;
}
while (b > 0){ // 快速幂
if ((b & 1) == 1)
res *= x;
x *= x;
b >>= 1;
}
return res;
}
}