Pow and Sqrt

50.Pow(x, n)

解法一: 求x的幂，可以将它的指数转换成二进制的形式，把n看成是以2为基底构成的，对x求幂，迭代知道n取到最高位。

$$ 3^{11} = 3^{1 + 2 + 8} = 3^1 3^2 3 ^8 $$

上述求幂的过程是，判断最高位是不是1，如果是那么res = res,res= x;

double myPow(double x, int n){
  bool negative = n < 0?true:false;

  n = abs(n);
  double res = 1;
  for(int i = 31; i >= 0; i--){
    res *= res;
    if(n>>i & 1)
      res *= x;
  }
  return nagative?1/res:res;
}

感觉这个方法不太对，因为像(-2.0, INT_MIN)这样的情况并没有考虑到。 经过测试，发现abs(INT_MIN) = INT_MIN,并没有得到想要的2147483648，因为int表示不了这个值。同时，上面的解法没有考虑到底数是0的情况。

递归的版本

class Solution {
public:
    double myPow(double x, int n) {
        if(n<0) return 1/x * myPow(1/x, -(n+1));
        if(n==0) return 1;
        if(n==2) return x*x;
        if(n%2==0) return myPow( myPow(x, n/2), 2);
        else return x*myPow( myPow(x, n/2), 2);
    }
};

完整的版本

#include <iostream>
#include <limits.h>

using namespace std;

bool invalidInput = false;

//判断两个浮点数是否相等
bool equal(double num1,double num2){
        return ((num1 - num2 > -0.000001) && (num1-num2 < 0.0000001));
}

//也可以用递归来求解power
double power(double x, unsigned int p){
    double res = 1.0;

    for(int i = 31; i >= 0; i--){
        res *= res;
        if((p>>i) & 1)
            res *= x;
    }
    return res;
}

double power2(double x, unsigned int p){
  if(p == 0)
    return 1;
   double res = power(x, p/2);

   return (p&1)?res*res*x:res*res;
}
double myPower(double base, int exponent){
    invalidInput = false;

    if(equal(base, 0.0) && exponent <= 0){
        invalidInput = true;
        return 0.0;
    }

    unsigned int absExponent = (unsigned int)(exponent);
    if(exponent < 0)
        absExponent = (unsigned int)(-exponent);

    double result = power(base, absExponent);

    if(exponent < 0)
        result = 1.0/result;
    return result;
}

int main(){
    double b = 0.0;
    int p = 0;

    cout<<myPower(b, p)<<endl;
    return 0;
}