快速幂

注意到

$$ X^{62} = (X^{31})^2 \\ X^{31} = (X^{15})^2 \times X\\ X^{15} = (X^7)^2 \times X\\ X^7 = (X^3)^2 \times X\\ X^3 = X^2 \times X $$

至多进行两次乘法操作，可以将问题的规模缩小为原来的一半。所以，需要进行的乘法次数不超过2logN。

一个简单的递归实现

    public static long pow1(long base, int exponent) {
        // 基准情况
        if (exponent == 0)
            return 1;
        if (exponent == 1) 
            return base;
        if (exponent % 2 == 0) {
            return pow1(base * base, exponent / 2);
        } else {
            return pow1(base * base, exponent / 2) * base;
        }
    }

优化后的递归实现

上面代码中第四行的判断其实是不必要的，因为 N = 1 的情形也可以正常处理。如果我们删除无用的判断，并尽可能地使用位运算可以得到下面代码。

    public static long pow2(long base, int exponent) {
        // 基准情况
        if (exponent == 0)
            return 1;
        if ((exponent & 1) == 0) {
            return pow2(base * base, exponent >> 1);
        } else {
            return pow2(base * base, exponent >> 1) * base;
        }
    }

使用循环代替递归

进一步优化，我们使用循环代替递归。

    public static long pow3(long base, int expoent) {
        if (expoent == 0)
            return 1;
        long result = 1;
        while(expoent != 1) {
            if ((expoent & 1) == 1) {
                result *= base;
            }
            expoent >>= 1;
            base *= base;
        }
        result *= base;
        return result;
    }