power(a, n) in iteration way

Given a, n, calculate a^n in non-recursive way.

The traditional way is to use recursion to reach O(logN) solution. For iteration, we can use stack to implement the recursion process. In stack, 1 means result times a, -1 means result times result, 0 doing nothing.

Take 11 as example, the process is like:

Take 15 as example, the process is like:

Below is my code:

public static int power(int a, int n) {
    // build stack
    Stack s = new Stack();
    s.add(n);
    while(s.peek()>1) {
        int curr = s.pop();
        s.push(curr%2); //1 means result should time a.
        s.push(-1); //-1 means result should time result.
        s.push(curr/2);
    }
    int result = 1;
    while(!s.isEmpty()) {
        int curr = s.pop();
        switch (curr) {
            case 1:
                result = result * a;
                break;
            case -1:
                result = result * result;
                break;
        }
    }
    return result;
}

However, this problem can be solved in O(logN) time and O(1) space. Below is a process to calculate a^9:

public static int power(int a, int n) {
    int result = 1;
    while(n>0) {
        if(n%2==1)
            result = result * a;
        a = a * a;
        n = n>>1;
    }
    return result;
}

In order to understand this solution more clearly, we can transform the exponent in binary: . We know a in the code is a base. It changes like: . And we know . In this way, we know that calculating  is similar the process to build binary 1001.  The difference is that instead doing plus, we do multiplication.

In the code, a = a* a is to enlarge the base. result = result * a is to add the base in the result.