Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

miniluigi's blog

By miniluigi, history, 8 years ago,

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:

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

• +8

| Write comment?
 » 8 years ago, # | ← Rev. 2 →   +10 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.
•  » » 8 years ago, # ^ |   0 Huh, OK I guess that makes sense. Thanks for your help!
 » 8 years ago, # |   +32 You can make that function run even in O(1) if you use some bit hacks (works only in GCC, 8992243): int log(int x) { return 32 - __builtin_clz(x) - 1; } 
•  » » 7 weeks ago, # ^ |   0 Won't the TC be O(lg x) instead of O(1) since , TC of __builtin_clz(x) is lg(x) ?
•  » » » 7 weeks ago, # ^ |   +10 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).
•  » » » » 5 weeks ago, # ^ |   0 Okay, thnx for info
 » 8 years ago, # |   0 Here is the implementation of log2 function, it's 200 lines of code. In contrast, your log function compiles into a 4 instruction loop, so it takes 128 instructions in the worst case.
 » 8 years ago, # | ← Rev. 3 →   -8 slight modification of BekzhanKassenov's code to cover long long as well int log(long long x) { return 64 - __builtin_clzll(x) - 1; } 
 » 5 weeks ago, # |   -8 easy