今天之所以要连在昨天之后紧跟一篇,是因为昨天更新完之后,看了这个函数的源代码,瞬间觉得自己弱爆了,不废话,先贴代码:
-
template <class T, class Integer, class MonoidOperation>
-
T power(T x, Integer n, MonoidOperation op) {
-
if (n == 0)
-
return identity_element(op);
-
else {
-
while ((n & 1) == 0) {
-
n >>= 1;
-
x = op(x, x);
-
}
-
-
T result = x;
-
n >>= 1;
-
while (n != 0) {
-
x = op(x, x);
-
if ((n & 1) != 0)
-
result = op(result, x);
-
n >>= 1;
-
}
-
return result;
-
}
-
}
说实话,我之前在应届生去面试的时候,就被人问过这道题目,怎么算x的y次方,当时想的是分奇数和偶数递归,但是知道昨天拷到这个,瞬间明朗了。。。
第一步判断n是否为0;
第一个while循环,尽可能的将底数变的更大,更好进行后续的计算,经过第一个while之后,n肯定是一个奇数了,再进入第二个循环,如果是1,则直接返回。
第二个while循环感觉就是求当前底数(x的偶数次平方,y)的奇数(m)次平方的过程,也就是求m的二进制各个位是否为1的过程,如果当前位M为1,则结果额外乘以y的2^M次方~
拜服了~~~
阅读(2620) | 评论(0) | 转发(0) |