如何编写时间复杂度为O(log n)的计算m ^ n的迭代版本？

Question

如果我有两个整数m和n,我必须来计算power(m,n),即米^ñ,然后我写了下面的递归代码,这给时间复杂度为O(log n)的,但我不能写它的迭代版本,它提供了类似的时间复杂.

int power(int m, int n) {
    int p;
    if (n == 1)
        return m;
    p = power(m, n / 2);
    if (n % 2 == 1) 
        return p * p * m;
    else
        return p * p;
}

Answer 1

如果毫厘n是1,m乘到结果.
如果第二个最小位n是1,m*m则乘以结果.
如果第三个最小位n是1,(m*m)*(m*m)则乘以结果.

重复这一点,代码应该是这样的:

int power(int m, int n)
{
    int res = 1;
    while (n > 0) /* check all bit which is 1 */
    {
        if (n % 2 == 1) res *= m; /* check current bit */
        m *= m; /* calculate what to multiply if next bit is 1 */
        n >>= 1; /* proceed to next bit */
    }
    return res;
}