imnasim3.1415's blog

log2 function limitations!!! be careful with this function
By imnasim3.1415, history, 6 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?
»
6 years ago, hide # |
← 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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

We can even use log2l() inbuilt method.

→ Reply
»
6 years ago, hide # |
← 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
»
6 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

use __lg(x) (for gcc compiler)

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    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
    • »
      »
      »
      6 years ago, hide # ^ |
       
      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
  • »
    »
    5 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it -13 Vote: I do not like it

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

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

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

      how does this work?

      → Reply
      • »
        »
        »
        »
        5 years ago, hide # ^ |
        ← 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
»
6 years ago, hide # |
 
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