428. pow(x, n)

public class  {
    
     * @param x: the base number
     * @param n: the power number
     * @return: the result
     */
    public double myPow(double x, int n) {
        // write your code here
        if (x == 0 && n == 0) {
            throw new IllegalArgumentException("0 to 0 is not legal!");
        }

        boolean isNeg = false;
        if (n < 0) {
            isNeg = true;
            n = - (n + 1); // avoid overflow
            x= 1 / x;
        }
        
        eg. x^N = x^9 = x^(1001(2)) = x^(2^3 + 2^0)
        = x^(2^3) . x^(2^0)
        tmp: (x, x^2 , x^ 4, x^8,...)
             (x^(2^0), x^(2^1), x(2^2),2^(2^3)...)
             当n那一位是1时，把tmp乘上ans去


        */
        double ans = 1, tmp = x;
        while(n != 0) {
            if ((n & 1) == 1) {
                ans *= tmp;
            }
            tmp *= tmp;
            n = n>>1;// n已经是正数，右移补0
        }
        if (isNeg) {
            ans = ans * x;
        }
        return ans;



    }
}

public class  {
    
     * @param x: the base number
     * @param n: the power number
     * @return: the result
     */
    public double myPow(double x, int n) {
        boolean isNeg = false;
        if (n < 0) {
            isNeg = true;
        }
        return isNeg ? (1/x) * helper(x, n) : helper(x, n);
    }

    private double helper(double x, int n) {
        if (n < 0) {
            x = 1 / x;
            n = - (n + 1);
        }
        if (n == 0) { // base case
            return 1;
        }

        double tmp = helper(x, n/2);
        if (n % 2 == 1) {
            return tmp * tmp * x;
        } else {
            return tmp * tmp;
        }
    }
}