快速计算幂（例如 2^11）[重复]

可能的重复：
实现基于整数的幂函数 pow(int, int) 的最有效方法 https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int

如何以更好的运行时间计算功率？

例如。 2^13。

我记得在某处看到过，它与以下计算有关：

2^13 = 2^8 * 2^4 * 2^1

但我不明白计算方程右侧的每个分量然后将它们相乘对我有什么帮助。

有任何想法吗？

编辑：我的意思是任何基础。您在下面提到的算法，特别是“平方求幂”如何提高运行时间/复杂性？

有一个通用的算法可以解决这个问题，但是在具有位移位的语言中，有一种更快的方法来计算 2 的幂。你只需输入1 << exp（假设你的位移运算符是<<因为大多数语言都支持该操作）。

我假设您正在寻找通用算法，并且只是选择了一个不幸的基础作为示例。我将用Python给出这个算法。

def intpow(base, exp):
   if exp == 0:
      return 1
   elif exp == 1:
      return base
   elif (exp & 1) != 0:
       return base * intpow(base * base, exp // 2)
   else:
       return intpow(base * base, exp // 2)

这基本上使得指数能够在 log2 exp 时间内计算出来。这是一种分而治之的算法。 :-) 正如其他人所说通过平方求幂 http://en.wikipedia.org/wiki/Exponentiation_by_squaring.

如果将示例插入其中，您可以看到它是如何工作的并且与您给出的方程相关：

intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8