quick-pow-iterative.java

public class Solution {
    public double myPow(double x, int n) {
        if (n < 0 && -n < 0) {
            n /= 2;
            x *= x;
        }
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        // Loop invariant:
        // At the beginning of the j-th (0-based) iteration, y = x to the power of n', where n' is the first j digits of n.
        // Alternatively:
        // At the end of each iteration, y = x to the power of n >> i.
        double y = 1;
        for (int i = Integer.SIZE-1; i >= 0; i--) {
            y *= y;
            if ((n & (1 << i)) != 0) {
                y *= x;
            }
        }
        return y;
    }
}