难度: Medium
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 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
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n 是一个整数x 不为零，要么 n > 0 。-104 <= xn <= 104运行时间: 36 ms
内存: 14.8 MB
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0.:
return 0.
if n < 0:
x = 1 / x
n = -n
ans = 1
while n != 0:
if n & 1 != 0:
ans *= x
x = x * x
n >>= 1
return ans
该题解使用快速幂算法，通过二分法将幂次 n 分解，每次将 n 除以2，同时将底数 x 平方，直到 n 为0。若 n 为奇数，则将当前答案乘以底数 x。最终得到 x 的 n 次幂结果。若 n 为负数，则先将 x 取倒数，同时将 n 取相反数，转化为正数的情况。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0.:
return 0.
if n < 0:
# 如果n为负数，将x取倒数，n取相反数
x = 1 / x
n = -n
ans = 1
while n != 0:
if n & 1 != 0: # 如果n的当前二进制位为1
ans *= x # 将当前答案乘以x
x = x * x # 将x平方
n >>= 1 # 将n除以2
return ans
快速幂算法通过每次对 n 进行二进制右移操作（即除以2），可以有效地减少计算量。每次右移都对应于将问题规模减半，因此算法的时间复杂度是对数级别的，即 O(log n)。这种方法使得每次只需处理当前的最低位，从而简化了幂次的处理，使算法既高效又易于实现。
当 n 为负数时，x 的 n 次幂实际上是 1/(x 的 |n| 次幂)。为了使用快速幂算法计算正幂次，我们将 x 取倒数，这样 x 的 -n 次幂就转化为了 (1/x) 的 n 次幂。随后将 n 取相反数，使其变为正数，这样可以利用相同的幂次计算过程。这种操作让算法能够统一处理正数和负数幂次的情况，保证了算法的正确性和通用性。
在快速幂算法中，每次处理 n 的最低位，并根据这一位是否为 1 来决定是否将当前的 x 值（已经平方了若干次的）乘入最终结果 ans 中。对于 n = 11，其二进制为 1011，算法会在 n 的每一位是 1 的时候乘以当前的 x 值。具体过程中，x 会不断平方，对应于 n 的每次右移，这样每个二进制位都对应一个 x 的幂次，确保了算法能够正确地累乘所有必要的 x 的幂次，从而得到正确的结果。
使用 `if n & 1 != 0` 来检查 n 的最低位是否为 1 是一种直接且效率较高的位操作方法，它直接对 n 的二进制表示的最低位进行检测。这一操作与检查 n 是否为奇数本质上是相同的，因为整数的奇偶性由其最低位的二进制决定。然而，使用位操作更直接地表达了这一逻辑，且在某些编程环境中可能比标准的奇偶性检查更快，因为它避免了任何额外的比较逻辑，只涉及基本的位运算。