快速计算功率(例如2 ^ 11)

Question

可能重复:
实现基于整数的幂函数pow(int,int)的最有效方法

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

例如2 ^ 13.

我记得在某个地方看到它与以下计算有关:

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

但我看不出如何计算等式右边的每个分量然后乘以它们会对我有所帮助.

有任何想法吗？

编辑:我的意思是任何基础.您在下面提到的算法,特别是"通过平方展示",如何改善运行时/复杂度？

Answer 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时间内计算.这是一种分而治之的算法.:-)正如其他人通过平方说取幂.

如果您将示例插入此中,您可以看到它的工作原理并与您给出的等式相关:

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

Answer 2

使用按位移位.防爆.1 << 11返回2 ^ 11.