This project is performed in C++ and helps students and users to find Fast Exponentiation of a number using the method of Bit Manipulation.

Today we will learn the Bit Manipulation method to find the Fast Exponentiation of a number using C++.

Given two integers **a** and **n**, the task is to calculate **a** raised to power **n** (i.e. **a ^{n}**).

The basic approach would be to repetitively multiply the integer **a**, **n** times and output the product. However, this approach will have a *Time Complexity of O(N) *and a *Space Complexity of O(1)* which indicates longer running time performed by an algorithm.

**Efficient Approach:**

To optimize the above approach, the idea is to use *Bit Manipulation*. Bitwise operations are incredibly simple and thus usually faster than arithmetic operations which involve making use of bitwise and shift operators. We start off by converting the integer **n** to its binary form and follow the steps below:

- Declare and Initialize
**ans**to store the final answer of a^{n}. - The loop is traversed until
**n > 0**. In each iteration, perform*Right Shift*operation on**n**so that with each iteration, we discard the bit of n until the last bit. - In each iteration of the loop,
**a**is multiplied/squared with itself and updated. - If the current least significant bit is set, then multiplication of the current value of
**a**is done with that of**ans**. - Finally, after the loop condition does not suffice, we come out of the loop and print
**ans**, the result of a^{n}.

Below is the implementation of the above approach:

#include using namespace std; //Exponentiation/Power using Bitmasking int power_optimised(int a, int n){ int ans = 1; while (n>0) { int last_bit = (n&1); if(last_bit){ ans=ans*a; } a=a*a; //Square up n=n>>1; //Discard the last bit of N } return ans; } int main(){ int a, n; cout<<"Enter the base number: "; cin>>a; cout<<"Enter the exponent: "; cin>>n; cout<<"The power of "<<a<<" raised to "<<n<<" is: "<<power_optimised(a,n)<<endl; return 0; }

Enter the base number: 3 Enter the exponent: 5 The power of 3 raised to 5 is: 243

The* Time Complexity *is

Submitted by Anushka Sethi (anushkasethi)

Download packets of source code on Coders Packet

## Comments