### imnasim3.1415's blog

By imnasim3.1415, history, 18 months ago,

log2 function making problems with long integers. while for x=765228007342234864, log2(x)=59, which is correct. But while x=576460752303423487 log2(x) returns negative value..

why is this happening and how to solve it? any built-in functions to update this?

nevertheless, be careful with it

• -2

 » 18 months ago, # | ← Rev. 2 →   +8 Instead of this use your own function.If u need ceil(log2(N)) then first calculate whether N is a perfect power of 2 if yes then simply calculate LOG2(N) otherwise LOG2(N)+1 #define lli long long int bool ispower2(lli n){ return(n and (n&(n-1))==0 ); } lli LOG2(lli n){ lli cnt=0; while(n){ cnt++; n/=2; } return cnt; } if(ispower2(N)) print(LOG2(N)) else print(LOG2(N)+1) 
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 thanks for the help man... also see the second comment, I think typecasting will be really easy and effective...
 » 18 months ago, # |   +3 I got a wrong answer on Test Case 8 of Today's Div2 C for using this function.After the contest I typecasted the parameter type of the log2() function to long double,and the solution got accepted.
•  » » 18 months ago, # ^ |   0 yeah...same situation :P typecasted it and got ac now -_- thanks again
•  » » » 18 months ago, # ^ |   0 Hard luck man!...Will try not to repeat similar mistakes again...
•  » » » 18 months ago, # ^ |   0 In ongoing contest if u use something predefined function and u gt WA then I will suggest just make ASAP the user defined function .BTW today C is just one liner print(2*n - No._of_1s_in(2*n)) 
 » 18 months ago, # |   0 We can even use log2l() inbuilt method.
 » 18 months ago, # | ← Rev. 2 →   0 This error mainly occurs for precision loss of double type, If you pass the argument of log2() function as long double, the chance of error loss becomes tiny. To pass the argument as long double, you have to multiply the argument with 1.0L. (L stands for suffix of long double literal).so you can write log2(1.0L*x) instead of log2(x).Thank you
 » 18 months ago, # |   +1 use __lg(x) (for gcc compiler)
•  » » 18 months ago, # ^ |   0 is it give ceil value or floorif i call __lg(576460752303423487) then it will give 58 while my user defined log function give 59 ? HOW ?
•  » » » 18 months ago, # ^ |   0 it prints the 0-indexed position of the leading bit of the number(for positive integers only, UB otherwise), which is (mathematically) equivalent to taking floor(log_2(x)). Your number is in range [2^58, 2^59) so it prints 58.
•  » » 6 months ago, # ^ | ← Rev. 4 →   -13 __lg() is risky https://codeforces.com/blog/entry/90175Edit: better function int log(ll x){ return __builtin_clzll(1ll) - __builtin_clzll(x); }
•  » » » 6 weeks ago, # ^ |   0 how does this work?
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 it works in binary representation, __builtin_clzll() returns the number of consecutive zeroes from the left in a binary representation. for example: if we have 64 bit representation of 6 (000...110) then the above function will return 61 as the number of zeroes before 1st set bit from the left.so the above expression __builtin_clzll(1ll) - __builtin_clzll(x); works by subtracting the number of zeroes on the left of long long binary representation of x from the number of zeroes on the left of long long binary representation of 1. This works because log base 2 of a natural number is the highest significant bit in it's binary representation.NOTE: these are builtin functions of GCC compiler, have no idea about other compilers.
•  » » » » » 6 weeks ago, # ^ |   0 Thanks . I understood
•  » » » » » 6 weeks ago, # ^ |   0 how come __log() doesn't work
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I don't know why it doesn't work but in this post I tried __lg() in this question and it was causing TLE for some unknown reason. changing the __lg() to log2() from cmath lib fixed the TLE. maybe someone can read the documentation and explain why that happened but I don't know.EDIT: __lg() was causing TLE even for the sample test case for GNU C++17.
•  » » » » » » » 6 weeks ago, # ^ |   +1 That's because that program tried doing __lg(0), which is undefined.
•  » » » » » 6 weeks ago, # ^ |   0 Just one small note, with C++20 now being a thing on cf, you can just use bit_width instead of all of these weirdly named functions. Python has had bit_width for a long time now (it is called bit_length in Python) and it is both very useful and easy to remember.
 » 18 months ago, # |   0 Instead of log2(x) use log2((long double)x). Generally, operations with long double are more precise than operations with double. (I passed round 647 div2 A using this).