自语之快速幂的使用

1,139 阅读3分钟

前言

昨天晚上,笔者下班后闲着没事,就开始了网上刷题之旅。

期间,恰好遇见了一道关于快速幂的问题。其实,在大学学习算法的时候,就曾了解过该算法。不过,当时码题的时候死活想不起来。

看来,笔者的题还没刷够!

快速幂能解决什么问题?

在重温快速幂的过程中,笔者搜索了很多博文,大部分的内容除了理论还是理论。其实,很多时候像这种不常用的小算法,我们只想知道该算法能解决什么问题,不想知道其底层原理和理论。

话不多说,我们看看这题:

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

这道题除了用循环叠乘和二分叠乘的方法外,快速幂在这种场景极其适用,即求一个数的N次幂。

那..如何使用快速幂?

这一部分内容, 笔者不讲快速幂的内容,只讲快速幂的使用和如何用代码实现。

我们来看个例子:计算3^5 (3的5次方)

上述例子可以拆解为:底数=3, 指数=5。快速幂的要点是,利用指数的二进制的位数进行叠乘运算。

什么?利用指数的二进制的位数进行叠乘运算!!!

没错,我们来看看,指数5的二进制形式为:0101。这里笔者是利用8421码算出其指数的二进制的….

得到指数的二进制码后, 我们从右向左看, 每前进一个位数, 底数就要翻倍(叠乘), 如图1-1。

企业微信20190810113152.png

从上图, 我们很容易得到:3 ^ 5 = 3 ^ 4 * 3 ^ 1

得到二进制码后,可以利用指数5和1的二进制数, 加上移位操作来判断当前二进制的末尾数是否为1, 如图1-2:

企业微信20190810115216.png

如果为1, 则说明当前二进制数是叠乘结果的组成部分之一。

从上文的8421码的表达式中:3 ^ 5 = 3 ^ 4 * 3 ^ 1可以得到:3 ^ 5的叠乘结果由3 ^ 43 ^ 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, 都需要进行翻倍操作!

总结

写到这里,关于快速幂算法,笔者也不知道读者们理解没有….

如果无法理解, 也没关系。

毕竟, 快速幂算法除了在码题的时候可能会遇到以外,其他时候有可能一辈子也用不到。