剑指offer 15. 数值的整数次方

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

只要输出结果与答案的绝对误差不超过 10⁻² 即视为正确。

注意：

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

样例1

输入：10 ，2

输出：100
1
2
3

样例2

输入：10 ，-2  

输出：0.01
1
2
3

方法一：快速幂 O(logn)

此题的指数是 $int$ 范围，可能会很大，所以要用到快速幂。这道题相当于是快速幂的模板题。

另外，需要注意的是如果指数为负数，在最后要计算一次倒数。

那么我们来看看何为快速幂，假如我们要计算 $x^5$ ，最暴力的做法就是将 $x$ 循环乘 $5$ 次。这样做虽然简便，但是一旦数据特别大的时候时间复杂度就会比较高，而快速幂就可以将 $O(n)$ 的时间复杂度降到 $O(logn)$ 。

而我们可以将快速幂看成把幂拆分成二进制的形式进行计算，比如 $x^5$ 就可以将幂变成二进制表示即 $x^{101}$ ，而 $x^{101}$ 又可以转换成 $x^4\times x^1$ 。可以发现这个幂拆分成二进制以后就只用看其最低位是否为 $1$ 即可，拿 $x^{21}$ 来举例：

第一步： 先将 $x^{21}$ 的幂转换成二进制表示，即 $k=21=10101$ ，而二进制对应的十进制可以用下面的表格来表示。可以发现当 $k$ 转换二进制后就非常直观，它其实就是 $2$ 的次方构成。
所以 $x^{21}$ 也可以表示成 $x^{16}\times x^4\times x^1$ ，其幂也可以由 $21$ 拆分成 $2^4+2^2+2^0$ ，故可以直接根据其最低位是否为 $1$ 进行累乘运算。

第二步： 进行快速幂运算，发现最低位为 $1$ ，所以用答案 $res$ 乘以当前位 $x^0$ ，并且 $base$ 需要乘以 $2$ 后续要用到，$k$ 同时右移判断下一位，而右移实际上就是除以 $2$ 。

第三步： 继续判断，发现最低位为 $0$ ，所以 $x^2$ 不会被乘到 $res$ 中去。

第四步： 继续判断，发现最低位为 $1$ ，所以 $x^4$ 会被乘到 $res$ 中去。

第五步： 继续判断，发现最低位为 $0$ ，所以 $x^8$ 不会被乘到 $res$ 中去。

第六步： 继续判断，发现最低位为 $1$ ，所以 $x^{1}6$ 会被乘到 $res$ 中去。

第七步： 判断幂是否为负数，如果为负数需要取倒数，然后输出结果即可。

class Solution {
public:
    double Power(double base, int exponent) {
        typedef long long int LL;
        bool is_minus = exponent < 0;
        double res = 1;
        for (LL k = abs((LL)exponent); k; k >>= 1) {
            if (k & 1) res *= base;
            base *= base;
        }
        if (is_minus)    res = 1 / res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

欢迎大家在评论区交流~