题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。

示例1

输入

2.00000,3

返回值

8.00000

思路

其实这道题并不难，要么暴力，要么快速幂。因为最近笔试遇到快速幂的问题卡壳了，就觉得以前死记硬背的还是容易忘，所以决定从原理层面再过一遍快速幂。

快速幂原理

快速幂可以节省时间最主要的原因是它将base的n次方保留下来，不用每次求的时候都再次进行n个base相乘。从而把时间复杂度从O(N)降到O(lgN)。

快速幂代码

double Power(double base, int exponent) {
    if(base == 0) return 0;
    double ans = 1;
    while(exponent!=0){
        if(exponent&1!=0)%odd
        { 
            ans *= base;
        }
        exponent >>= 1;
        base *= base;
    }
    return ans;
}

以2⁵为例，程序运行的变量变化规律如下表所示。

具体分析

根据上文对程序运行变量的观察，可以得出求幂次的过程可以进行如下分解
eg1. 2⁵ = 2¹ * 4⁰ * 16¹ (101为5的二进制)
eg2. 2¹³ = 2¹ * 4⁰ * 16¹ * 32¹ (1101为13的二进制)
所以可以得出
base^exponent = base^exponent&1 * (base²)^{exponent>>1&1} * (base⁴)^{exponent>>2&1} * ...

题解

class Solution {
public:
    double Power(double base, int exponent) {
        if(base == 0) return 0;
        bool flag = 0;
        if(exponent<0) exponent = -exponent, flag = !flag;
        double ans = 1;
        while(exponent){
            if(exponent&1){
                ans *= base;
            }
            exponent >>= 1;
            base *= base;
        }
        return flag?1/ans:ans;
    }
};