题目描述

实现函数double Power（double base, int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

样例

样例1
输入：10 ，2
输出：100

样例2
输入：10 ，-2  
输出：0.01

算法

$10^4=10^2\times10^2$
$10^5=10^2\times10^2\times10$

时间复杂度 $O(logn)$

参考文献

【剑指offer】

Java 代码

class Solution {

    public double Power(double base, int exponent) {
        if(base==0 && exponent==0){
            throw new RuntimeException("base==0 && exponent==0");
        }
        if(exponent>0){
            return dfs(base,exponent);
        }
        if(exponent<0){
            return 1/dfs(base,-exponent);
        }
        return 1;
    }

    public double dfs(double base, int exponent) {
        if(exponent==1){
            return base;
        }
        double result=dfs(base,exponent>>1);
        result*=result;
        if((exponent&1)==1){
            result*=base;
        }
        return result;
    }
}