不能理解在这个快速求幂代码中采用的方法？
不能理解在这个快速求幂代码中采用的方法？
提问于 2017-03-18 22:00:08
我偶然发现了以下用于快速求幂的代码片段。我可以看到它可以正确地工作，但我不理解作者用来如此简洁地编写它的逻辑。我确实知道快速求幂的概念和人们为它找到的递归使用分治的通用代码。尽管下面的代码片段必须做到这一点，但我不能理解作者用什么逻辑来编写它。
有没有人能解释一下？
int fastExp(int base, int exponent ) {
int b = 1, a = base;
while(exponent > 0) {
if(exponent%2) {
b = b * a;
}
exponent /= 2;
a = a * a;
}
return b;
}回答 1
Stack Overflow用户
发布于 2017-03-18 22:35:56
例如，2^10
FIRST RUN
a = base
a = 2
if (exp(10) % 0)
do nothing
exponent /= 2
exponent = 10/2
exponent = 5
a = a * a
a = 2 * 2
a = 4
since exponent > 0, do another run
SECOND RUN
a = 4
if(exp(5) % 1)
b = b * a
b = 1 * 4
b = 4
exponent /= 2
exponent = 5/2
exponent = 2
a = a * a
a = 4 * 4
a = 16
since exponent > 0, do another run
THIRD RUN
a = 16
if(exp(2) % 2)
b = 4
do nothing here
exponent /= 2
exponent = 2/2
exponent = 1
a = 16 * 16
a = 256
since exponent > 0, do another run
FOURTH RUN
a = 256
if(exp(1) % 2)
b = b * a
b = 4 * 256
b = 1024
exponent =/ 2
exponent = 1/2
exponent = 0
a = a * a
a = 254 * 254
b = 1024
since exponent is now 0,
return b希望这能回答你的问题！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42875314
复制相关文章
相似问题
腾讯云开发者
