How do you handle a binary overflow?

Answer 1

When adding two signed integrals (x and y) of the same type, the result cannot overflow when they have opposing signs. The result can only be x or y or somewhere in between, and all values in the range x to y are valid regardless of which is the larger. But when they have the same sign, there is a potential for overflow. Given that x + y = z has well-defined behaviour, we can perform the following pseudocode operations to test for an overflow in z:

if x=0 or y=0 then overflow:=false

else if x<0 and y>0 then overflow:=false

else if x>0 and y<0 then overflow:=false

else if x<0 and z>0 then overflow:=true

else if x>0 and z<0 then overflow:=true

else overflow:=false

The following example shows how we can implement this in C:

// Returns true if x + y = z overflows

bool int_sum_overflow (int x, int y, int z) {

if (!x !y (x<0 && y>0) (x>0 && y<0)) return false; return (x<0 && z>0) (x>0 && z<0);

}

When dealing with unsigned integrals, we must test the operation before we perform the operation. This is because overflowing an unsigned integral has undefined behaviour in much the same way that division by zero has undefined behaviour. If we perform the operation first and an overflow occurs, then it's already too late; undefined behaviour has unpredictable consequences. If we're lucky, our program will simply crash and no harm will be done. If not, we have no way of knowing what has happened. Even if our specific implementation provides well-defined behaviour, it cannot be guaranteed across all architectures and cannot be regarded as being portable. Where undefined behaviour is concerned, prevention is always better than cure.

Fortunately, x + y = z is relatively simple to test without the need to evaluate z first. Given that z cannot exceed the maximum unsigned integral without overflowing, it follows that if max - x were less than y then the result will overflow. This can be stated as follows:

if (max-x)<y then overflow:=true

else overflow:=false

Given that max is a well-defined constant, this is trivial to implement. The following example shows how we might implement this in C:

#include<limits.h> // for UINT_MAX

// Returns true if the sum of x and y would overflow:

bool uint_sum_overflow (unsigned x, unsigned y) {

return (UINT_MAX - x) < y;

}

The above examples deal with addition only but we can perform similar tests for subtraction and multiplication operations. Aside from divide by zero, integral division operations present no major problems, although most divisions will result in a truncation of any fractional component.

If we want to improve efficiency then we really have to lift the bonnet and use assembly programming. In the case of unsigned integral addition, we need to test the carry bit in the most significant bit-adder. For signed integrals we need to test both carry out and the carry in bits of the most-significant bit-adder.