题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
思路：用快速幂 附上wiki：https://oi-wiki.org/math/quick-pow/
两种实现方式：
1.递归
2.非递归
代码：
class Solution { public: double Power(double base, int exponent) { long long p = abs((long long) exponent); double res = 1; while(p > 0){ if(p & 1) res *= base; base *= base; p >>= 1; } return exponent < 0 ? 1/res : res; } };
算法描述¶
计算 的 次方表示将 个 乘在一起： 个 。然而当 太大的时侯，这种方法就不太适用了。不过我们知道： 。二进制取幂的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。
首先我们将 表示为 2 进制，举一个例子：
因为 有 个二进制位，因此当我们知道了 后，我们只用计算 次乘法就可以计算出 。
于是我们只需要知道一个快速的方法来计算上述 3 的 次幂的序列。这个问题很简单，因为序列中（除第一个）任意一个元素就是其前一个元素的平方。举一个例子：
因此为了计算 ，我们只需要将对应二进制位为 1 的整系数幂乘起来就行了：
将上述过程说得形式化一些，如果把 写作二进制为 ，那么有：
其中 。那么就有
根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 项推出 项。
这个算法的复杂度是 的，我们计算了 个 次幂的数，然后花费 的时间选择二进制为 1 对应的幂来相乘。