34

I'm reading an article about integer security. On page 166 it says:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo to the number that is one greater than the largest value that can be represented by the resulting type.

What does this mean?

Improve this question
3
  • 16
    That's.. misleading. It overflows. But it does so in a defined way, namely by wrapping in the way they explain. Commented Apr 17, 2013 at 9:48
  • 4
    @harold: That's a matter of semantics. For example, the authors of the C++ standard say that it doesn't overflow, because modular arithmetic keeps the result within range; they only use the term to describe signed overflow, which is an error giving undefined behaviour. Commented Apr 17, 2013 at 9:57
  • 1
    @harold It is from n1570 standard §6.2.5/9 Commented Feb 10, 2017 at 4:57

4 Answers 4

Reset to default
50

It means the value "wraps around".

UINT_MAX + 1 == 0
UINT_MAX + 2 == 1
UINT_MAX + 3 == 2

.. and so on

As the link says, this is like the modulo operator: http://en.wikipedia.org/wiki/Modulo_operation

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I know signed overflow is undefined behavior, but wouldn't it too wrap around?
@0x499602D2 On most hardware it does, although the compiler can make optimizations which won't.
It's just like an old-style car odometer. If it only reads up to 999,999 miles, then one more mile brings it back to zero.
Where is that defined in the C++ standard?
@Pubby, I think it's important to point out that in recent years compilers have become a lot more aggressive about optimizing assuming that signed integer overflow will not happen. A decade or two ago, you could leave optimizations off and kind of ignore the undefined behavior because it would work on most machines. These days, at least some compilers will actively break your code if you ignore the fact that signed integer overflow is undefined. However, the gcc option -fwrapv does make signed overflow defined, if you want it. It is non-standard so I would not recommend in general code.
8

No overflow?

"Overflow" here means "producing a value that doesn't fit the operand". Because arithmetic modulo is applied, the value always fits the operand, therefore, no overflow.

In other words, before overflow can actually happen, C++ will already have truncated the value.

Modulo?

Taking a value modulo some other value means to apply a division, and taking the remainder.

For example:

0 % 3 = 0  (0 / 3 = 0, remainder 0)
1 % 3 = 1  (1 / 3 = 0, remainder 1) 
2 % 3 = 2  (2 / 3 = 0, remainder 2)
3 % 3 = 0  (3 / 3 = 1, remainder 0)
4 % 3 = 1  (4 / 3 = 1, remainder 1)
5 % 3 = 2  (5 / 3 = 1, remainder 2)
6 % 3 = 0  (6 / 3 = 2, remainder 0)
...

This modulo is applied to results of unsigned-only computations, with the divisor being the maximum value the type can hold plus one. E.g., if the maximum is 216 - 1 = 65535, then 65530 + 6 = (65530 + 6) % 216 = 0.

Improve this answer

Comments

6

It means that you can't alter the sign of a unsigned calculation, but it can still produce unexpected results. Say we have an 8-bit unsigned value:

 uint8_t a = 42;

and we add 240 to that:

 a += 240;

it will not fit, so you get 26.

Unsigned math is clearly defined in C and C++, where signed math is technically either undefined or implementation dependent or some other "things that you wouldn't expect may happen" wording (I don't know the exact wording, but the conclusion is that "you shouldn't rely on the behaviour of overflow in signed integer values")

Improve this answer

6 Comments

Wording: "implementation defined behaviour", when a compiler shall document behaviour, and "undefined behaviour", where compilers can do what they want. edit: Oh and, "clearly defined" would be "well defined" in C++ parlance :)
I think there is (at least) a third one which is something like "implementation detail", but my point was rather that I don't know which level of "it's not certain what happens here" that signed integer math ends up under - does it allow just "strange results" or "anything could happen" (e.g. what happens if the processor has an overflow trap that fires on integer overflow?)
"implementation detail" would be "implementation defined" in C++ parlance. Without reviewing the standard, I think overflowing signed values results in undefined behaviour.
I was under the impression there is a subtle difference: "implementation defined" means that the compiler producer has to tell you what they do. "implementation detail" means "it's up to the compiler producer, and there is no need to explain that it is". Either way, "don't overflow signed integers" is the conclusion.
@phresnel, I understand, this was long time ago, but "no need to explain" is "unspecified behaviour", unlike "undefined" one it produces sane results, which may still differ.
|
0

One more example to show unsigned data type wraps around instead of overflow:

unsigned int i = std::numeric_limits<unsigned int>::max(); // (say) 4294967295

Assigning a -ve number to the unsigned is not recommended but for the illustrative purpose, I'm using it below

unsigned int j = -1; // 4294967295 wraps around(uses modulo operation)
unsigned int j = -2; // 4294967294

Visualizing the unsigned (0 to max) range with respect to the modulo of max+1 (where max = 2^n):

Range         :         0,     1,        2,.......,     max-2,   max-1,       max
.................................................................................
Last-to-First :  -(max+1),  -max, -(max-1),.......,        -3,      -2,        -1

First-to-Last :     max+1, max+2,    max+3,......., max+max-1, max+max, max+max+1

Modulo Addition Rule: (A + B) % C = (A % C + B % C) % C

[max + max + 1] % (max + 1) = [(max) + (max + 1)] % (max + 1)
                            = [(max % (max + 1)) + ((max + 1) % (max + 1))] % (max + 1)
                            = [(max % (max + 1)) + 0] % (max + 1)
                            = [max] % (max + 1) 
                            = max
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.