原理介绍

快速幂的目的就是做到快速求幂，假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)。我们可以对指数b拆分：（1）如果b为偶数，那么a^b = (a^2)^(b/2);（2）如果b为奇数，那么a^b = a * (a^2)^(b-1)/2)；（3）如果b/2为偶数，那么a^b = ((a^2)*(a^2))^(b/4);（4）如果b/2为奇数，那么a^b = (a^2) *((a^2)*(a^2))^((b/2-1)/2);（5）如果b/4为偶数，那么a^b = ((a^4)*(a^4))^(b/8);（6）如果b/4为奇数，那么a^b = (a^2)*(a^4)*((a^4)*(a^4))^((b/4-1)/2);......在上面的（3）与（4）中，使用((a^2)*(a^2))表明a^4不是累乘四次a得到的，而是在a^2的基础上，做了一次乘法得到的，在（5）（6）的(a^4)*(a^4)也是同样的原理。如果b是2的幂次项，那么一直以上面这种方式，可以很快得到结果，不需要进行b次累乘。如果b不是2的幂次项，当发现其中的一个b/n不是偶数，那么就需要把这个阶段的a^n先乘出来。其实我们一直对b做除以2的运算，而>>可以实现除以二的功能，那么我们用二进制以及位运算来实现上述的过程。如果b/n为偶数，那么表示b/n的二进制表示中最后一位为0，那么不需要在结果上单独乘以一个a^n;若b/n为奇数，最后一位为1，那么就需要在结果上乘以一个a^n。现在举一个例子，比如b = 11二进制表示为(1011)，a^11 = a^(2^0+2^1+2^3)；11为奇数，那么需要先乘以一个a，即a^(2^0);11>>1 = 5为奇数，那么需要先乘以一个a^(2^1);5>>1 = 2为奇数，此时不需要乘以a^(2^2);2>>1 = 1为奇数，此时不需要乘以a^(2^3);

实战

以下为牛客网上的一道编程题，在这里我们作为例子练习以下

java实现

public class Solution { public double Power(double base, int exponent) { if(equal(base,0.0f)){ return 0.0f; } double result = 1.0f; boolean flag = true; if(exponent < 0){ exponent *= (-1); flag = false; } while(exponent != 0){ if((exponent & 1) == 1){ result *= base; } base = base *base; exponent >>= 1; } if(flag ==false){ result = 1/result; } return result; } //两个double类型数值是否相等，由于计算机无法精确表示小数，当两个double类型的数据的差值在规定的差值范围，即认为相等 public boolean equal(double num1,double num2){ if(num1 > num2){ } if((num1 >= num2 && num1 - num2 < 0.0000000001) || (num1 <= num2 && num2 - num1 < 0.0000000001)){ return true; } return false; } }

参考资料

快速幂讲解