如何編寫時間複雜度爲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; 
}