[C Programming] 數值自乘非遞迴解

續求m^n問題(m與n是正整數)。前面的提示會得到一個遞迴的程式，
請發展一個非遞迴，但效率相同的程式。

答：
我們先以求m^45為例，45的二進位為101101，
所以m^45 = m^(1*2^5 + 0*2^4 +1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)
我們可以用一個tmp來記錄從最低位算到最高位的值，
先令tmp=1, 當碰到這個位數是1時，就乘上m，
每次位數檢查完以後都讓m自乘，
顯然剛好m -> m^2 -> m^4 -> m^8 ->...，
會符合每一位所代表其為m的正確的次方數。
每次檢查完以後，我們就將n的尾數丟棄(n>>=1)，
記錄到最後n==0時，就離開迴圈輸出值。

Code：

#include <stdio.h>
#include <stdlib.h>

unsigned long iterative_power(unsigned long m, unsigned long n)
{
 unsigned long temp = 1;
 while(n > 0)
 {
  if ( n & 0x01UL == 1) // last bit is 1
   temp *= m;
  m *= m;      // m -> m^2 -> m^4 -> m^8 ......
  n >>= 1;     // throw the last bit
 }
 return temp;
}

int main(int argc, char *argv[])
{ 
 unsigned long m, n;
 m = 4;
 n = 13;
 printf("\n%ld^%ld = %ld\n",m , n, iterative_power(m,n));
 system("PAUSE");
 return 0;
}