【剑指offer】数值的整数次方

很经典的快速幂算法，当时学的时候真是一头雾水啊难啊，不过现在看来都是菜菜，哈哈哈~

// 看offer书，突然想到一个学习快速幂算法的思路：先看书上的公式，试着递归求解，递归求解思路还是很清晰的，最最后试着看递推思路。（一上来学递推思路有点吃力）

// 递推写法
public class Solution {
    public static double Power(double base, int exp) {

        boolean flag = false;
        if (exp < 0) {
            flag = true;
            exp = -exp;
        }
        double ans = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                ans = ans * base;
            }
            exp >>= 1;
            base *= base;
        }
        return flag ? 1 / ans : ans;
    }
}

我竟然没写过递归的快速幂算法，成功get到新技能~

// 递归写法
public class Solution {
    public static double Power(double base, int exp) {
        boolean flag = exp < 0;
        if (flag) {
            exp = -exp;
        }
        double result = getPower(base, exp);
        return flag ? 1 / result : result;
    }

    public static double getPower(double base, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp == 1) {
            return base;
        }
        double ans = getPower(base, exp >> 1);
        ans *= ans;
        if ((exp & 1) == 1) {
            ans *= base;
        }
        return ans;
    }
}