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

`log2`

function, it's 200lines of code. In contrast, your`log`

function compiles into a 4 instruction loop, so it takes 128instructionsin the worst case.slight modification of BekzhanKassenov's code to cover long long as well

easy