剑指offer(C++)-JZ16：数值的整数次方(算法-位运算)

题目描述：

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：

1.保证base和exponent不同时为0。

2.不得使用库函数，同时不需要考虑大数问题

3.有特殊判题，不用考虑小数点后面0的位数。

数据范围： ∣base∣≤100  ，∣exponent∣≤100  ,保证最终结果一定满足∣val∣≤104

进阶：空间复杂度O(1)  ，时间复杂度O(n)  

示例：

输入：

2.00000,-2

返回值：

0.25000

说明：

2的-2次方等于1/4=0.25

解题思路：

本题考察位运算。三种解题思路。

1）暴力法

      循环累乘即可。复杂度O(n)。

2）位运算-快速幂

      对次方数进行位运算即可实现快速幂计算。复杂度O(logn)。

      如13次方是1101，分别是1、4、8，也就是说base的13次方等于base的1次方*base的4次方*base的8次方。以此为例，下面文字讲述过程便于理解。

      a)首次进入循环后，当前次方数是1101，&1可得true，result乘base，然后将base*=base，base就变成了2次方，位运算右移得到0110。

      b)第二次循环，&1得到false，也就是说当前低位是0，result不需要乘base，继续累乘base，base就变成了4次方，位运算右移得到0011。

      c)第三次循环，&1得到true，result乘base，此时的base是4次方，result就变成base的5次方，然后累乘base，base变成8次方，位运算右移得到0001。

      d)第四次循环，&1得到true，result乘base，base是8次方，result就变成了base的13次方，然后累乘base，base变成16次方，位运算右移得到0000。

      e)退出循环，返回result。

测试代码：

1）暴力法

class Solution {
public:
    double Power(double base, int exponent) {
        // 负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        // 累乘
        double result = 1;
        for(int i = 0; i < exponent; ++i){
            result *= base;
        }
        return result;
    }
};

2）位运算-快速幂

class Solution {
public:
    double Power(double base, int exponent) {
        // 负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        // 位运算实现快速幂
        double result = 1;
        while(exponent){
            if(exponent & 1){
                result *= base;
            }
            base *= base;
            exponent = exponent >> 1;
        }
        return result;
    }
};