【35】实现Power函数

题目：给定一个函数原型Power(double base, int exponent)，要求实现该函数，并且不能使用库函数也不用考虑大数问题。

分析：

1. 最简单的实现Power函数是直接利用for循环，这样时间复杂度为O(n)。

2. 我们可以利用快速幂来求解，这样就可以把时间复杂度降低到O(logn)

3. 注意几个问题

  （1）base是否为0，如果是0则0的几次幂都是0

  （2）exponent是否为0，如果为0则返回1；如果小于0则要先求正次幂然后再利用倒数x^(-5) = 1/(x^5)；如果是正数则正常求解

代码：

#include<iostream>
#include<algorithm>
using namespace std;

const double eps = 1e-9;

//判断两个浮点数相等
bool IsEqual(double n, double m){
    if(((n-m)> -eps) && ((n-m) < eps)){
        return true;
    }
    else{
        return false;
	}
} 

//快速幂 
double QuickPower(double base, int exponent){
    double ans = 1;
    while(exponent){
        if(exponent&1 == 1){
		    ans = ans*base; 
        }
        base = base*base;
        exponent >>= 1;
    }
    return ans;
} 

//Power函数
double Power(double base, int exponent){
    //base为0，浮点数判断不能直接== 
	if(IsEqual(base, 0.0)){
        return 0;
	} 
	//exponent为0返回1
	if(exponent == 0){
	    return 1;
    } 
    //先求正数次幂的值
	double ans = QuickPower(base, abs(exponent));
	//判断是否是负数次幂
	if(exponent < 0){
	     ans = 1.0/ans;
    } 
    return ans;
} 
 

int main(){ 
    cout<<Power(0,5)<<endl; 
    cout<<Power(4,0)<<endl;
    cout<<Power(4.0,8)<<endl;
    
    return 0;
}
/*
输出
0
1
65536 
*/