面试题 16：数值的整数次方.md

试题链接：27. 数值的整数次方 - AcWing题库

方法一：快速幂

• 思路：底数为 0 直接返回 0，指数为 0 直接返回 1。考虑指数是否为负数，为负数则最终结果取倒数，用布尔变量标识；再考虑底数为负数且指数为奇数的情况，此时结果需要为负；注意指数可能取到整数的最小值，因此不能直接加符号转为正数，需要用一个长整形来存放。最后就变成了底数和指数都为整数的运算，使用快速幂得到结果后，在加上负号或者取反。
• 时间复杂度：O(logn)
• 空间复杂度：O(1)

class Solution {
public:
    double Power(double base, int exponent) {
        if (base == 0.0) return 0.0;
        if (exponent == 0) return 1.0;
        
        bool flag = false;
        long b = exponent;
        if (exponent < 0) {
            flag = true;
            b = -b;
        }
        
        bool sign = true;
        if (base < 0.0) {
            base = -base;
            if (b % 2) sign = false;
        }
        
        double ans = 1.0;
        while (b) {
            if (b & 1) ans *= base;
            base *= base;
            b >>= 1;
        }
        
        if (!sign) ans *= -1.0;
        if (flag) return 1.0 / ans;
        return ans;
    }
};