扩展算法：
快速幂算法：
快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高（为O(指数n)），就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
算法讲解：
比如说一道ACM算法题： 求 A^B的最后三位数表示的整数
- 解法一： 很简单啊，先求出该数然后对1000求余就得到了结果
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public long normalPower(long base,long power){
long result = 1;
for(int i=1;i<=power;i++){
result = result*base;
}
return result%1000;
}
|
看起来没有问题，但是输入测试用例(2 ,100) ，发现结果为0。为什么呢？
首先Java 中的数据表示是有一定的范围的，比如说int(-2147483648,+2147483648)，long 的范围相应更大。但是题目中2^100它的数值已经远远大于了long表示的范围。如果一个数已经无法表示，那么相应它与1000的余数就更不用说求出来了。
“取模”运算的规则：
1
2
3
4
5
| (a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
|
第三条，两个数乘积的取模 = 各个因子分别取模然后乘起来综合取模。 相应的代码变换成这个样子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public long normalPower(long base,long power){
long result = 1;
for(int i=1;i<=power;i++){
result = result*base;
result = result%1000;
}
return result%1000;
}
|
解法三：解法二已经能够解决问题，但是速度太慢，如果我要求 2^10000000000，那么循环就需要执行10000000000次，这显然不合理。因此考虑降低计算循环的次数。
快速幂法入门：快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高（为O(指数n)），就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
1
2
3
4
5
| 3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3) //循环10次
3^10=(3*3)^5 //循环5次
3^10=9^5 //循环1次
|
可以看出，通过对指数进行折半，底数翻倍 的操作能够很大程度上降低循环的次数。如果说指数不是一个偶数，那么可以将它转化为偶数次幂乘以本身，将单独的一个提取出来先进行和结果的乘法操作。代码可以修改为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public long normalPower(long base,long power){
long result = 1;
while(power>0){
if(power%2==0){
power=power/2;
base=base*base%1000;
}
else{
result=result*base%1000;
power=power-1;
power=power/2;
base=base*base%1000;
}
}
return result%1000;
}
|
- 解法四： 上面的解法三已经有了快速幂算法的味道了，接下来我们需要对代码中的重复部分进行提取优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public long normalPower(long base,long power){
long result = 1;
while(power>0){
if(power%2==1){
result=result*base%1000;
}
power=power/2;
base=base*base%1000;
}
return result%1000;
}
|
- 解法五：终极优化 power%2==1 的求余运算可以用位运算来代替。例如：power&1。因为如果power为偶数，则其二进制表示的最后一位一定是0；如果power是奇数，则其二进制表示的最后一位一定是1。将他们分别与1的二进制做“与”运算，得到的就是power二进制最后一位的数字了，是0则为偶数，是1则为奇数。例如5是奇数，则5&1=1；而6是偶数，则6&1=0；因此奇偶数的判断就可以用“位运算”来替换了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| /**
* 普通的求幂函数
* @param base 底数
* @param power 指数
* @return 求幂结果的最后3位数表示的整数
*/
public long normalPower(long base,long power){
long result = 1;
while(power>0){
if((power&1)==0){
//指数为奇数，先进行乘法操作将其转化为偶数
result=result*base%1000;
}
power=power/2;
base=base*base%1000;
}
return result%1000;
}
|
回到这一题，直接通过快速幂算法进行求解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public double myPow(double x, int n) {
if(x==0)
return 0;
long b = n;
if(b<0){
x=1/x;
b=-b;
}
double res = 1;
while(b>0){
if((b&1)==1){
res = res*x;
}
x= x*x;
b>>=1;
}
return res;
}
}
|