C++ Program of Fast Exponentiation using Bit Manipulation

By Anushka Sethi

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ⁿ).

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ⁿ.
• 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ⁿ.

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 O(logN) and the Space Complexity is O(1) of the optimized approach which is much better than the basic approach.