数值的整数次方

一、使用递归的快速幂

求base的exponent次方，可分为以下两种

我们可以使用递归进行求解此问题
但是还有一个问题就是，当n为负数的时候，那么求得的最终结果必定是当n为正数时求的结果的倒数，
所以我们还需要有一个标记，标记n是正数还是负数。

public double Power(double base, int exponent) {
        if(exponent == 0)
            return 1;
        if(exponent == 1)
            return base;  /*两个特判*/
        boolean isNegative = false;  /*用来标记exponent是否为负数*/
        if(exponent < 0){
            exponent = -exponent;   /*这里将exponent重新变为正数*/
            isNegative = true;      /*标志为负数*/
        }
        double pow = Power(base*base, exponent/2);   /*递归求解*/
        if(exponent % 2 != 0){          /*如果exponent为奇数，则还需要乘多一边base*/
            pow *= base;
        }
        return isNegative ? 1/pow:pow;   /*判断exponent为正数还是负数*/
  }

二、非递归的快速幂

已知6可以表示成二进制110


所以将指数跟1进行与运算，如果不为0，则表示当前位需要乘进结果中，具体看代码就能够明白

public double Power(double base, int exponent) {
        // exponent为负数则先将底数取倒数，然后按指数为正数的去计算
        if(exponent < 0){
            base = 1/base;
            exponent = -exponent;
        }
        double res = 1.0;   /*作为返回结果*/
        while(exponent != 0){   /*当指数不为0时*/
            if((exponent&1)==1)   /*等于1，则证明当前位数需要乘进结果*/
                res *= base;
            base*=base;
            exponent >>= 1;
        }
        return res;
  }

以base=3，exponent=6为例子，用表格记录每次操作