快速幂

昨天来大学报道了，很期待将来的学习生活。

在刷学校OJ新生题时刷到几题要用幂运算（虽然都是二次幂三次幂），正好复习一下快速幂这个算法。

朴素做法

按照定义，要多少次幂就乘以多少次数字呗。

1
2
3
4
5
6

long long myPow(int x, int n)
{
  long long ans = 1;
  for (int i = 1; i <= n; ++i) ans *= n;
  return ans;
}

递归做法

很容易能发现，有些中间步骤其实我们已经计算过了，就不需要再计算了。

例如:

$2^6$ 可以被拆成$2^3 * 2^3$，$2^3可以拆成2^2 * 2$，$2^2$可以拆成$2 * 2$。

这样只需要计算$2^2$和$2^3$的值是多少就行了。

不再需要乘以6下才能得到结果。

1
2
3
4
5
6
7

long long myPow(int x, int n)
{
  if (!n) return 1;
  if (n & 1) return myPow(x, n - 1) * x;
  long long temp = myPow(x, n / 2); //定义temp减少计算次数
  return temp * temp;
}

循环做法

递归的话会占用额外的栈空间，还可以优化一下不使用递归来进行操作。

这又涉及到一点点二进制的知识了。

例如：

$2^{10}$把它的指数用二进制表示就是BIN(1010)。

所以可以把$2^{BIN(1010)}$变成$2^{BIN(1000)} * 2^{BIN(10)}$。

这样就可以大大节省运算次数了。

1
2
3
4
5
6
7
8
9
10

long long myPow(int x, int n)
{
	int ans = 1;
	while (n) {
		if (n & 1) ans *= x;  //遇到1了，把当前结果乘进ans里
		x *= x;
		n >>= 1;  //n的二进制右移一位
	}
	return ans;
}