[C Programming] 數值自乘非遞迴解-延伸1

請參見數值自乘非遞迴解。
*1. 這個程式的乘法數目還可以再降低，
     其實我們保持完整的m, m^2, m^4, m^8, ...是沒多大需要的，
     請以此為出發點來改良程式。
感謝Jennya Chang的建議。
以下來試寫一個尚未驗證能否確實改進效率的方法。
這個方法的核心觀念在於：
如果像15=1111很多1的會很難作，
那麼我們是不是可以算16=10000，回過頭來再扣回1(除以m)就可以了？
整體而言，我們的演算法是：
如果~n的bitsum比較小，就算m^(n+~n+1)/m^(~n+1)，
這裡的~n是以從n的最高位以下的所有bit作反轉。

等式例如： 101011 = 1000000 - ( 010100 + 1)

我們先算n在二進位中有多少個digit，假設為d，
接著將1左移d位就是n+~n+1了!我們把它叫作x。
那麼~n就等於(x-1)和n作XOR。
同時我們就可以計算n的二進位含1的個數bit。
如果bit < d-bit 就直接算m^n，(也就是原來的方法)
否則就算m^x / m^(~n+1)。

這個方法關鍵點在於bitsum計算的速度，
以及最後會多出一個除法。
只要這兩件事情比起少做的乘法數還要快，
程式就會比較節省時間。
等有時間在來計算跑多次的執行時間列出來XD~

Code：

int bitsum(unsigned long n, int *d)
{
 int bitsum = 0;
 *d = 0;
 while(n) // while n > 0
 {
  *d = *d + 1;
  if ( n & 0x01UL == 1 )
   bitsum++;
  n >>= 1;
 }
 return bitsum;
}
unsigned long iterative_power(unsigned long m, unsigned long n)
{
 unsigned long m_x, n_c1, temp = 1, x = 1;
 int bit, *d;
 d = (int*)malloc(sizeof(int));
 bit = bitsum(n, d);
 if( bit < *d - bit)
  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
  }
 else
 {
  x <<= *d;        // 100000....0
  n_c1 = ((x-1)^n) + 1;   // n_c1 equals ((x-1) XOR n) + 1
  m_x = m;
  while(*d)
  {
    *d  = *d - 1;
   m_x *= m_x;
  }
  while(n_c1)     // while n_c1 > 0
  {
   if ( n_c1 & 0x01UL == 1) // last bit is 1
   temp *= m;
   m *= m;        // m -> m^2 -> m^4 -> m^8 ......
   n_c1 >>= 1;    // throw the last bit
  }
  temp = m_x / temp; // m^x / m^(n_c + 1)
 }
 return temp;
}