Golang实现快速求幂的方法详解

对于一个Golang开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《Golang实现快速求幂的方法详解》，主要介绍了求幂，希望对大家的知识积累有所帮助，快点收藏起来吧，否则需要时就找不到了！

今天讲个有趣的算法：如何快速求n^m，其中n和m都是整数。

为方便起见，此处假设m>=0，对于m|m|后再取倒数即可。

另外此处暂不考虑结果越界的情况（超过 int64 范围）。

当然不能用编程语言的内置函数，我们只能用加减乘除来实现。

n的m次方的数学含义是：m个n相乘：n*n*n...*n，也就是说最简单的方式是执行 m 次乘法。

直接用乘法实现的问题是性能不高，其时间复杂度是 O(m)，比如 3²⁹要执行29次乘法，而乘法运算是相对比较重的，我们看看能否采用什么方法将时间复杂度降低。

设m = x + y + z（x、y、z 都是整数），我们知道有如下数学等式： n^m= n^x+y+z = n^x∗n^y∗n^z。

也就是说，如果我们已经知道 n^x、n^y、n^z的值，是不是就可以直接用他们相乘得出 n^m的结果？这样的话乘的次数就大大降低了。

于是问题就变成应该将 m 拆成怎样的几个数的和。

因为计算机是玩二进制的，我们尝试着将这些数跟 2 扯上联系（以 2 为底），看看会不会有奇迹发生。

我们看看具体的例子：3²⁹。

我们将29做这样的拆分：29 = 16 + 8 + 4 + 1。

这个拆分有什么特点呢？右边的数都是 2 的 X 次方（2⁴+2³+2²+2⁰）。

我们把上面的拆分带进公式：3²⁹=3¹⁶∗3⁸∗3⁴∗3¹。

那我们能不能知道 3¹⁶、3⁸、3⁴、3¹是什么呢？

我们不用计算就知道3¹是什么——但仅此而已。

不过我们可以用 3¹自乘 4 次的到3⁴；然后再用 3_⁴自乘得到3⁸；再通过3⁸自乘得到3¹⁶。

好像有点感觉了——我们每做一次乘法，就能将结果翻倍（如 3⁴自乘就变成 3⁴∗3⁴=3⁸）。

如此，虽然也要多次乘法，但乘的次数从29次降到9次！

然后我们再回头看看上面的拆分：

29 =16+8+4+1=2⁴+2³+2²+2⁰= 1∗2⁴+1∗2³+1∗2²+0∗2¹+1∗2⁰。

这不就是学校学的二进制转十进制吗（29 的二进制是 11101）？

3²⁹=3¹⁶∗3⁸∗3⁴∗3¹是说：取 29 的二进制表示中所有值是 1 的位，算出它们的指数值并相乘就得到最终的值。

我们用 go 语言实现一下：

// 求 a 的 n 次方
// a、n 是非负整数
func Pow(a,n int64) int64 {
	// 0 的任何次方都是 0
	if a == 0 {
		return 0
	}
	
	// 任何数的 0 次方都是 1
	if n == 0 {
		return 1
	}

	// 1 次方是它自身
	if n == 1 {
		return a
	}

	// 用滚雪球的方式计算幂
	// 雪球初始值是 1
	var result int64 = 1
	// 滚动因子初始化为 a 的 1 次方（a 自身）
	factor := a
	// 循环处理直到 n 变成 0（所有的二进制位都处理完了）
	for n != 0 {
		// 跟 1 做与运算，判断当前要处理的位是不是 1
		// 之所以是直接跟 1 做与运算，因为后面每处理一轮都将 n 右移了一位，保证每次要处理的位都在最低位
		if n & 1 != 0 {
			// 当前位是 1，需要乘进去
			result *= factor
		}
		// 每轮结束时将滚动因子自乘
		// 因为每行进一轮，指数都翻倍，整体结果就是自乘
		// 比如本轮因子是 2**4，下一轮就是 2**8
		// 2**8 = 2**(4+4) = 2**4 * 2**4
		// （** 表示指数）
		factor *= factor
		// n 右移一位，将下一轮要处理的位放在最低位
		n = n >> 1
	}
	
	return result
}

有什么用呢

很多语言内置的 pow 函数都只接受浮点数，浮点数的运算是非常重的，如果我们的程序需要频繁计算整数的幂，就可以采用 quick pow 算法代替语言内置的幂函数以提升性能。

我们对 go 语言内置的 math.Pow 和 quick pow 算法做个性能测试对比一下。

// 测试 3 的 29 次方的性能测试
var benchPowB int64 = 3
var benchPowP int64 = 29

// 上面的 quick pow 算法
func BenchmarkQuickPow(b *testing.B)  {
	for i := 0; i 
<p>测试结果：</p>
<blockquote><p>goos: darwin<br>goarch: amd64<br>cpu: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz<br>BenchmarkQuickPow-8           357897716                3.373 ns/op<br>BenchmarkInnerPow-8           39162492                29.30 ns/op<br>BenchmarkSimpleMulti-8          121066731                9.549 ns/op<br>PASS<br>ok      command-line-arguments  4.894s</p></blockquote>
<p>从性能测试结果看，quick pow 算法比简单乘法快了好几倍，比 math.pow 快了近 10 倍。</p>
<p>所以，如果程序只需要求整数幂，而且能确保计算结果不会越界时，可以考虑使用 quick pow 算法代替语言内置的浮点函数。</p>
<p>到这里，我们也就讲完了《Golang实现快速求幂的方法详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！</p>