Program to calculate pow(x,n) using Binary operators
Some important concepts related to this approach:
- Every number can be written as the sum of powers of 2
- We can traverse through all the bits of a number from LSB to MSB in O(log n) time.
Illustration:
3^10 = 3^8 * 3^2. (10 in binary can be represented as 1010, where from the left side the first 1 represents 3^2 and the second 1 represents 3^8)
3^19 = 3^16 * 3^2 * 3. (19 in binary can be represented as 10011, where from the left side the first 1 represents 3^1 and second 1 represents 3^2 and the third one represents 3^16)
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <iostream>using namespace std;int power(int x, int n){ int result = 1; while (n > 0) { if (n & 1 == 1) // y is odd { result = result * x; } x = x * x; n = n >> 1; // y=y/2; } return result;}// Driver Codeint main(){ int x = 2; int n = 3; // Function call cout << (power(x, n)); return 0;}// This code is contributed bySuruchi Kumari |
Output
8
Time Complexity: O(log n)
Auxiliary Space: O(1)
C++ Program To Calculate the Power of a Number
Write a C++ program for a given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn’t happen.
Examples :
Input : x = 2, n = 3
Output : 8Input : x = 7, n = 2
Output : 49