X的N次方求解——pow(x,n)實現

X的N次方求解——pow(x,n)實現

最近看到這樣的一個題目求X的N次方，自己想了一些解決辦法，記錄一下留作日後參考。

求X的N次方，首先暴力求解：

int exp(int x, int n)
{
   int ret = 1;
   for(int i = 0; i < n; i++)
   {
       ret *= x;
   }
   return ret;
}

很簡單就可以實現，算法的復雜度是O（N），那麼有什麼辦法可以優化呢，現在是O（N），那麼就要朝著O（logN）的方向進行優化，以25為例X^25，可以先考慮X^1， X^2 ，X^4， X^8， X^16，然而還差X^9，同理我們將9分解為X^1， X^2 ，X^4， X^8，余下的就是X^1，將每個步驟的最大次方提取出來就是X^16，X^8，X^1，其實就是將25分解成16，8，1也就是25的二進制表示11001。把25分解後如何處理呢，遍歷25的每一位i，如果是1，那麼result *= X(2^i)，最後也就求出X^25 = X^1 * X^8 *X^16。

int exp(int x, int n)
{
    int ret = 1;
    if(n == 0)
       return ret;
    int k = n;
    while(k != 0)
    {
        if((k & 0x1) != 0)
           ret *= x;
        x *= x;
        k >>= 1;
    }
    return ret;
}

O（logN）的這種思路通過遞歸的方式實現理解起來比較簡單。

int exp(int x, int n)
{
    if(n == 0)
       return 1;
    if(n == 1)
    {  
       return x;
    }
    else
    {
      int s;
      int m  = n / 2;
      s = exp(x, m);
      if(m % 2 == 0)
      {
         return s * s;
      }
      else
      {
         return s * s * x;
      }
    }
}