题目：

快速幂

例子： x11x^{11}

原理：

  1. 将要求的幂的指数转为二进制形式，如11转换为1011。因此x11=x23+21+20x^{11}=x^{2^{3}+2^{1}+2^{0}}
  2. 由于x23+21+20=x23×x21×x20x^{2^{3}+2^{1}+2^{0}}=x^{2^{3}} \times x^{2^{1}} \times x^{2^{0}}，也就是只需要将每一位1所对应的权重相乘
  3. 实现方法就是首先初始化long b = n和double res = 1.0，使用按位与1运算判断最小位是否为1。如果为1，则res乘上此时的底数x。操作完成后b需要右移一位。
  4. 在进入下一次循环之前，需要让底数的指数翻倍x *= x，以匹配右移后的b。

剑16代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0){
            if((b & 1) == 1){
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

快速幂求余

剑14-II：这道题虽然可以直接用上述的快速幂封装方法代替Math.pow()或者a ** b，但是K神用的方法看起来更牛逼，还是学习一下。

如果直接使用封装的快速幂方法，则需要修改如下。依据是求余的性质

(xy)⊙p=[(x⊙p)(y⊙p)]⊙p(x y) \odot p=[(x \odot p)(y \odot p)] \odot p 

1
2
3
4
5
6
7
8
9
10
11
12
13
public long myPow(long x, int n) {
  long res = 1;
  while(n > 0) {
    if((n & 1) == 1) {
      res *= x;
      res = res % mod;
    }
    n = n >> 1;
    x *= x;
    x = x % mod;
  }
  return res;
}

然后把剑14-I的解法套过来就好～