快速幂

数学与数论

说明

按二进制位决定是否乘入当前底数；时间 O(log exponent)。

分析

把指数写成二进制：某一位为 1 时，把当前底数乘入答案；每轮底数平方、指数右移。这样只需对数次乘法。

图解推演

10 的二进制是 1010，故 2¹⁰=2⁸×2²。逐位处理时底数依次为 2、4、16、256，只有指数位为 1 才累乘。指数为 0 时返回乘法单位元 1；每轮平方也可能溢出，不能只检查最终答案。

查看图表代码

适用前提与边界

示例处理非负整数指数且使用普通 int，负指数或溢出风险需要另行处理。

示例输入与调用

fmt.Println(Power(2, 10))

运行输出

1024

完整 Go 示例

package main

import "fmt"

func Power(base, exponent int) int {
	result := 1
	for exponent > 0 {
		if exponent&1 == 1 {
			result *= base
		}
		base *= base
		exponent >>= 1
	}
	return result
}

func main() {
	fmt.Println(Power(2, 10))
}