Exponentiation By Squaring

我们都知道,一个数可以变成数个2的n次方之和,a=b+c,d^a = d^b × d^c,我们可以利用这两个性质快速计算一个数的n次幂。
在这之前,我们需要了解一下位运算。

位运算

逻辑右移与算数右移

X86关于右移提供了2种方法,逻辑右移 (Shift Logical Right)算数右移 (Shift Arithmetic Right),具体的硬件实现我们不在这里探讨,我们只探讨这两种右移有什么区别吧。

一句话说清楚,逻辑右移就是不考虑符号位,右移一位,左边补零即可;而算数右移考虑符号位,右移一位,左边用符号位填充。
而大部分编程语言使用的就是算数右移

快速幂

好了,但是我感觉这篇文章会成一篇大水文,因为这个算法很简单,下面开始介绍这种算法。
我们那8^23来举例子,23的二进制表达形式是10111,也就是1×2^0 + 1×2^1 + 1×2^2 + 0×2^3 + 1×2^4.
那么根据上面的a=b+c,d^a = d^b × d^c可以知道:
8^23 = 8^(1×2^0)×8^(1×2^1) × 8^(1×2^2) ×8^(0×2^3) × 8^(1×2^4)
把0的位删除,那么有:
8^23 = 8^(2^0) ×8^(2^1) ×8^(2^2) × 8^(2^4)
那么位运算有什么用呢??
我们知道,a & 1可以取出a的二进制表达形式下的最低位,而a >>= 1又可以舍弃掉a的二进制表达形式下的最低位。
用这样的方法就可以反着遍历a的二进制表达形式了,而我们需要的也正是这个。
那2次方怎么计算呢???很简单,我们有个简单的数学方法,a^(2^i) = (a^(2^(i-1)))^2
8^(2^1) = (8^(2^0))^2
8^(2^2) = (8^(2^1))^2

C语言实现:

int pow(int a, int b) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1)
ans = (long long) ans * a;
a = a * a;
}
return ans;
}

这里需要注意,一个整形乘以一个整形,结果只会存在2个整形最大的那个。
比如32位二进制乘以32位二进制,结果只会保存在32位下,而有时候32位保存不了。。
所以要 (long long)!!!

© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发

请登录后发表评论