Unsigned arithmetic and integer overflow

Question

I am trying to understand arithmetic overflow. Suppose I have the following,

unsigned long long x;
unsigned int y, z;

x = y*z;

y*z can lead to an integer overflow. Does casting one of the operands to an unsigned long long alleviate this issue. What is the expected result of the multiplication of a 64-bit operand with a 32-bit operand?

Both operands are promoted to the wider type first if they're not of equal type. — Kerrek SB
– Kerrek SB, Commented Mar 10, 2014 at 22:41
From many examples I can tell it uses the bigger type for the result. So yeah, casting one of the operands will solve the problem. — MoonBun
– MoonBun, Commented Mar 10, 2014 at 22:42
@KerrekSB: That doesn't apply in this case. y and z are both unsigned int. — Keith Thompson
– Keith Thompson, Commented Mar 10, 2014 at 22:51
@KeithThompson: No (I think I said that?), that was just in response to the question... — Kerrek SB
– Kerrek SB, Commented Mar 10, 2014 at 22:53

Pascal Cuoq · Accepted Answer · 2014-03-10 22:42:43Z

5

You are clearly assuming that unsigned int is 32-bit and unsigned long long 64-bit. They don't have to be, be let us assume this.

A 64-bit operand that was obtain by converting a 32-bit operand still fits in 32 bits. Thus in y*(unsigned long long)z, where each of the operands is first promoted to unsigned long long, the result is computed as an unsigned long long and cannot “overflow”, because it is the multiplication of two quantifies that fit in 32 bits each.

(Also, in the vocabulary of the C standard, unsigned operations do not “overflow”. Overflowing is the undefined behavior of producing a result outside the bounds of the destination type. What unsigned operations do is “wrap around”).

answered Mar 10, 2014 at 22:42

Pascal Cuoq

80.6k8 gold badges168 silver badges293 bronze badges

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

Comments

Keith Thompson · Accepted Answer · 2014-03-10 22:57:51Z

unsigned long long x;
unsigned int y, z;

x = y*z;

The evaluation of the expression y*z is not affected by the context in which it appears. It multiplies two unsigned int values, yielding an unsigned int result. If the mathematical result cannot be represented as an unsigned int value, the result will wrap around. The assignment then implicitly converts the (possibly truncated) result from unsigned int to unsigned long long.

If you want a multiplication that yields an unsigned long long result, you need to explicitly convert one or both of the operands:

x = (unsigned long long)y * z;

or, to be more explicit:

x = (unsigned long long)y * (unsigned long long)z;

C's * multiplication operator applies only to two operands of the same type. Because of this, when you give it operands of different types, they're converted to some common type before the multiplication is performed. The rules can be a bit complex when you're mixing signed and unsigned types, but in this case if you multiply an unsigned long long by an unsigned int, the unsigned int operand is promoted to unsigned long long.

If unsigned long long is at least twice as wide as unsigned int, as it is on most systems, then the result will neither overflow nor wrap around, because, for example, a 64-bit unsigned long long can hold the result of multiplying any two 32-bit unsigned int values. But if you're on a system where, for example, int and long long are both 64 bits wide, you can still have ~~overflow~~ wraparound, giving you a result in x that's not equal to the mathematical product of y and z.

Mats Petersson · Accepted Answer · 2014-03-10 22:48:50Z

3

If one operand is wider than the other, the compiler should be (or behave as if it is) converting both operands to the same size, so casting one to a larger size will produce the correct behaviour.

This is specified in the C and C++ standards. The C++11 standard (n3337 draft) has this to say, in chapter five, statement 9:

... if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank shall be converted to the type of the operand with greater rank.

There is a couple of pages describing all the conversions and stuff that goes on, but this is what defines this particular expression's behaviour.

edited Mar 10, 2014 at 22:48

answered Mar 10, 2014 at 22:41

Mats Petersson

130k15 gold badges147 silver badges233 bronze badges

8 Comments

Kerrek SB Over a year ago

This isn't the compiler's fault, though. The language demands this behaviour.

Mats Petersson Over a year ago

Yes, wording altered to reflect this and quote from standard document provided.

Kerrek SB Over a year ago

Beautiful. Once we have the wording from the standard, it's almost like we never need to talk about compilers at all :-) (The subject is already way too complicated as it is, without bringing in all the periphery!)

Keith Thompson Over a year ago

How does that apply in this case? Both y and z are of type unsigned int.

Kerrek SB Over a year ago

@KeithThompson: The OP asks if casting one value to unsigned long long helps.

|

Collectives™ on Stack Overflow

Unsigned arithmetic and integer overflow

3 Answers 3

Comments

Comments

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related