学习参考自：https://www.cnblogs.com/wendelhuang/p/3414738.html
https://blog.csdn.net/u011590573/article/details/81457797
https://blog.csdn.net/wzb56_earl/article/details/7199343
对于快速幂求解问题不是很了解，所以特地学习下，记下自己的理解，当然可能理解有错误，欢迎指出来
(：逃 毕竟我也刚学会
快速幂
- 快速幂的目的就是做到快速求幂，假设我们要求 a，按照朴素算法就是把a连乘b次
- 这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)
⭐⭐网上的快速幂的理解：
- 快速幂为什么快？
- 因为十进制 8 要计算8次，二进制表示只要4位，只要计算4次
- 所以十进制 N 要计算N次，二进制表示只要logn位，因此只要logn次
- 要明确任何数字一定可以被化成二进制
- 如果求 a，设 a = 3 ， b = 13
- **b可以表示成二进制 1101**- **1101 **可以拆成 **二进制****（ 1000 + 100 + 00 + 1 ）= （ 8 + 4 + 0 +1 ）****十进制**- ** a = 3=3 ×3× 3 × 3[ ****四步出结果 ****]**
- 其实加快的部分就是temp_base临时保存的值
- **temp_base = a ，a，a，a，a** 的成倍递增- **temp_base*=temp_base 加快速度的关键，也是反复平方法命名的由来！**
- temp_result 根据二进制的位数值 0或1 来决定是否操作
- 遇到 0 ，不执行 ** temp_result*=temp_base **- 遇到 1 ， 执行** temp_result*=temp_base **
注： 二进制中的加法 [ a ] 对应实际操作的乘法 [ a×a×a ]**
🚩例子说明第一种代码：
举例 a说明快速幂求解过程：
初始化temp_result=1，temp_base=a;
Step1：从右向左看1101，利用if(b&1)来判断，式子成立说明b的最后一位是 1
- 做 **temp_result*=temp_base**（ result 数值 **a **）**---> ****[ 运算 result = 1 * a ]**
- 后** temp_base*=temp_base **（ base 数值 **a**），为第二次执行temp_result做准备。
- 然后利用 **b>>1 **，将**1101变成110**
Step2：从右向左看110，if(b&1)判断式子最后一位为0
- **temp_result 还是 a ( 0**未做操作 **)**
- **temp_base *=temp_base ** （ base 数值**a**）
- 然后利用 **b>>1 **，将**110变成11 **
Step3：从右向左看11，if(b&1)判断式子最后一位为1
- **temp_result*=temp_base ** （ result 数值 **a **）**---> ****[ 运算 result = a * a ]**
- **temp_base**自乘数值变为 **a**
- 然后利用** b>>1 **，将**11变成1**
Step4：从右向左看11，if(b&1)判断式子最后一位为1
- **temp_result*=temp_base **（ 数值 **a **）**---> ****[ 运算 result = a * a ]**** **
- **temp_base**自乘数值变为 **a**
- 然后利用** b>>1** ，将**1变成0 **
Output：temp_result = a [ 这样操作后发现，就是遍历二进制数是否为01，遍历次数和二进制数位数有关 ]
（temp_base不管值是否为01,，每次都要temp_base*=temp_base，时刻准备下一次被temp_result用到）
第一种实现代码是这个样子的：（一般网上的代码）右->左 的顺序，参考例子
int poww (int a , int b ) {
int temp_result = 1, temp_base;
while (b != 0) {//判断是否终止
if (b & 1 != 0) //判断二进制最后一位 0 1
temp_result *= temp_base;
temp_base *= temp_base; //自增时刻准备着 也是之所以称之为反复平方法的缘由。
b >>= 1; //右移操作
}
return temp_result ;
}
⭐算导的快速幂的理解：
- 要明确计算过程： a， a ， a ， a 方向从左向右看
- 要明确算导的方向和上面是不一样的，它是从左向右看
- 要明确 int b ， 4字节 32位，去除最高位符号位，剩下31位，要进行32次操作
- 需要理解 if (b & 1<<i) ，其实加个括号优先级可能会好理解 if (b &（1<<i）)
- 假设 i =2，用 **1****1****01 &（0****1****00）判断此时的第 i 位是 0 还是 1**🚩例子说明第二种代码：
还是举例 a说明快速幂求解过程：
初始化temp_result=1 b=13
其中 1101前面全是0，所有temp_result不管怎么反复平方还是1
0000000000000000000000000000**1101**
红色代表 i 的位置 蓝色代表还没判断的部分 ，黑色代表判断结束
至于反复平方原因就是：1101看的方向是左到右，1到11，二进制已经升了1位 例如：100(4)->1000(8)升了一位，二进制是2倍的差距，但是a^4和a^8是自乘的差距，这就是原因。 每次 i 移动都代表了升位的产生，所有要反复平方 < 以上都是我的个人理解可能有错误 >
Step1： 此时二进制 1101，temp_result=temp_result 自身平方一次，temp_result值为1
**if (b & 1<<i)判断为**1 *
- 所以**temp_result *= a**，**temp_result值为a ---> ****[ 运算 result = 1 * a ]**** **
Step2：此时二进制 1101，temp_result=temp_result 自身平方一次，temp_result值为a
** if (b & 1<<i)判断为**1*
- 所以**temp_result *= a，temp_result值为a****---> ****[ 运算 result = a * a ]**** **
Step3：此时二进制 1101，temp_result=temp_result 自身平方一次，temp_result值为a
** if (b & 1<<i)判断为**0*
- 所以temp_result值不变.
Step4：此时二进制 1101，temp_result=temp_result 自身平方一次，temp_result值为a
if (b & 1<<i)判断为**1*
- 所以**temp_result *= a，temp_result值为a---> ****[ 运算 result = a * a ]**** **
第二种实现是代码是这个样子的：（《算法导论》的实现）左->右 的顺序，参考例子
int poww(int a, int b) {
int temp_result = 1;
for (int i = 31; i>=0; i--) {
temp_result *= temp_result; //此处就是反复平方法的名字由来
if (b & 1<<i)
temp_result *= a;
}
return temp_result;
}
总结
反复平方法求幂运算的两个算法的比较：
方法一与方法二的比较：
方法二更好，因为M = M×C, 中的C是个常量，对与固定的C可以有些优化算法
（1）根据C的二进制形式计算M×C 的方法称之为 binary method
（2）加速binary算法可以先将C分解（factor），再利用 binary method，称之为（factor and binary method）
反复平方法求幂运算的应用：
1.模幂运算：**M =C mod N**<br /> 只需在原算法中的每步运算中，加上mod N 就可以解决<br /> 该算法可以用于RSA算法中。<br /> 利用Montgomery算法改写算法中求mod运算可以加速上述算法的执行。
若有收获，就点个赞吧
0 人点赞
