Pow(x, n)

Implement pow(x, n).

This one seems easy, but one needs to be very careful to code it right. Esp. remember to deal with the fact that n could be negative!

1. Iterative way:
class Solution {
public:
    double pow(double x, int n) {
         if (n==0) return 1;
         double ret=1;
         int m=n;
         for (;n!=0;x=x*x,n=n/2)
         {
             if (n%2!=0)
                ret*=x;
         }
        
         if (m<0)
           ret=1/ret;
        
         return ret;
    }
};

2. Recursive way:
class Solution {
public:
    double pow(double x, int n) {
         if (n<0)
           return 1/power(x,-n);
         else
           return power(x,n);
    }
   
    double power(double x, int n)
    {
        if (n==0) return 1;
       
        double v=power(x,n/2);
       
        if (n%2==0)
           return v*v;
        else
           return v*v*x;
    }
};