目标
实现 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/2^2 = 1/4 = 0.25说明：
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31-1
- n 是一个整数
- 要么 x 不为零，要么 n > 0 。
- -10^4 <= x^n <= 10^4
思路
通常求 x^n 最直接的算法是迭代相乘，时间复杂度为 O(n)。但是当 n 超过 10^6 就需要考虑 O(logn) 的算法了。
快速幂的核心思想是根据幂次 power 的二进制表示来确定 对应的指数 是否需要计入结果。
比如 2^13， 幂次 13 的二进制表示为 1101，而 2^13 = 2^1 * 2^4 * 2^8，其中 1、4、8 刚好对应幂次的二进制表示中bit为 1 所代表的数字。我们可以循环将幂右移 1 位，直到幂为 0，并在循环中累计 base = base * base，当相应 bit 位为 1 时将 base 计入结果即可。
代码
/**
* @date 2024-08-16 10:19
*/
public class MyPow50 {
public double myPow(double x, int n) {
long cnt = n >= 0 ? n : -((long) n);
double res = 1.0;
while (cnt > 0) {
if ((cnt & 1) == 1) {
res = res * x;
}
x = x * x;
cnt = cnt >> 1;
}
return n == 0 ? 1 : n > 0 ? res : 1 / res;
}
}
性能
