Power bit wise problem

#1

anyone help me with the logic please

#2

@Sajid07
It would be better if you would try its recursive approach first for a better understanding first. The idea is simple but gets a little complicated while implementing. We use the exponentiation property -

a^b = ( a ^ (b/2) ) ^ 2

Now since we are only creating factors of 2 here , we can use bitwise operations to implement this .
Here’s a pseudocode

// Returns a^b
power(a,b)
{
res = 1
while ( b > 0 )
{
if( b & 1)
{
res = res * a
}
a *= a
b = b>>1
}

return res

}

The idea is to keep increasing the power of a by multiplying it with itself and to multiply it with result as soon as we hit a set bit in b.
Since we are dividing b by 2 in the loop , the no of set bits in b is the no of times we have to exponentiate res.
Try to dry run this pseudocode on a simple testcase and I believe the idea should be clear enough.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.