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

請參見數值自乘非遞迴解。
*1. 這個程式的乘法數目還可以再降低，
     其實我們保持完整的m, m^2, m^4, m^8, ...是沒多大需要的，
     請以此為出發點來改良程式。
 2. 請用手算方式列出計算2^13, 2^15, 2^16的過程，
     是不是這個程式也會得到算2^15時要多幾個乘法呢？
　 請問一般而言，當n是多少時會比較慢？
 3. 如果您用的硬體系統會偵測出整數溢位(Overflow)，
     那麼這個程式可能就會有問題，因為求出m^45時會同時多算了m^64，
     那麼m^64就可能溢位。請修改程式克服這一點問題。

個人解答：
1. 這題不太確定題目的意思。
    因為不論如何還是會經過m的偶數次方。
    如果是指想要快速經過中間二進位的0值的話，
    大概再將3.的答案改成如下：

Code：

while(1)
{
 while( n & 0x01UL == 0 )
  if((n >>= 1) > 0)
   m *= m;
 if ( n & 0x01UL == 1 ) // last bit is 1
  temp *= m;
 if((n >>= 1) > 0)
  m *= m;
 else
  break;
}

這並不是好作法，而且會降低程式可讀性。
如果有人能理解這題到底是想改進什麼的話，
請不吝指教XD~

2. 換成二進位來看時，13 = 1101 , 15 = 1111, 16 = 10000
    我們以只考慮temp*=m和m*=m這兩個乘法作的總次數為前提來看的話，
    1101會做7次，1111會做8次，10000會做6次，
    簡而言之，乘法的總次數相當於(二進位值的總位數+二進位值裡的1的總數)。
    所以在二進位位數同等狀況下，裡面含有越多1，程式就做越慢。
    這點跟之前遞迴解時，有些n會導致乘法次數變多的原因是一樣的。
3. 由於n為正整數，我們可以將判斷迴圈繼續的條件搬到迴圈裡面，
    先判斷n丟掉最右邊的bit後是否還大於0，
    還大於0的話才表示有繼續將m往上計算的價值，
    否則的話我們就可以直接break。

Code：

while(1)
{
 if ( n & 0x01UL == 1) // last bit is 1
  temp *= m;
 if((n >>= 1) > 0)
  m *= m;
 else
  break;
}