【剑指offer-C++】JZ16：数值的整数次方

题目描述

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

注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题。
3.有特殊判题，不用考虑小数点后面0的位数。

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

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

输入：2.00000,3
返回值：8.00000

输入：2.10000,3
返回值：9.26100

输入：2.00000,-2
返回值：0.25000
说明：2的-2次方等于1/4=0.25

解题思路

数值的整数次方：最直观的想法是，求a的b次方，使用for循环直接循环b次。更快求数值的整数次方的方法是快速幂，其基本思想是：如果b是偶数，那么a^b就分为a^b/2×a^b/2；如果b是奇数，那么a^b就分为a^b-1×a。举一个通俗易懂的例子，比如求5⁵，则5⁵=5⁴×5，5⁴=5²×5²，5²=5¹×5¹。如果使用计算机来实现的话，可以使用二进制来判断，当指数大于0时进入循环，首先判断指数的最后一位是否为1，如果是则将其乘入结果，同时每次循环中还需要对底数进行自乘并将指数右移一位，为下次循环做准备。

double Power(double base, int exponent) 
{double result=1;bool flag=exponent>0?true:false;exponent=abs(exponent);while(exponent>0){if(exponent&1) //二进制最后一位是1result*=base;base*=base;exponent>>=1;}return flag==true?result:1.0/result;;
}