数值的整数次方

我当然只能想到最low的直接运算解法：

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double ret = 1.0;
        for (int i = 0; i < exp; ++i) {
            ret *= base;
        }
        return ret;
    }
}

这种数学类的题目我一般很讨厌就是难度不大，侮辱性极强，知道解法就很容易，不知道的时候就GG，考的比较偏，什么快速幂什么的对于我这种业余选手实在是第一次听说，好在理解上并不困难，因此这种题目我始终是作为一种开拓思路的心态。

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        return p(base, exp);
    }
    double p(double b, int n) {
        if (n == 0) 
            return 1.0;
        double ret = p(b, n / 2);
        if ((n & 1) == 1) { // 奇数
            return ret * ret * b;
        } else {
            return ret * ret;
        }
    }
}

非递归的快速幂：

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double ret = base;
        while (exp > 1) { // 以内ret的起始值是base，因此这里条件是大于1
            ret *= ret;
            if ((exp & 1) == 1) { // 奇数
                ret *= base;
            }
            exp >>= 1;
        }
        return ret;
    }
}

题解中的非递归快速幂的解法如下：

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double x = base, ret = 1.0;
        while (exp > 0) {
            if ((exp & 1) == 1) { // 奇数
                ret *= x;
            }
            x *= x;
            exp >>= 1;
        }
        return ret;
    }
}

题解中的是每次x平方，当exp为奇数时，才变更ret的值，我觉得这个解法首先是正确的，而且实现的也非常巧妙，但是觉得上手有点费解。