Unsigned integer overflow detection

[Raymond]

Source:
http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html

Example from source:

char unsigned augend (255);
char unsigned const addend (255);
char unsigned const sum (augend + addend);

if (sum < augend)
{
std:uts ("Overflowed!");
}

sum = augend + addend
sum = 255 + 255
sum = 510 modulo 256 // Behind the scenes.
sum = 254

Does it touch any implementation defined or undefined behaviour, or was
that specific to signed integers (on some platforms)?

What other methods are there for detecting unsigned integer overflow
and/or underflow in C++?

 

[Alf P. Steinbach]

* Raymond:

Source:
http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html

Example from source:

char unsigned augend (255);
char unsigned const addend (255);
char unsigned const sum (augend + addend);

if (sum < augend)
{
std:uts ("Overflowed!");
}

sum = augend + addend
sum = 255 + 255
sum = 510 modulo 256 // Behind the scenes.
sum = 254

Does it touch any implementation defined or undefined behaviour, or was
that specific to signed integers (on some platforms)?

In C++ unsigned integer arithmetic is defined as modulo 2^n, where n is
the number of bits.

What other methods are there for detecting unsigned integer overflow
and/or underflow in C++?

Generally you don't.

If you want range checking you can check if your compiler provides range
checking for signed integer types, or you can implement a range-checked
integer type as a class, like

class CheckedInt
{
private:
int myValue;
public:
CheckedInt( int v = 0 ): myValue( v ) {}

int intValue() const { return myValue; }

CheckedInt operator+( CheckedInt const& other ) const
{
int const a = intValue();
int const b = other.intValue();
int const result = a + b;

// Assuming two's complement form:
if( (a < 0) == (b < 0) && (result < 0) != (a < 0) )
{
throw std::something_blah_blah();
}
return result;
}
};

Quite possibly there are existing such classes freely available on the
net -- Google (and please report results of that search here! ).

Cheers, & hth.,

- Alf

 

[Neelesh Bodas]

Source:http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when....

Example from source:

char unsigned augend (255);
char unsigned const addend (255);
char unsigned const sum (augend + addend);

if (sum < augend)
{
std:uts ("Overflowed!");

}

sum = augend + addend
sum = 255 + 255
sum = 510 modulo 256 // Behind the scenes.
sum = 254

Does it touch any implementation defined or undefined behaviour, or was
that specific to signed integers (on some platforms)?

3.9.1(4): Unsigned integers, declared unsigned, shall obey the laws of
arithmetic modulo 2^n where n is the number of bits in the value
representation of that particular size of integer

Footnote: 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.

Thus the only implementation-defined aspect in your example is the
value of 'n'. A 'char' is not necessarily 8 bit entity, and hence n
neednot be 8.

What other methods are there for detecting unsigned integer overflow
and/or underflow in C++?

There are no overflows possible for unsigned integer arithmetic. The
question of "underflow" doesnot arise since it is "unsigned"
arithmetic.

-N

 

[Victor Bazarov]

Source:
http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html

Example from source:

char unsigned augend (255);
char unsigned const addend (255);
char unsigned const sum (augend + addend);

if (sum < augend)
{
std:uts ("Overflowed!");
}

sum = augend + addend
sum = 255 + 255
sum = 510 modulo 256 // Behind the scenes.
sum = 254

Does it touch any implementation defined or undefined behaviour, or
was that specific to signed integers (on some platforms)?

No, the behaviour is well-defined. All arithmetic operations with
unsigned values work modulo 2^N, where N is the number of bits in
the representation of the number.

What other methods are there for detecting unsigned integer overflow
and/or underflow in C++?

If you look in the archives (use Google Groups interface, e.g.), you
should find that unsigned does not overflow. There is no such thing
as "underflow" AFA integers are concerned, IIUIC.

There is no way to "detect" it in the current language. There is only
a way to "predict" it:

