LeetCode - Pow(x, n)

Implement pow(x, n).
Code from http://www.programcreek.com/2012/12/leetcode-powx-n/

public class Pow {

    public double pow(double x, int n) {

        // Handling special cases

        if (n == 0)

            return 1;

        if (x == 0 || x == 1)

            return x;

        if (x == -1) {

            if ((n & 1) == 1)

                return -1;

            else

                return 1;

        }

 

        double result = 1;

        // Handling the case when n is negative

        // pow(x,n) would normally become pow(1/x,-n)

        if (n < 0) {

            x = 1.0 / x;

            // Handle this case before n=-n; otherwise n would still be negative after n=-n

            if (n == Integer.MIN_VALUE) {

                result *= x;

                n++;

            }

            n = -n;

        }

        // Understand pow(x,n) in terms of binary representation of n: n_k, ..., n_1, n_0

        // n_i = 1 : multiply x 2^i times

        while (n != 0) {

            if ((n & 1) == 1)

                result *= x;

            x *= x;

            n >>= 1;

        }

 

        return result;

    }

Recursive Version

public 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; } }   public double pow(double x, int n) { if (n < 0) { return 1 / power(x, -n); } else { return power(x, n); } }

Read full article from LeetCode – Pow(x, n)