stl当中的power函数

今天之所以要连在昨天之后紧跟一篇，是因为昨天更新完之后，看了这个函数的源代码，瞬间觉得自己弱爆了，不废话，先贴代码：

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次方~
拜服了~~~