Saturday, August 18, 2007

Detecting overflow/underflow when adding/subtracting unsigned integers in C++

Assume three unsigned integers of the same type. In these examples, the type is char unsigned, but it can be any other unsigned integer type. In these examples, UCHAR_MAX is 255.

(Observe that, in any unsigned integer addition, where the highest possible value (2n − 1) is added to itself, the result is 2n − 1 + 2n − 1 = 2n − 2 where n is at least 8 or more in this context.)

Adding unsigned integers of the same type

When the sum is less than the augend then the sum is the result of an overflow.
char unsigned augend (UCHAR_MAX);
char unsigned const addend (UCHAR_MAX);
char unsigned const sum (augend + addend);

if (sum < augend)
{
std::puts ("Overflowed!");
}
sum = augend + addend
sum = 255 + 255
sum = 510 modulo 256 // Behind the scenes.
sum = 254

In the event of an unsigned integer overflow, the sum will always be less than the augend. In this example, an overflow occured because the sum (254) is less than the augend (255).

Subtracting unsigned integers of the same type

When the difference is greater than the minuend then the difference is the result of an underflow.
char unsigned minuend (0);
char unsigned const subtrahend (1);
char unsigned const difference (minuend − subtrahend);

if (difference > minuend)
{
std::puts ("Underflowed!");
}
The C++ standard (ISO 14882:2003): "Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2n where n is the number
of bits in the value representation of that particular size of integer." + "This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type."

The original test program
#include <climits>
#include <cstdio>

void addition ()
{
char unsigned augend (0);
char unsigned const addend (1);
char unsigned sum;

for (int loop_count (0); loop_count < INT_MAX; ++loop_count)
{
sum = augend + addend;

if (sum < augend) // Unsigned integer overflow?
{
std::printf ("[%3d] %3u + %u = %u (Overflowed!)\n", loop_count, augend, addend, sum);
break;
}
else
{
std::printf ("[%3d] %3u + %u = %u\n", loop_count, augend, addend, sum);
augend = sum;
}
}
}

void subtraction ()
{
char unsigned minuend (UCHAR_MAX);
char unsigned const subtrahend (1);
char unsigned difference;

for (int loop_count (0); loop_count < INT_MAX; ++loop_count)
{
difference = minuend - subtrahend;

if (difference > minuend) // Unsigned integer underflow?
{
std::printf ("[%3d] %3u - %u = %u (Underflowed!)\n", loop_count, minuend, subtrahend, difference);
break;
}
else
{
std::printf ("[%3d] %3u - %u = %u\n", loop_count, minuend, subtrahend, difference);
minuend = difference;
}
}
}

int main ()
{
addition ();
subtraction ();
}
To handle signed integers, see the pages of Bjarne Stroustrup. One method is demonstrated on pages 12 and 13 in the paper Abstraction and the C++ machine model [PDF].

(Motivation for this post) I looked but I could not find a simple technique to check whether an unsigned integer overflowed in C++, and here it is. As a bonus, the opposite allows checking for underflows.

No comments: