剑指 Offer 16. 数值的整数次方

剑指 Offer 16. 数值的整数次方

剑指 Offer 16. 数值的整数次方

要求不使用库函数来实现pow（x,b）

用右移运算代替/2、用位与运算代表求余运算来判断一个数是奇数还是偶数（位运算的效率比乘除法及求余运算的效率要高很多）

假设我们要求一个数的32次方，则只用2次方，4次方，8次方，16次方，32次方（五次）较大程度减少了时间复杂度，而对于奇数次方，例如5次方，则需要一个判奇数偶数条件（n&1）只需要2次方，四次方，再乘上之前的res存储的一次方，就能实现五次方。

详细步骤见代码

class Solution {
public:
//快速幂法 可将时间复杂度降低至 O(log_2 n)
     double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        //将5的-2次方转位 1/5的平方
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            //b&1 =0为偶数 =1为奇数
            //a>>1 =a/2
            //a<<1 = a*2
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
};

时间复杂度 O(log_2 n)        (二分的时间复杂度为对数级别。) 
空间复杂度 O(1) ： res, b 等变量占用常数大小额外空间。