Fast Exponentiation using Bit Manipulation
Given two integers A and N, the task is to calculate A raised to power N (i.e. AN).
Examples:
Input: A = 3, N = 5
Output: 243
Explanation:
3 raised to power 5 = (3*3*3*3*3) = 243Input: A = 21, N = 4
Output: 194481
Explanation:
21 raised to power 4 = (21*21*21*21) = 194481
Naive Approach:
The simplest approach to solve this problem is to repetitively multiply A, N times and print the product.
#include <iostream>
using namespace std;
// Function to calculate power using brute force approach
long long findPower(int a, int n) {
long long result = 1;
// Multiply 'a' by itself 'n' times
for (int i = 0; i < n; ++i) {
result *= a;
}
return result;
}
int main() {
int a = 3;
int n = 5;
// Calculate and display the result
long long result = findPower(a, n);
cout<<result<<endl;
return 0;
}
public class Main {
// Function to calculate power using brute force approach
static long findPower(int a, int n) {
long result = 1;
// Multiply 'a' by itself 'n' times
for (int i = 0; i < n; ++i) {
result *= a;
}
return result;
}
public static void main(String[] args) {
int a = 3;
int n = 5;
// Calculate and display the result
long result = findPower(a, n);
System.out.println(result);
}
}
//This code is contributed by Aman
# Function to calculate power using brute force approach
def findPower(a, n):
result = 1
# Multiply 'a' by itself 'n' times
for i in range(n):
result *= a
return result
# Main function
a = 3
n = 5
# Calculate and display the result
result = findPower(a, n)
print(result)
# This code is contributed by Yash Agarwal(yashagarwal2852002)
using System;
public class PowerCalculation
{
// Function to calculate power using brute force approach
public static long FindPower(int a, int n)
{
long result = 1;
// Multiply 'a' by itself 'n' times
for (int i = 0; i < n; ++i)
{
result *= a;
}
return result;
}
public static void Main(string[] args)
{
int a = 3;
int n = 5;
// Calculate and display the result
long result = FindPower(a, n);
Console.WriteLine(result);
}
}
// Function to calculate power using brute force approach
function findPower(a, n) {
let result = 1;
// Multiply 'a' by itself 'n' times
for (let i = 0; i < n; i++) {
result *= a;
}
return result;
}
// Main function
const a = 3;
const n = 5;
// Calculate and display the result
const result = findPower(a, n);
console.log(result);
//This code is contributed by Aman.
Output
243
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, the idea is to use Bit Manipulation. Convert the integer N to its binary form and follow the steps below:
- Initialize ans to store the final answer of AN.
- Traverse until N > 0 and in each iteration, perform Right Shift operation on it.
- Also, in each iteration, multiply A with itself and update it.
- If current LSB is set, then multiply current value of A to ans.
- Finally, after completing the above steps, print ans.
Below is the implementation of the above approach:
// C++ Program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to return a^n
int powerOptimised(int a, int n)
{
// Stores final answer
int ans = 1;
while (n > 0) {
int last_bit = (n & 1);
// Check if current LSB
// is set
if (last_bit) {
ans = ans * a;
}
a = a * a;
// Right shift
n = n >> 1;
}
return ans;
}
// Driver Code
int main()
{
int a = 3, n = 5;
cout << powerOptimised(a, n);
return 0;
}
// Java program to implement
// the above approach
class GFG{
// Function to return a^n
static int powerOptimised(int a, int n)
{
// Stores final answer
int ans = 1;
while (n > 0)
{
int last_bit = (n & 1);
// Check if current LSB
// is set
if (last_bit > 0)
{
ans = ans * a;
}
a = a * a;
// Right shift
n = n >> 1;
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int a = 3, n = 5;
System.out.print(powerOptimised(a, n));
}
}
// This code is contributed by PrinciRaj1992
# Python3 program to implement
# the above approach
# Function to return a^n
def powerOptimised(a, n):
# Stores final answer
ans = 1
while (n > 0):
last_bit = (n & 1)
# Check if current LSB
# is set
if (last_bit):
ans = ans * a
a = a * a
# Right shift
n = n >> 1
return ans
# Driver code
if __name__ == '__main__':
a = 3
n = 5
print(powerOptimised(a,n))
# This code is contributed by virusbuddah_
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return a^n
static int powerOptimised(int a, int n)
{
// Stores readonly answer
int ans = 1;
while (n > 0)
{
int last_bit = (n & 1);
// Check if current LSB
// is set
if (last_bit > 0)
{
ans = ans * a;
}
a = a * a;
// Right shift
n = n >> 1;
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int a = 3, n = 5;
Console.Write(powerOptimised(a, n));
}
}
// This code is contributed by Princi Singh
// JavaScript program to implement
// the above approach
// Function to return a^n
function powerOptimised(a, n)
{
// Stores final answer
let ans = 1;
while (n > 0)
{
let last_bit = (n & 1);
// Check if current LSB
// is set
if (last_bit > 0)
{
ans = ans * a;
}
a = a * a;
// Right shift
n = n >> 1;
}
return ans;
}
// Driver Code
let a = 3, n = 5;
console.log(powerOptimised(a, n));
Output
243
Time Complexity: O(logN)
Auxiliary Space: O(1)
Another efficient approach : Recursive exponentiation
Recursive exponentiation is a method used to efficiently compute AN, where A & N are integers. It leverages recursion to break down the problem into smaller subproblems. Follow the steps below :
- If N = 0, the result is always 1 because any non zero number raised to the power of 0 is 1.
- If N is even, we can compute AN as (AN/2)2 . This is done by recursively computing AN/2 & squaring the result.
- If N is odd, we compute AN as A * AN – 1 . Again, we recursively compute AN -1 & multiply the result by A.
Below is the implementation of the above approach :
#include <iostream>
using namespace std;
// Function to calculate A raised to the power N using recursion
long long recursive_exponentiation(long long A, long long N) {
if (N == 0) {
// Base case: A^0 = 1
return 1;
} else if (N % 2 == 0) {
// If N is even, recursively compute A^(N/2) and square it
long long temp = recursive_exponentiation(A, N / 2);
return temp * temp;
} else {
// If N is odd, recursively compute A^(N-1) and multiply by A
return A * recursive_exponentiation(A, N - 1);
}
}
int main() {
// Test case
cout << recursive_exponentiation(3, 5);
return 0;
}
public class RecursiveExponentiation {
// Function to calculate A raised to the power N using recursion
public static long recursiveExponentiation(long A, long N) {
if (N == 0) {
// Base case: A^0 = 1
return 1;
} else if (N % 2 == 0) {
// If N is even, recursively compute A^(N/2) and square it
long temp = recursiveExponentiation(A, N / 2);
return temp * temp;
} else {
// If N is odd, recursively compute A^(N-1) and multiply by A
return A * recursiveExponentiation(A, N - 1);
}
}
public static void main(String[] args) {
// Test case
System.out.println(recursiveExponentiation(3, 5));
}
}
def recursive_exponentiation(A, N):
if N == 0:
return 1
elif N % 2 == 0:
# If N is even, recursively compute A^(N/2) and square it
temp = recursive_exponentiation(A, N // 2)
return temp * temp
else:
# If N is odd, recursively compute A^(N-1) and multiply by A
return A * recursive_exponentiation(A, N - 1)
# Test cases
print(recursive_exponentiation(3, 5))
// Function to calculate A raised to the power N using recursion
function recursiveExponentiation(A, N) {
if (N === 0) {
// Base case: A^0 = 1
return 1;
} else if (N % 2 === 0) {
// If N is even, recursively compute A^(N/2) and square it
const temp = recursiveExponentiation(A, N / 2);
return temp * temp;
} else {
// If N is odd, recursively compute A^(N-1) and multiply by A
return A * recursiveExponentiation(A, N - 1);
}
}
// Test case
console.log(recursiveExponentiation(3, 5));
Output
243
Complexity Analysis :
Time Complexity: O(logN)
Auxiliary Space: O(1)