数值的整数次方

问题陈述

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

快速幂解析

快速幂是二分思想的一种应用。

根据二分推导，可通过循环x=x^2操作，每次将幂n降至n/2，直至将幂降为0。

设res=1，则初始状态xn=xnres，在循环二分时，当n为奇数，将多出的一项乘以res，偶数则不用处理，最终x^n=1res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public double myPow(double x,int n){
        if(x==0) return 0;
        long b=n;  //由于int范围n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -nn=−n 会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。

        double res=1;
        if(b<0){
            x=1/x;
            b=-b;
        }
        while(b>0){
            if(b&1==1){  // b%2==1?
                res*=x;
            } 
            x*=x;  // x=x^2
            b>>=1;  //b=b/2;
        }
        return res;
    }
}