Power(O(Log n))

#1

I’m able to solve this ques using recursion but not using bitmasking approach. With bitmasking I’m able to solve only when the number is 2. How should I solve for other numbers using bitmasking.

Here is the link to my code:

#2

Hello @priyanshi.agarwal3405,

APPROACH:
This method uses bitmasks and without using extra space to calculate a^n in O(log n) time.

  1. Let’s take variable ans in which we store the result and initialize it with 1.
  2. Extract last bit from n.
  3. If the Extracted bit is 1 multiply ans with a, otherwise if the Extracted bit is 0 then don’t multiply.
  4. Update a to a*a.
  5. Discard rightmost bit i.e right shift b by 1.
  6. Repeat steps 2 to 5 until n becomes 0.

Following is the program explaining this:

/* Iterative Function to calculate (x^y) in O(log y) */
int power(int x, unsigned int y)
{
int res = 1; // Initialize result

while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = res*x;

// y must be even now 
y = y>>1; // y = y/2 
x = x*x;  // Change x to x^2

}
return res;
}

Hope, this would help.
Give a like, if you are satisfied.