AcWing_27_数值的整数次方

题目

实现函数double Power(double base, int exponent)，求base的 exponent次方。
不得使用库函数，同时不需要考虑大数问题。
只要输出结果与答案的绝对误差不超过 10^(−2) 即视为正确。
注意：

不会出现底数和指数同为0的情况
当底数为0时，指数一定为正
底数的绝对值不超过 10，指数的绝对值不超过 109。

示例

示例1

输入：10 ，2
输出：100

示例2

输入：10 ，-2
输出：0.01

代码

解法：快速幂 O(logn)

class Solution {
public:
    double Power(double x, int n) {
        typedef long long LL;
        bool is_minus = n < 0;
        double res = 1;
        for (LL k = abs(LL(n)); k; k >>= 1) {
            if (k & 1) res *= x;
            x *= x;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
};

快速幂思想：

预处理出 $a^{2^0},a^{2^1},a^{2^2},\ldots,a^{2^{logb}}$.这b个数
将 $a^b$ 用 $a^{2^0},a^{2^1},a^{2^2},\ldots,a^{2^{logb}}$ 这b种数来组合,即组合成 $a^b=a^{2^{x_1}}\times a^{2^{x_2}}\times \ldots \times a^{2^{x_t}}=a^{2^{x_1}+2^{x_2}+\ldots+2^{x_t}}$ 即用二进制表示

1、为什么这样可行？每个数都可以用二进制表示，等于用每位数乘上该位对应的二进制权重。如 10：1010 = 1×2^3 + 0×2^2 + 1×2^1 + 0×2^0 = 10.同样幂也可以表示为二进制，然后用有效位的值相乘就可以了。视频讲解

2、为什么最大到 logb？还是举个例子来看，3 个 2 进制位可以表示 2^3 个十进制数。也就是 b 最多需要 logb 个二进制位来表示。

代码解析：代码太巧妙，令我不得不看

for (LL k = abs(LL(n)); k; k >>= 1) {
    if (k & 1) res *= x;
    x *= x;
}

先拿到幂的值，假如说为 10：1010 。k & 1 得到最低位 0 ，不用乘上该位对应的权重（最开始底数x为初识值，或者说是x^(2^0)），x *= x之后 x 为x^(2^1)，得到下一次最低位的权重，k >>= 1之后 k 的最低位是 1，乘上该位对应的权重x^(2^1)......我应该描述的更清楚才行。

以底为 3 幂为 10 为例

$$ \begin{align} & 3^{10}\\ & =2^{1010_{2}}\\ & =3^{1*2^{3}+0*2^{2}+1*2^{1}+0*2^{0}}\\ & =3^{1*2^{3}}*3^{0*2^{2}}*3^{1*2^{1}}*3^{0*2^{0}} \end{align} $$

题目：数值的整数次方