imnasim3.1415's blog

log2 function limitations!!! be careful with this function
By imnasim3.1415, history, 4 years ago, In English

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like 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

#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)
→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah...same situation :P typecasted it and got ac now -_- thanks again

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hard luck man!...Will try not to repeat similar mistakes again...

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can even use log2l() inbuilt method.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

use __lg(x) (for gcc compiler)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it -13 Vote: I do not like it

    __lg() is risky
    https://codeforces.net/blog/entry/90175

    Edit: better function
    int log(ll x){ return __builtin_clzll(1ll) - __builtin_clzll(x); }

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how does this work?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks . I understood

          → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how come __log() doesn't work

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              That's because that program tried doing __lg(0), which is undefined.

              → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply