Simple Trick to Detect Integer Overflow (C/C++)

[harshraj22]

Don’t know if problem is with my internet or the website, but I can’t open it.

[ssjgz]

Hmmm … strange. Anyway, here’s a copy-n-paste of it:

// Simon St James (ssjgz) - 2020-XX-XX
// 
// Solution to: TODO - problem link here!
//
//#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#else
#define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
#pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
#endif
#include <iostream>
#include <vector>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

#if 0
SolutionType solveBruteForce()
{
    SolutionType result;
    
    return result;
}
#endif

#if 0
SolutionType solveOptimised()
{
    SolutionType result;
    
    return result;
}
#endif


int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
        // TODO - generate randomised test.
        //const int T = rand() % 100 + 1;
        const int T = 1;
        cout << T << endl;

        for (int t = 0; t < T; t++)
        {
        }

        return 0;
    }
    
    // TODO - read in testcase.
    const auto T = read<int>();

    for (int t = 0; t < T; t++)
    {

#ifdef BRUTE_FORCE
#if 0
        const auto solutionBruteForce = solveBruteForce();
        cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 0
        const auto solutionOptimised = solveOptimised();
        cout << "solutionOptimised:  " << solutionOptimised << endl;

        assert(solutionOptimised == solutionBruteForce);
#endif
#else
        const auto solutionOptimised = solveOptimised();
        cout << solutionOptimised << endl;
#endif
    }

    assert(cin);
}

[nihith123]

while submitting solution should we comment this line #define _GLIBCXX_DEBUG?

[ssjgz]

In my template? Assuming I haven’t made a mistake, it should be enough to just uncomment the

//#define SUBMISSION

Obviously, only do this when you’ve finished debugging and are sure your solution is correct

[nihith123]

Yeah thanks @ssjz

[rahul_g]

The performance impact is noticeable
NwF8je - Online C++0x Compiler & Debugging Tool - Ideone.com (with)
l2fSzm - Online C++0x Compiler & Debugging Tool - Ideone.com (without)

[ssjgz]

Great - thanks for doing the experiment and providing some hard numbers

[everule1]

I’m trying to use the

#pragma GCC optimize "trapv"

But when i use the following code

#pragma GCC optimize "trapv"
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
        int a=10000000,b=1000000000;
        cout<<a<<" "<<b<<'\n';
        int f=a*b;
        cout<<f;
}

It’s not crashing. How do I use it correctly?

[ssjgz]

@everule1

It’s not crashing. How do I use it correctly?

Interesting - it’s not crashing for me, either. However:

[simon@simon-laptop][17:53:24]
[~/devel/hackerrank/otherpeoples]>cat everule1-ftrapv-test.cpp 
#pragma GCC optimize "trapv"
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
        int a,b;
        cin >> a >> b;
        cout<<a<<" "<<b<<'\n';
        int f=a*b;
        cout<<f;
}

[simon@simon-laptop][17:53:32]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++14 everule1-ftrapv-test.cpp  -O3
[simon@simon-laptop][17:53:37]
[~/devel/hackerrank/otherpeoples]>echo "10000000 1000000000" | ./a.out
10000000 1000000000
Aborted (core dumped)

crashes as expected.

I’d guess that with the original version, the compiler is computing the result of a * b at compile-time, and so not triggering the runtime error.

[everule1]

Okay thanks, I thought i was using it incorrectly.

[aneee004]

@ssjgz

#pragma GCC optimize "trapv"

Is it safe to submit with this optimization? I read someplace that this increases runtime. Increased runtime is fine as long as it don’t give TLE.

[ssjgz]

Simple Trick to Detect Integer Overflow (C/C++) - #16 by rahul_g

[aneee004]

What do you guys use for a long long infinity?
I generally use int INF = 987654321 for an int infinity. This works everytime, but when I used a random INF value for long long infinity, I got a WA. So I ended up using LLONG_MAX, and whenever I did a = b + c, I had to do this instead.

[Random as in not rand(), some random large value]

if(b == LLONG_MAX or c == LLONG_MAX) a = LLONG_MAX
else a = b + c

Having a long long infinity can make this so much simpler.

[everule1]

1e18. You can add without overflows

[spaanse]

I often use (1<<29) as an infinity value for int, and would probably use something like (1LL<<60) for a long long infinity.

[l_returns]

Wow thank you so much such an awesome post.
You deserve 10 likes from each user.

[ssjgz]

Sadly, there’s a pretty big flaw in it discovered in this thread:

Dementia rated contest - Problem Code: TOWIN

Can any one please tell me what’s going wrong??? #include <bits/stdc++.h> using namespace std; #define endl ("\n") #define pi (3.141592653589) #define mod 1e9+7 #define ll long long #define rfo(i, n) for(int i = n-1; i >=0; i--) #define fo(i, n) for(int i = 0; i < n; i++) #define ifo(i, k, n) for(int i = k; i < n; i++) #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); void solve(); int main() { fast // Forget ratin…

(see the Important Update in the OP)

[l_returns]

Will need to read about it a bit more. I am sure it will be useful otherwise it won’t be available in the first place. Just need to figure out when and why.

[ssjgz]

Yes, I suppose: I’ve been using it for ages, and this situation is the first I’ve seen where it breaks

[sampras123]

Can you please. explain where it fails I am not able to get the program