快速计算幂(例如2^11)
快速计算幂(例如2^11)
提问于 2010-02-04 08:07:15
如何用更好的运行时来计算功率？
例如2^13。
我记得在某个地方看到它与以下计算有关：
2^13 = 2^8 * 2^4 * 2^1
但我看不出计算方程右边的每个分量，然后再乘以它们对我有多大帮助。
有什么想法吗？
编辑:我指的是任何一个基地。下面提到的算法，特别是“通过平方进行扩展”，如何提高运行时/复杂性？
回答 6
Stack Overflow用户
回答已采纳
发布于 2010-02-04 08:08:51
这有一个通用的算法，但是在有位移位的语言中，有一种计算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^8Stack Overflow用户
发布于 2010-02-04 08:11:44
使用按位移位。例如。1 << 11返回2^11。
Stack Overflow用户
发布于 2010-02-04 08:09:36
二的力量是容易的。在二进制中，2^13是一个1，后面跟着13个零。
您可以使用位移位，它是许多语言中内置的运算符。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2198138
复制相关文章
相似问题
腾讯云开发者
