题目描述
给定一个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;
}
以25为例，程序运行的变量变化规律如下表所示。
| 3 | 2 | 1 | 0 | odd | base | ans | newbase | newans |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | yes | 2 | 1 | 4 | 2 |
| 0 | 0 | 1 | 0 | no | 4 | 2 | 16 | 2 |
| 0 | 0 | 0 | 1 | yes | 16 | 2 | 256 | 32 |
具体分析
根据上文对程序运行变量的观察，可以得出求幂次的过程可以进行如下分解
eg1. 25 = 21 * 40 * 161 (101为5的二进制)
eg2. 213 = 21 * 40 * 161 * 321 (1101为13的二进制)
所以可以得出
baseexponent = baseexponent&1 * (base2)exponent>>1&1 * (base4)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;
}
};
