简介
快速幂就是快速计算底数 x 的 n 次幂，使其时间复杂度为 O(logN)，这与朴素的 O(n) 相比有了极大的提高。
快速幂的核心思想就是每一步把指数分成两半，而相应的底数做平方运算，即 526 = 516+8+2 = 516 * 58 * 52
模板
1
2
3
4
5
6
7
8
9
10
|
public long quickPow(int x, int n) {
long res = 1;
while (n != 0) {
if ((n & 1) == 1) {
res *= x;
}
x *= x;
n >>= 1;
}
}
|
例子
LC 剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
输入：x = 2.00000, n = 10
输出：1024.00000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public double myPow(double x, int n) {
if (x == 0)
return 0;
long b = n;
if (n < 0){
x = 1 / x;
b = -b;
}
double res = 1.0;
while (b > 0){
if ((b & 1) == 1)
res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
|