power(a, n) in iteration way

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

First of all, let's write down how we solve it in recursive fashion.

Here a and n are all integers and n>=0, and assume the result is in the range of integers.

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


Let's solve it in iterative way. For example, n = 4, we starts with a, calculate a^2 by a*a, then a^4 by a^2 multiples itself and return that as final result. try n = 9, we starts with a, a^2, a^4, a^8, then return a^8 * a as final result. Let's write down the formula:

a^9 = a^(0b1001) = a^8 * a.
a^4 = a^(0b100)   =  a^4
a^10=a^(0b1010) = a^8 * a^2

Essentially we represent n as binary, go through this binary number from lower bits to higher bits, then if the i-th bit is 1, then a^i is part of result.

//n>=0
public int power(int a, int n){
    if(n==0)
        return 1;
    int result = 1;
    while(n>0){
       if(n&1==1)//test the least bit
            result = result * a;
       //move to higher bit at position i
       n = n>>1;
       //calculate the a^i
      a = a * a;
   }
 return result;
}