Hi reader. Coming straight to the point. The value of (1ll<<59) or 2^59 is 576460752303423488(say x).So if you do log2(x),the answer should come out to be 59.That's indeed the case. But here is the catch... .If you do log2(x-1) in C++ 14(not sure for other versions),it also gives 59 as output..(but actual answer is 58), which is wrong and that caused me a fst in recent Div 3 problem F.
So, can anyone explain why is this happening and how to avoid these types of things. Thanks for spending your time in reading this blog.
Why log2((2^59)-1)=59?
Be careful with log2() !!!!
log2 function limitations!!! be careful with this function
The comment section of these blogs will answer your question.
Not only log2(). You should also be careful with pow(), sqrt(), and any other inbuilt functions that operate on integers $$$\ge 2^{31}$$$.
Thanks bro. Got it.
I use log2((long double)x).It even works for integers >2^31.
Use __lg(x) for floored log2.
I use
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) — __builtin_clzll((X)) — 1))I got to know about this when I was solving this question Here is my submission without using the above code which gave me a
WAand here is my submission with the above code give gave me aAC. Hope was helpfulNice :)