Time Complexity of floor and log2

Правка en3, от 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://mirror.codeforces.com/contest/633/submission/18990265

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский miniluigi 2016-07-09 21:25:56 4
en2 Английский miniluigi 2016-07-09 21:25:22 4
en1 Английский miniluigi 2016-07-09 21:22:56 578 Initial revision (published)