XiangXunyi's blog

1e18 + 1 == 1e18 in C++
By XiangXunyi, history, 3 months ago, In English

As the title, 1e18 + 1 == 1e18 in C++.

This is because the double type stores the first 53 binary bits of a number. So the number 1 will be ignored.

And most of submissions which fst on test 13 of problem C of edu round 187 are for this reason.

UPD: I collected some suggestions from the comments:

  1. Use 1000000000000000001 (I do not suggest it because it is prone to errors.)
  2. Use (long long)(1e18) + 1
  3. Use 1e18L + 1
  4. Use 1'000'000'000'000'000'001LL
  • Vote: I like it
  • +248
  • Vote: I do not like it

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

I hate my life

→ Reply
»
3 months ago, hide # |
 
Vote: I like it -20 Vote: I do not like it

f*ck this shit

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I got wrong for this :(

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

Just use LLONG_MAX, it's in the c++ standard and expressive!

reference

→ Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it +16 Vote: I do not like it

    Then inf + inf leads to overflow. I don't like to assign more than 3e18 to inf for that reason.

    → Reply
    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it +15 Vote: I do not like it

      i usually use LLONG_MAX/4 so that it is >2e18 while inf+inf is still in long long range. for int i would use INT_MAX/2

      although it is a strange habit but it avoids problems most of the time

      → Reply
»
3 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

laugh as never use expressions like that.i only use 100000000... despite that the work of counting zeros is a bit annoying

→ Reply
»
3 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

hi! i think using implicit conversion is a good enough fix for this i.e. using something like: -

const long long INF = 1e18

i used the above mentioned declaration for my binary search bounds, and it AC'ed without any issues.

although i do believe the best way to avoid such issues is to use integer literals: -

const long long INF = 1000000000000000000LL
→ Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Why is it that we should use 1000000000000000000LL instead of 1e18, really curious as I have zero idea?

    → Reply
    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      essentially because they represent different data types, 1e18 is a double whereas the first one's an integer literal.

      → Reply
»
3 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

u can just force it back to long long to avoid this problem, like this const long long INF = (long long) 1e18;

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

There is 1e18l in g++

→ Reply
»
3 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

你说的很对！

→ Reply
»
3 months ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

I hate this type of bug. That's I always initialize long long with a loop to make sure the value reach exactly the correct limit. For example, to initialize with 1e18 + 1 it suffices to do:

ll MAX = 1e9;
while(MAX <= 1e18 + 1) MAX++;
MAX--;

Note the optimization that I initialize with MAX = 1e9 instead of MAX = 0 to save time. This works because 1e9 is represented exactly without errors.

This is a powerful technique which can be used to find floor of various function like sqrt or log. For example, to find largest long long x such that x * x <= N, I always write it as follows:

ll x = sqrt(N) - 1;
while (x * x <= N) x++;
x--;

This allows to compute sqrt in O(1) while I can be sure the value is correct without any floating-point shenanigans. Similarly for logs, just use while ((1 << x) <= N) x++;

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

use 1000000009 and 1000000000000000018, This can avoid counting the wrong number of 0.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

only after seeing testcase 13 where i got wrong then only i able to figure out this

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

how about using (1LL << 60)

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

You can use apostrophes in C++ integer literals, which is sometimes useful when you want to specify large constants. In this case it would be 1'000'000'000'000'000'001LL.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Those who use hex numbers to define infinity.

const int inf_32 = 0x3f3f3f3f;
const long long inf_64 = 0x3f3f3f3f3f3f3f3f;
→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).

→ Reply