Time Complexity of floor and log2

Revision en3, by miniluigi, 2016-07-09 21:25:56

When I was coding a solution for 633E, I noticed that using

int log(int x) {
    int ct = 0;
    int k = 1;
    while (k <= x) {
        k *= 2; ct++;
    }
    return ct-1;
}

over floor(log2(x)) allowed my program to run in time. Could someone please explain to me why one is faster than the other? Thanks!

See here for my code and use compare to see that nothing else is different:

log(x): http://codeforces.net/contest/633/submission/18990265

floor(log2(x)): http://codeforces.net/contest/633/submission/18990181

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English miniluigi 2016-07-09 21:25:56 4
en2 English miniluigi 2016-07-09 21:25:22 4
en1 English miniluigi 2016-07-09 21:22:56 578 Initial revision (published)