快速幂和乘法

本文介绍两种快速幂算法和一种快速乘法算法的 C 实现。

普通幂

逐次连乘，时间复杂度 O(n)：

unsigned long long   pow1(int x, int n)
{
	unsigned long long  r = 1;
	while (n--)r *= x;
	return r;
}

二分快速幂

利用二进制分解指数，每轮将底数平方并右移指数，时间复杂度 O(log n)：

//二分快速幂
unsigned long long   pow2(int x, int n)
{
	unsigned long long  r = 1, base = x;
	while (n)
	{
		if (n & 1)r *= base; // 如果是奇数
		base *= base;
		n >>= 1;
	}
	return r;


}

二分快速乘法

与快速幂思路相同，将乘法转化为加法，每轮将加数翻倍并右移乘数：

//二分快速乘法
unsigned long long   mult(int x, int n)
{
	unsigned long long  r = 0, base = x;
	while (n)
	{
		if (n & 1)r += base;
		cout <<n<<"        " << (n&1)<<"     "<< base<<"      "<<r << endl;
		base += base;
		n >>= 1;
	}
	return r;


}