前言
昨天晚上,笔者下班后闲着没事,就开始了网上刷题之旅。
期间,恰好遇见了一道关于快速幂的问题。其实,在大学学习算法的时候,就曾了解过该算法。不过,当时码题的时候死活想不起来。
看来,笔者的题还没刷够!
快速幂能解决什么问题?
在重温快速幂的过程中,笔者搜索了很多博文,大部分的内容除了理论还是理论。其实,很多时候像这种不常用的小算法,我们只想知道该算法能解决什么问题,不想知道其底层原理和理论。
话不多说,我们看看这题:
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
这道题除了用循环叠乘和二分叠乘的方法外,快速幂在这种场景极其适用,即求一个数的N次幂。
那..如何使用快速幂?
这一部分内容, 笔者不讲快速幂的内容,只讲快速幂的使用和如何用代码实现。
我们来看个例子:计算3^5
(3的5次方)
上述例子可以拆解为:底数=3
, 指数=5
。快速幂的要点是,利用指数的二进制的位数进行叠乘运算。
什么?利用指数的二进制的位数进行叠乘运算!!!
没错,我们来看看,指数5的二进制形式为:0101
。这里笔者是利用8421码算出其指数的二进制的….
得到指数的二进制码后, 我们从右向左看, 每前进一个位数, 底数就要翻倍(叠乘), 如图1-1。
从上图, 我们很容易得到:3 ^ 5 = 3 ^ 4 * 3 ^ 1
得到二进制码后,可以利用指数5和1的二进制数, 加上移位操作来判断当前二进制的末尾数是否为1, 如图1-2:
如果为1, 则说明当前二进制数是叠乘结果的组成部分之一。
从上文的8421码的表达式中:3 ^ 5 = 3 ^ 4 * 3 ^ 1
可以得到:3 ^ 5
的叠乘结果由3 ^ 4
和 3 ^ 1
组成。
我们可以很快的写出代码, 核心代码主要是计算3 ^ 4 和3 ^ 1
的结果, 如下:
// result = 叠乘结果
// base = 底数
// exponent = 指数
double result = 1, cur = base;
while (exponent != 0) {
if ((exponent & 1) == 1) { // 计算叠乘结果
result *= cur;
}
cur *= cur; // 翻倍(1-1)
exponent >>= 1; // 指数右移一位
}
代码中, 翻倍(1-1)操作是根据指数的二进制码中, 我们从右向左看, 每前进一个位数, 底数就要翻倍的原理。
而且, 在翻倍操作中, 不管末尾&操作(图1-2)的结果是否为1, 都需要进行翻倍操作!
总结
写到这里,关于快速幂算法,笔者也不知道读者们理解没有….
如果无法理解, 也没关系。
毕竟, 快速幂算法除了在码题的时候可能会遇到以外,其他时候有可能一辈子也用不到。