剑指Offer_数值的整数次方

题目描述：

            给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

            思路1：最简单的肯定是直接调用API  return Math.pow(base,exponent);，面试官肯定是不会喜欢的；那么可以分类讨论，把base连乘N次,直接求解呢？ 这种肯定是可以的，但是这样使用的时间复杂度是O(n);

            思路2：划分思想 要求 base的exponent次幂，那么我们可以这么考虑（这里只考虑正数的情况）：

                        情况1：如果exponent是奇数

                                    temp=Math.pow(base,exponent/2)；

                                    result=base*temp*temp;

                        情况2：如果exponent是偶数

                                   temp=Math.pow(base,exponent/2)；

                                    result=temp*temp;

            这样再加划分的结果乘起来时间复杂度就是O（logN）；

程序：递归版

            

非递归版：

            

Copy:    

public double Power(double base, int exponent) {

        double result=1.0;
        int y=exponent;
        if(exponent<0){
            if(base==0)
                throw new RuntimeException("分母不能为零");
            y=-y;
        }
        else if(exponent==0)
            return 1;
        double harf=Power(base,y>>1);
        result=harf*harf;
        if((y&1)==1){//如果是奇数幂{
            result*=base;
        }
        if(exponent<0)
            result=1/result;
        return result;
    }
    
    
    
    public double Power(double base, int exponent) {
        boolean flag=true;//表示是正数次幂；
        double res=1.0;
        if(exponent<0){
            if(base==0)
                throw new RuntimeException("分母不能为零");
            exponent=-exponent;
            flag=false;
        }
        else if(exponent==0)
            return 1;
        while(exponent!=0){
            if((exponent&1)==1)//如果是base的奇数次幂 ，那么就乘一个base，使幂变成偶数
                res*=base;
            base=base*base;//先求基数的平方
            exponent>>=1;//再把幂/2
        }
        if(flag)
            return  res;
        else
            return 1.0/res;
    }