1.通过递归实现快速幂运算：

int power(int a, int n)
{
	int ans;
	if (n == 0)//结束条件
		ans = 1;
	else
	{
		ans = power(a * a, n / 2);//递归调用
		if (n % 2 == 1)//若 n 为奇数，ans 需再乘一个 a。
			ans *= a;
	}
	return ans;
}

注：书写递归时需要先写特殊情况（出口）。

2.通过循环实现快速幂运算：

int power(int a, int n)
{
	int ans = 1;
	while (n)//当 n 不为 0 时
	{
		if (n % 2)//若 n 为奇数
			ans *= a;
		a = a * a;//底数平方
		n /= 2;//指数减半
	}
	return ans;
}

3.算法竞赛中，几乎所有的快速幂在运算时，所有的乘法都要取模。如：

int power(int a, int n)
{
	int ans = 1;
	while (n)//当 n 不为 0 时
	{
		if (n % 2)//若 n 为奇数
			ans = ans * a % MOD;
		a = a * a % MOD;//底数平方
		n /= 2;//指数减半
	}
	return ans;
}

4.快速幂运算的时间复杂度为O（logN）.