50.Pow(x, n)

[niuworld]

Question:

Implement pow(x, n).

Solution:

此题不可以直接使用pow，也不可以直接用 x = x * x * x ····来解（会超时）。

使用二分法进行求解，思路：3^8-->3^4 * 3^4 ,然后每个3^4再分解成3^2 * 3^2，直到 3^1,遇到 n 为奇数的时候，就在另外多进行一次乘法即可。

class Solution {
public:
    double myPow(double x, int n) {
     if ( x == 0) 
          return 0;
     if ( x != 0 && n == 0)
          return 1;
     bool neg = ( n < 0 )? true:false;
     n = abs( n );
     double res = 1.0;
     while( n != 0){
         if( n % 2 == 1)
          res = res * x;
          x = x * x;
          n = n / 2;
      }
     return neg? 1 / res : res ; 
    }
};