| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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
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
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.
yeah...same situation :P typecasted it and got ac now -_- thanks again
Hard luck man!...Will try not to repeat similar mistakes again...
We can even use log2l() inbuilt method.
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 oflog2(x).Thank you
use
__lg(x)(for gcc compiler)is it give ceil value or floor
if i call __lg(576460752303423487) then it will give 58
while my user defined log function give 59 ? HOW ?
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.
__lg() is risky
https://codeforces.com/blog/entry/90175
Edit: better function
int log(ll x){ return __builtin_clzll(1ll) - __builtin_clzll(x); }how does this work?
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.more on builtin funcitons
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.
Thanks . I understood
how come
__log()doesn't workI 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()tolog2()fromcmathlib 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.That's because that program tried doing
__lg(0), which is undefined.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_widthfor a long time now (it is calledbit_lengthin Python) and it is both very useful and easy to remember.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).