CODEWITHSUNDEEP
c++algorithmmath
Shane Hsu
Shane Hsu

Reputation: 8357

Can someone explain how this C code calculate 2^n?

Here's the code that does the trick. I do know the concept how to calculate m^n in O(logn) time, and I think it's related, but how?

for(long long int i = 2; N; N /= 2, i *= i){
    if(N & 1){
        ans *= i;
    }
}

Upvotes: 0

Views: 1345

Answers (2)

Foon
Foon

Reputation: 6468

That's the square and multiply algorithm.

N /= 2 has the effect of removing the lowest bit (and when all the bits remaining are zero, the algorithm is finished).

N & 1 checks if the lowest bit is odd or even

Upvotes: 9

Aravind
Aravind

Reputation: 3199

It basically works the same way log N time m power n algorithm works. Just trace the code for these two sets of input:

P.S:ans should be set to 1.

  1. n=2
  2. n=3

I am sure you will get it.

Upvotes: 1

Related Questions