从零学算法50

50.实现 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

• 还真没我想的那么简单，这题可以学一下快速幂，我就直接说结论了，有兴趣的可以看原文。ok 首先显而易见我们最终要求的是 xⁿ，然后我们知道 xⁿ = x^a+b(a+b=n)=x^ax^b。神来之笔就来了，我们把 n 转成二进制，比如 n 为 5，我们就得到了 0101，二进制转十进制都知道吧，这个 0101 的含义就是 0 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰，也就是说 xⁿ 比如 x⁵ 我们最终可以表示成 x⁰¹⁰¹ 也就是 x 的 0 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰ 次 = x^8x0x^4x1x^2X0x^1x1，你会发现这最终转换成了求 x^1ax^2bx^4cx^8d…x^y的问题，所以我们最终遍历求解时只需要两个操作，不断累乘 x 使得其成为 x¹x²x⁴…，还有就是不断获取那些 abcd 是 0 还是 1，获取也很简单，二进制数 b 的最右位为 b&1，取完以后 b>>1，就等于把第二最右位移到了最右位。

•   public double myPow(double x, int n) {
        long b = n;
        double ans = 1.0;
        // 由于 int 范围为 -2的31次 <= n <= 2的31次-1，所以 -n 可能会超出 int 能表示最大值，就用了 long
        if(b < 0){
            b=-b;
            x=1/x;
        }
        while(b>0){
        	// 如果此时的 abcd 对应的是 1 就乘 x，否则其实就是乘以 1，所以可以跳过
            if((b&1)==1)ans*=x;
            // 累乘 x 得到下一个 x 的 y 次方（y 为 2 的 n 次）
            x*=x;
            // 等待下一位 abcd，因为 >> 相当于整除 2，所以循环结束条件就是 b > 0
            b>>=1;
        }
        return ans;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18