前言

这个算法是很久很久之前我学习的,最近在Luogu看到了一题矩阵加速递推的斐波那契数列居然是绿题...

正文

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

位运算

逻辑右移与算数右移

X86关于右移提供了2种方法,逻辑右移 (Shift Logical Right)算数右移 (Shift Arithmetic Right),具体的硬件实现我们不在这里探讨,我们只探讨这两种右移有什么区别吧。
一句话说清楚,逻辑右移就是不考虑符号位,右移一位,左边补零即可;而算数右移考虑符号位,右移一位,左边用符号位填充。
而大部分编程语言使用的就是算数右移

与或非

与门的真值表
1 & 1 = 1
0 & 1 = 0
1 & 0 = 0
0 & 0 = 0
或门的真值表
1 & 1 = 1
0 & 1 = 1
1 & 0 = 1
0 & 0 = 0
非门的真值表
!0 = 1
!1 = 0

快速幂

好了,但是我感觉这篇文章会成一篇大水文,因为这个算法很简单,下面开始介绍这种算法。
我们那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)!!!