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?

Answer 1

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.

Answer 2

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”).

Answer 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.