Suppose you have two integers

*a*and

*b*. You want to add them, but you also want to be sure they don't overflow. You're working in a language where overflow is undefined, such as C. You can't use arbitrary precision variables or anything fancy like that, nor can you make use of low-level things like CPU overflow detection. You need to guard against overflow

*mathematically*, without the use of any of those systems. Maybe you're working on a reduced architecture that doesn't provide overflow detection. Maybe your language or library is deficient and lacks an arbitrary precision integer type. It doesn't really matter. The point is, taking away all those "outs", we're left with a somewhat interesting problem.

Here are some assumptions you may make:

- You have a constant called
`INT_MAX`

which is equal to the largest integer which can be represented on your system. You also have another called`INT_MIN`

, which serves a similar purpose for the smallest (most negative) integer. - You're working in two's complement, but overflow is still undefined.
- You
*do not*have the exact number of bits available (but you could figure it out from`INT_MAX`

, so that's not much of a restriction). - You may throw an exception to indicate an overflow condition.

Here's the solution:

int safeAdd(int a, int b){ const int halfMax = INT_MAX/2; //rounded down since INT_MAX is odd const int halfMin = INT_MIN/2; //First, check if they're too big: if(a > halfMax && b > halfMax){ throw overflowException(); } if((a == INT_MAX && b > 0) || (b == INT_MAX && a > 0)){ throw overflowException(); } if(a > halfMax){ a -= halfMax; // make a small enough to add it to b if(a + b > halfMax){ throw overflowException(); } return a + b + halfMax; } if(b > halfMax){ b -= halfMax; if(a + b > halfMax){ throw overflowException(); } return a + b + halfMax; } //They're not too big. Check if they're too small: if(a < halfMin && b < halfMin){ throw underflowException(); } if(a < halfMin){ a -= halfMin; //halfMin is negative, so this *increases* a if(a + b < halfMin){ throw underflowException(); } return a + b + halfMin; } if(b < halfMin){ b -= halfMin; if(a + b < halfMin){ throw underflowException(); } return a + b + halfMin; } //They're neither too big nor too small, so: return a + b; }

The second if statement looks redundant to the third and fourth, and is not mirrored in the negatives section. Determining its purpose is left as an exercise for the reader.

Disclaimer: While I have put a fair amount of thought into the above code, I have

*not*tried it, so use it at your own peril!