今天講個(gè)有趣的算法：如何快速求n^m，其中n和m都是整數(shù)。

為方便起見，此處假設(shè)m>=0，對于m< 0的情況，求出n^|m|后再取倒數(shù)即可。

另外此處暫不考慮結(jié)果越界的情況（超過 int64 范圍）。

當(dāng)然不能用編程語言的內(nèi)置函數(shù)，我們只能用加減乘除來實(shí)現(xiàn)。

n的m次方的數(shù)學(xué)含義是：m個(gè)n相乘：n*n*n...*n，也就是說最簡單的方式是執(zhí)行 m 次乘法。

直接用乘法實(shí)現(xiàn)的問題是性能不高，其時(shí)間復(fù)雜度是 O(m)，比如?3²⁹要執(zhí)行29次乘法，而乘法運(yùn)算是相對比較重的，我們看看能否采用什么方法將時(shí)間復(fù)雜度降低。

設(shè)m = x + y + z（x、y、z 都是整數(shù)），我們知道有如下數(shù)學(xué)等式：?n^m=?n^x+y+z?=?n^x?n^y?n^z。

也就是說，如果我們已經(jīng)知道?n^x、n^y、n^z的值，是不是就可以直接用他們相乘得出?n^m的結(jié)果？這樣的話乘的次數(shù)就大大降低了。

于是問題就變成應(yīng)該將 m 拆成怎樣的幾個(gè)數(shù)的和。

因?yàn)橛?jì)算機(jī)是玩二進(jìn)制的，我們嘗試著將這些數(shù)跟 2 扯上聯(lián)系（以 2 為底），看看會(huì)不會(huì)有奇跡發(fā)生。

我們看看具體的例子：3²⁹。

我們將29做這樣的拆分：29 = 16 + 8 + 4 + 1。

這個(gè)拆分有什么特點(diǎn)呢？右邊的數(shù)都是 2 的 X 次方（2⁴+2³+2²+2⁰）。

我們把上面的拆分帶進(jìn)公式：3²⁹=3¹⁶?3⁸?3⁴?3¹。

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

我們不用計(jì)算就知道3¹是什么——但僅此而已。

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

好像有點(diǎn)感覺了——我們每做一次乘法，就能將結(jié)果翻倍（如?3⁴自乘就變成?3⁴?3⁴=3⁸）。

如此，雖然也要多次乘法，但乘的次數(shù)從29次降到9次！

然后我們再回頭看看上面的拆分：

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

這不就是學(xué)校學(xué)的二進(jìn)制轉(zhuǎn)十進(jìn)制嗎（29 的二進(jìn)制是 11101）？

3²⁹=3¹⁶?3⁸?3⁴?3¹是說：取 29 的二進(jìn)制表示中所有值是 1 的位，算出它們的指數(shù)值并相乘就得到最終的值。

我們用 go 語言實(shí)現(xiàn)一下：

// 求 a 的 n 次方
// a、n 是非負(fù)整數(shù)
func Pow(a,n int64) int64 {
	// 0 的任何次方都是 0
	if a == 0 {
		return 0
	}
	
	// 任何數(shù)的 0 次方都是 1
	if n == 0 {
		return 1
	}

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

	// 用滾雪球的方式計(jì)算冪
	// 雪球初始值是 1
	var result int64 = 1
	// 滾動(dòng)因子初始化為 a 的 1 次方（a 自身）
	factor := a
	// 循環(huán)處理直到 n 變成 0（所有的二進(jìn)制位都處理完了）
	for n != 0 {
		// 跟 1 做與運(yùn)算，判斷當(dāng)前要處理的位是不是 1
		// 之所以是直接跟 1 做與運(yùn)算，因?yàn)楹竺婷刻幚硪惠喍紝?n 右移了一位，保證每次要處理的位都在最低位
		if n & 1 != 0 {
			// 當(dāng)前位是 1，需要乘進(jìn)去
			result *= factor
		}
		// 每輪結(jié)束時(shí)將滾動(dòng)因子自乘
		// 因?yàn)槊啃羞M(jìn)一輪，指數(shù)都翻倍，整體結(jié)果就是自乘
		// 比如本輪因子是 2**4，下一輪就是 2**8
		// 2**8 = 2**(4+4) = 2**4 * 2**4
		// （** 表示指數(shù)）
		factor *= factor
		// n 右移一位，將下一輪要處理的位放在最低位
		n = n >> 1
	}
	
	return result
}

有什么用呢

很多語言內(nèi)置的 pow 函數(shù)都只接受浮點(diǎn)數(shù)，浮點(diǎn)數(shù)的運(yùn)算是非常重的，如果我們的程序需要頻繁計(jì)算整數(shù)的冪，就可以采用 quick pow 算法代替語言內(nèi)置的冪函數(shù)以提升性能。

我們對 go 語言內(nèi)置的 math.Pow 和 quick pow 算法做個(gè)性能測試對比一下。

// 測試 3 的 29 次方的性能測試
var benchPowB int64 = 3
var benchPowP int64 = 29

// 上面的 quick pow 算法
func BenchmarkQuickPow(b *testing.B)  {
	for i := 0; i < b.N; i++ {
		algo.Pow(benchPowB, benchPowP)
	}
}

// go 語言 math 包的 Pow 方法，只接受 float64 類型
func BenchmarkInnerPow(b *testing.B)  {
	x := float64(benchPowB)
	y := float64(benchPowP)
	for i := 0; i < b.N; i++ {
		math.Pow(x, y)
	}
}

// 用簡單乘法實(shí)現(xiàn)（3 自乘 29 次）
func BenchmarkSimpleMulti(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var r int64 = 1
		var j int64 = 0
		for ; j < benchPowP; j++ {
			r *= benchPowB
		}
	}
}

測試結(jié)果：

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
BenchmarkQuickPow-8 ? ? ? ? ? 357897716 ? ? ? ? ? ? ? ?3.373 ns/op
BenchmarkInnerPow-8 ? ? ? ? ? 39162492 ? ? ? ? ? ? ? ?29.30 ns/op
BenchmarkSimpleMulti-8 ? ? ? ? ?121066731 ? ? ? ? ? ? ? ?9.549 ns/op
PASS
ok ? ? ?command-line-arguments ?4.894s

從性能測試結(jié)果看，quick pow 算法比簡單乘法快了好幾倍，比 math.pow 快了近 10 倍。

所以，如果程序只需要求整數(shù)冪，而且能確保計(jì)算結(jié)果不會(huì)越界時(shí)，可以考慮使用 quick pow 算法代替語言內(nèi)置的浮點(diǎn)函數(shù)。