unsigned a = UINT_MAX - 2, b = UINT_MAX - 3; // or whatever
if (UINT_MAX - a < b)
std::cout << "Adding " << a << " to " << b
<< " would \"overflow\"\n";

V

 

[Alf P. Steinbach]

* Neelesh Bodas:

There are no overflows possible for unsigned integer arithmetic. The
question of "underflow" doesnot arise since it is "unsigned"
arithmetic.

Just a nit, but at least as far as the terminology I've been exposed to
(for some decades), "underflow" is strictly a non-integer representation
phenomenon. Integers just overflow, whether that's towards positive or
negative infinity. I.e., "overflow" and "underflow" refer to the
absolute value, not the sign.

 

[Neelesh Bodas]

* Neelesh Bodas:




Just a nit, but at least as far as the terminology I've been exposed to
(for some decades), "underflow" is strictly a non-integer representation
phenomenon. Integers just overflow, whether that's towards positive or
negative infinity. I.e., "overflow" and "underflow" refer to the
absolute value, not the sign.

Agreed. (But had to refer to wikipedia for that !!). so that would
make a very small change in my reply:
The question of "underflow" doesnot arise since it is unsigned
"integer" arithmetic

(Just a slip-of-quote)
-N

 

[Raymond]

* Raymond:

In C++ unsigned integer arithmetic is defined as modulo 2^n, where n is
the number of bits.

Yes, correct, but in my haste I left out *why* I felt unsure/asked these
questions, and I think I found the part that I had read before; section
1.9 15, where overflows triggering exceptions are mentioned with regards
to integers, or signed integers if the example is to be taken literally.

If you want range checking you can check if your compiler provides range
checking for signed integer types, or you can implement a range-checked
integer type as a class, like

Quite possibly there are existing such classes freely available on the
net -- Google (and please report results of that search here! ).

There is only so much time one can spend searching before beginning to
think again..

Anyway, thanks, but I think you made this a lot more complex than it
needed to be, at least for me. Existing classes? Perhaps, but for such
a small problem, that doesn't sound like the solution for me.

It wasn't easy for me to find something concrete on this subject, and I
tried finding other solutions after this one. The paper on Stroustrup's
page, also linked to from the article, only dealt with signed integers,
as your example did.

 

[Raymond]

No, the behaviour is well-defined. All arithmetic operations with
unsigned values work modulo 2^N, where N is the number of bits in
the representation of the number.
Yes.


If you look in the archives (use Google Groups interface, e.g.), you
should find that unsigned does not overflow. There is no such thing
as "underflow" AFA integers are concerned, IIUIC.

My current point of view on this; an overflow comes from adding too
much; an "underflow" comes from subtracting too much. An overflow in the
general sense does not explain whether too much was added or subtracted,
just that information was lost; it doesn't include how it happened.

There is no way to "detect" it in the current language. There is only
a way to "predict" it:

unsigned a = UINT_MAX - 2, b = UINT_MAX - 3; // or whatever
if (UINT_MAX - a < b)
std::cout << "Adding " << a << " to " << b
<< " would \"overflow\"\n";

What do you mean? The source code I linked to detects it fine, and it
appears to be fully portable. No need to think about the underlying
binary interpretation of signed integers, or exceptions either apparently.

 

[Raymond]

3.9.1(4): Unsigned integers, declared unsigned, shall obey the laws of
arithmetic modulo 2^n where n is the number of bits in the value
representation of that particular size of integer

Footnote: 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.
Yes.

Thus the only implementation-defined aspect in your example is the
value of 'n'. A 'char' is not necessarily 8 bit entity, and hence n
neednot be 8.

As mentioned in the article too, I might add, but we're busy people.

There are no overflows possible for unsigned integer arithmetic. The
question of "underflow" doesnot arise since it is "unsigned"
arithmetic.

Yes, but if you wanted to detect an overflow, then there is an overflow,
because it is now defined as adding too much, resulting in loss of
information due to a limited container. Same goes for underflow.