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
i bet the main reason ur code is faster is because c++ function log2() works with doubles, and ur function log() works with integers only. I just replaced int by double in type that log() returns and in parameter that log() recieves and it caused TL 22.
Huh, OK I guess that makes sense. Thanks for your help!
You can make that function run even in O(1) if you use some bit hacks (works only in GCC, 8992243):
Won't the TC be O(lg x) instead of O(1) since , TC of __builtin_clz(x) is lg(x) ?
The implementation of __builtin_clz(x) is based on simple CPU instructions that exist for certain CPU architectures and is incredibly fast, in fact it seems like it is just two Assembly instructions. This makes it faster than even things like multiplication, i.e. it is O(1).
Okay, thnx for info
Here is the implementation of
log2function, it's 200 lines of code. In contrast, yourlogfunction compiles into a 4 instruction loop, so it takes 128 instructions in the worst case.slight modification of BekzhanKassenov's code to cover long long as well
easy