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. an).
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:
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.
Submitted by Anushka Sethi (anushkasethi)
Download packets of source code on Coders Packet
Comments