Binary exponentiation is a simple technique used to find the value for **a ^{n}** in O(logn) multiplications instead of the naive way which is O(n) multiplications. First, let's have a look at the naive way then this way.

## The naive way

From mathematics, **a ^{n}** is expressed as a multiplying itself n times. Hence a naive function for solving this will be like below.

```
int pow(int a, int n){
int ans = 1;
while(n--){
ans *= a;
}
return ans;
}
```

This is quite simple but we will want to reduce the complexity of this function and that is where binary exponentiation comes in.

## This way(Binary Exponentiation)

In this method, the work is split into the binary representation of the exponent which reduces the computation to O(logn).

#### Example

Naive: 3^{13} = 3 * 3 *...* 3

This way: 3^{13} = 3^{1101} = 3^{8} * 3^{4} * 3^{1}

Implementing an algorithm for this is very simple. intead of looping n times we rather loop through the bits which is logn times. To get our solution, we then find the powers at which a bit is set just like the example above. Because we are using the binary presentation of n the power at a set bit will be the square of the previous set bit.

That is:

3^{1} = 3

3^{2} = (3^{1})^{2}

3^{4} = (3^{2})^{2}

3^{8} = (3^{4})^{2} ...

So with this, we just find the product of the powers set in n.

## Code for this way

```
int pow(int a,int n){
int res = 1;
while(b){
if(b&1){
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
```

The above code computes in O(logn) which is better than the naive way which computes in O(n)

## Top comments (2)

There seems to be a small mistake in the example:

This way: 3should be^{13}= 3^{1101}= 3^{8}* 3^{4}* 3^{2}3^{8}* 3^{4}* 3^{1}Thanks for the correction