【LeetCode】50. Pow(x, n)

1 问题

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，$x^n$ ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

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

2 答案

自己写的超出时间限制

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        res = 1
        for _ in range(abs(n)):
            res *= x
        return res if n > 0 else 1/res
1
2
3
4
5
6
7
8

官方解，利用二进制转十进制

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0: 
            return 0.0
        res = 1
        if n < 0:
            x, n = 1/x, -n
        while n:
            if n & 1:  # 按位与，即 n % 2 == 1
                res *= x
            x *= x  
            n >>= 1  # 即 n % 2 == 1
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13

对于任何十进制正整数 $n$，设其二进制为 $b^m...b^3{b}^2{b}^1$（$b^i$为二进制某位值，$i\in [1,m]$），则有：

• 二进制转十进制：$n=1b_1+2b_2+4b_3+\dots +2^{m-1}{b}_m$ （即二进制转十进制公式）
• 幂的二进制展开：$x^n=x^{1b_1+2b_2+4b_3+\dots +2^{m-1}{b}_m}=x^{1b_1}{x}^{2b_2}{x}^{4b_3}\dots x^{2^{m-1}{b}_m}$