How to apply bitmasking in this problem

#1

how to apply bitmasking in this problem

#2

Hello @pragyachoudhary1111,

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.