Pow(x, n) 求一個數的n次方

我們知道C++中是有pow函數的，我們這次自己來寫個，因為有這樣的算法題目。

所需數學知識：

大緻考慮正數，0，負數即可。n多個數相乘的問題。

1.簡單For循環

這還不簡單，馬上寫一個for循環：

double pow(double x, int n){
  int m = abs(n);
  double result = 1;
  for(int i = 0; i < m; ++i){
    result *= x;
  }
  return n > 0 ? result : 1/result;
}      

2.最慢的遞歸求解

受 1+2+3+4+5...+N的問題用遞歸求解思路影響，我們知道這裡可以用一個非常慢的遞歸來求解。

double pow(double x, int n){
    if(n == 0){
        return 1;
    }
    if(n > 0 ){
          return x * pow(x, n - 1);
     }else{
          return 1 /  pow(x, -n);
     }
    
}      

搞不好比for循環還要慢。

3.很大改進的遞歸求解

都先考慮正數。我們在想，n多個2相乘，如果n剛好能被2整除，我們可以把n分成一半一半來考慮。

可以把它們想成是一半*一半，不能被2整除的話，也隻是多乘以一個自己。

double pow(double x, int n){
  if(n == 0){
    return 1;
  }
        if(n > 0 ){
      double half = pow(x, n / 2);
      if(n % 2 == 0){
    return half * half;
      }else{
    return half * half * x;
      }      
  }else{
    return 1 /  pow(x, -n);
  }
}      

我們知道這裡的 n / 2，和 n % 2還可以用位運算來提高速度

n / 2  ==  n >> 1 (在傳回是int值的情況下)

n % 2 == n&1

修改如下：

double pow(double x, int n){
  if(n == 0){
    return 1;
  }
        if(n > 0 ){
      double half = pow(x, n >> 1);
      if((n&1) == 0){
    return half * half;
      }else{
    return half * half * x;
      }      
  }else{
    return 1 /  pow(x, -n);
  }
}      

4.當然還有優化空間！

3标題中我們其實做的事情是對n的每次取半再相加，這樣太慢了，直接除以2比較快。當然遇到不能整除的要多乘以一個自己。

double pow(double x, int n){
  int m = abs(n);
  double result = 1;
  while(m > 0){
    if(m % 2 != 0){
      result = result * x;
    }
    x *= x;
    m = m / 2;
  }
  return n > 0 ? result : 1 / result;
}      

通過位運算優化後就是：

double myPowFunction(double x, int n){
    int m = abs(n);
    double result = 1;
    while(m > 0){
        if((m&1) != 0){
            result = result * x;
        }
        x *= x;
        m >>= 1;
    }
    return n > 0 ? result : 1 / result;
}      

​