An exercise

Sometimes, I feel like stretching my programming muscles.  A while ago, I read about this problem, or one like it.  It's not an especially hard problem, but I'd like to go over it anyway, because low-level data types can be unintuitive.

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:

1. 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.
2. You're working in two's complement, but overflow is still undefined.
3. 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).
4. You may throw an exception to indicate an overflow condition.

Actually think about this problem for a few minutes.  I'll put the solution after the break.  I really think most people who are likely to read this blog can solve this on their own, so please actually try this.

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!