剑指offer 12 数值的整数次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

// 简单快速幂
class Solution {
public:
    double Power(double base, int exponent) {
        long long p = abs((long long)exponent);
        double r = 1.0;
        while(p){
            if(p & 1) r *= base;
            base *= base;
            p >>= 1;
        }
        return exponent < 0 ? 1/ r : r;
    }
};

第一种方法：使用递归，时间复杂度O(logn)
当n为偶数，a^n =（a^n/2）*（a^n/2）
当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
举例：
2^11 = 2^1 * 2^2 * 2^8
2^1011 = 2^0001 * 2^0010 * 2^1000

第二种方法：累乘，时间复杂度为O(n)