剑指offer-JZ12

C++
数***算，很明显这是需要在二进制上操作，但是可以先用暴力法测试一些边界条件。
利用暴力法时，需要注意当指数为负时的情况：

class Solution {
public:
    double Power(double base, int exponent) {
        if ( exponent < 0 ) {
            base = 1 / base;
            exponent = -exponent;
        }
        double ans = 1.0;
        for (int i=0; i<exponent; i++)
            ans = ans *base;
        return ans;
    }
};

其中幂可以不用便利计算，可以利用递归减少计算量
递归法：

class Solution {
public:

    double q_power(double b, int n){
        if (n == 0) return 1.0;
        double ans = q_power(b, n/2);
        if (n&1){
            return ans*ans*b;
        }else{
            return ans*ans;
        }
    }
    double Power(double base, int exponent) {
        if ( exponent < 0 ) {
            base = 1 / base;
            exponent = -exponent;
        }
        return q_power(base, exponent);

    }
};

对其进行优化，利用二进制的表达原理：

因此当约束exponent为正数时，

所当e=base，
代码如下：

class Solution {
public:
    double Power(double base, int exponent) {
        if ( exponent < 0 ) {
            base = 1 / base;
            exponent = -exponent;
        }
        double x = base;
        double ans=1.0;
        while(exponent){
            if (exponent&1){
                ans *=x;
            }
            x *= x;
            exponent >>=1;
        }
        return ans;
    }
};