【2错1对-1】数值的整数次方

https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

日期	是否一次通过	comment
2019-02-05 20:20	N	不会取巧
2019-02-06 09:20	Y	💪
2019-02-10 12:20	N	非递归一次通过，递归卡住了

题目：实现Math.pow(x, n)
思路：

1. >>1相当于int型变量/2；

3. 尾递归和非递归终止条件的差异：
   a. 尾递归终止条件是0：实际上1结束后，计算已经完成；如果终止条件是1，考虑幂次直接为0时，递归没有结束条件；
   b. 非递归终止条件是1：实际上1结束后，计算已经完成；幂次为0的情况已经兜底；如果终止条件是0，无法跳出循环。

1. 尾递归

public class Solution {
    public double Power(double base, int exponent) {
       return helper(1.0, base, exponent);
    }
     
    private double helper(double result, double base, int exponent) {
        if(exponent < 0) {
            return helper(result, 1/base, -exponent);
        }
         
        if(exponent == 0) {
            return result;
        }
         
       
         
        if((exponent & 1) == 1) {
            return helper(result*base, base*base, exponent>>1);
        } else {
            return helper(result, base*base, exponent>>1);
        }
    }
}

2. 非递归

public class Solution {
    public double Power(double base, int exponent) {
        double result = 1.0;
        if(exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }
         
        while(exponent > 0) {
            if((exponent & 1) == 1) {
                result *= base;
            }
             
            base *= base;
            exponent >>= 1;
        }
         
        return result;
    }
}