「力扣」第 50 题:Pow(x, n)

liweiwei1419 ... 2022-1-6 位运算
  • 位运算
About 2 min

今天要和大家分享的是「力扣」第 50 题:Pow(x, n)。这题有一个名称叫「快速幂」,我们这里只分享「递归」和「非递归」的写法,其中 「递归」对应「当指数为奇数时,把指数分解成偶数 + 1,当指数为偶数时,把指数除以 2」,「非递归」对应把指数转化成二进制。「快速幂」还有矩阵的求法,感兴趣的朋友可以在网络上自行搜索(我也不会)。

# 题目描述

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000
1
2

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100
1
2

示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示:

  • 100.0<x<100.0-100.0 < x < 100.0
  • 231n2311-2^{31} \le n \le 2^{31}-1
  • 104xn104-10^4 \le x^n \le 10^4

# 把指数部分看做二进制数(Python 代码)

当指数为负数的时候,可以转化为底数取导数,指数取相反数的情况,这一点并不难理解。

为了避免一次又一次将底数相乘,我们采用这样“偷懒”的策略,比如要计算 5185^{18},其实我们只要算出 595^9,然后再自己乘自己就好了,这样就可以避免做 99 次“×5\times 5” 的运算。(这种思想有点像“记忆化递归”。)

那么有一种机制就能帮助我们找到一个整数的合适的“分解”,那么就是将一个整数看成它的二进制形式。就那上面的例子来说,1818 的二进制表示为 (10010)2(10010)_2,即:

18=1×24+1×2118 = 1 \times 2^4 + 1\times2^1

那么:

518=524×5215^{18} = 5^{2^4} \times 5^{2^1}

于是,我们可以把指数 nn 做“二进制分解”,在底数不断自身乘以自身的过程中,将最终结果需要的部分保存下来

image.png

写得比较晦涩,相信聪明的你看我写的代码一定能看懂。

class Solution:
    def myPow(self, x: float, n: int) -> float:

        if n < 0:
            x = 1 / x
            n = -n

        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Last update: January 14, 2022 00:24
Contributors: liweiwei1419