剑指offer | 16.数值的整数次方

ゝ一纸荒年。 2022-12-25 13:50 96阅读 0赞

**题目内容**

> 实现函数double Power(double base, int  
> exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

**示例 1:**

输入: 2.00000, 10
    输出: 1024.00000

**示例 2:**

输入: 2.10000, 3
    输出: 9.26100

**示例 3:**

输入: 2.00000, -2
    输出: 0.25000
    解释: 2-2 = 1/2^2 = 1/4 = 0.25

**说明:**

-100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

--------------------

**思路：**

*  因为直接连乘会超时，但是其实你会发现 x 8 x^8 x8就相当于4个 x 2 x^2 x2连乘，所以当算出 x 2 x^2 x2后再乘3次自己就可以了，这样比原来要乘7次的时间少得多。
 *  然后再用快速幂求解， x n x^n xn中n的二进制可以分解成若干个0和1，比如 x 9 x^9 x9中，9=1001= 1 ∗ 2 3 1\*2^3 1∗23\+ 0 ∗ 2 2 0\*2^2 0∗22\+ 0 ∗ 2 1 0\*2^1 0∗21\+ 1 ∗ 2 0 1\*2^0 1∗20;即：  
    ![在这里插入图片描述][20201202074119116.png]
 *  所以可以看出，每次乘的值都是前一个值的两倍，当n的二进制位为0时跳过。
 *  负数幂和正数幂相同，因为除以一个数就相当于乘这个数的倒数。

**完整代码：**

class Solution { 
    public:
        double myPow(double x, int n) { 
            if(x == 1 || n == 0) return 1;
            double ans = 1;
            long num = n;//因为如果 n = -2^31，那么后面 num = -num = 2^31，用 int 的话会溢出
            if(n < 0){ 
                num = -num;
                x = 1/x;
            }
            while(num){ 
                if(num & 1) ans *= x;
                x *= x;
                num >>= 1;
            }
            return ans;
        }
    };

![在这里插入图片描述][20201202075045936.png]

参考：[C++ 乘法快速幂][C_]

[20201202074119116.png]: /images/20221120/6c198de393f94a158b3891396a5296b1.png
[20201202075045936.png]: https://img-blog.csdnimg.cn/20201202075045936.png
[C_]: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/c-cheng-fa-kuai-su-mi-by-yizhe-shi/