Does C guarantee 32-bit integer arithmetic?

Question

In C, suppose int is 32 bit,

uint64_t x = 1000000u * 1000000u;

this is commonly implemented by multiplying the numbers for a 32-bit result, discarding overflow bits, then assigning with zero extension to x.

Does the language guarantee this, or could the compiler instead choose to do everything in 64 bits, giving the mathematically accurate result?

(I know the language standard allows int to be 64 bit in the first place. I'm talking specifically about the situation where int is 32 bit.)

Answer 1

Yes, the Standard guarantees this—if the operands are 32 bits wide. In C11, the Standard 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 the number that is one greater than the largest value that can be represented by the resulting type.

This is reiterated in Annex H of C11:

C’s unsigned integer types are “modulo” in the LIA−1 sense in that overflows or out-of-bounds results silently wrap.

So, the result of an unsigned multiplication that overflows is to throw out the upper bits of the result.

If you do not want this behavior, the workaround is to write at least one constant as 1000000ULL, guaranteeing that the intermediate result will be promoted to at least 64 bits. You could also put an explicit cast in front of one of the operands, e.g. (uint_fast64_t)1000000, if you wanted.

If you want to guarantee it, write both operands as ((uint32_t)1000000UL). This type, if it exists, must be exactly 32 bits wide.

However, I do not recommend having your program depend implicitly on subtle implicit behavior that varies between implementations. You could make it much clearer to anyone maintaining it with code like:

static const uint32_t multiplicand = 1000000UL;
static const uint64_t product_low_word = multiplicand * multiplicand; // Upper 32 bits cleared.

Answer 2

Yes, assuming unsigned int is 32 bits.

Per 6.5.5 Multiplicative operators, paragraph 3:

The usual arithmetic conversions are performed on the operands.

Those conversions per 6.3.1.8 Usual arithmetic conversions are:

This pattern is called the usual arithmetic conversions:

• First, if the corresponding real type of either operand is long double, the other operand is converted, without change of type domain, to a type whose corresponding real type is long double.
• Otherwise, if the corresponding real type of either operand is double, the other operand is converted, without change of type domain, to a type whose corresponding real type is double.
• Otherwise, if the corresponding real type of either operand is float, the other operand is converted, without change of type domain, to a type whose corresponding real type is float.62)
• Otherwise, the integer promotions are performed on both operands. Then the following rules are applied to the promoted operands:
  • If both operands have the same type, then no further conversion is needed.
  • Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank is converted to the type of the operand with greater rank.
  • Otherwise, if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type.
  • Otherwise, if the type of the operand with signed integer type can represent all of the values of the type of the operand with unsigned integer type, then the operand with unsigned integer type is converted to the type of the operand with signed integer type.
  • Otherwise, both operands are converted to the unsigned integer type corresponding to the type of the operand with signed integer type.

Note "If both operands have the same type, then no further conversion is needed."

Since both operands are the same type - unsigned int, the result of your multiplication operation will be unsigned int for any conforming compiler.

EXAMPLE 2 from 5.1.2.3 Program execution is informative on how strictly arithmetic operations must be treated (EXAMPLE 6 is even better, but it's too long IMO to effectively quote):

EXAMPLE 2 In executing the fragment

      char c1, c2;
      /* ... */
      c1 = c1 + c2;

the ''integer promotions'' require that the abstract machine promote the value of each variable to int size and then add the two ints and truncate the sum. Provided the addition of two chars can be done without overflow, or with overflow wrapping silently to produce the correct result, the actual execution need only produce the same result, possibly omitting the promotions.

Answer 3

The operation 1000000u * 1000000u has precedence over the assignment and occurs independently of it. Where unsigned int is 32 bit, this will be a 32 bit unsigned result regardless of the type of x.

Answer 4

uint64_t x = 1000000u * 1000000u;

Your stated assumption is that int is 32 bits. To be 100% clear, we need to assume that UINT_MAX is 2³²-1, or 4294967295. (The standard requires unsigned int to have a range of at least 0 to 65535, which implies a size of at least 16 bits -- but it can have padding bits.) It's almost certainly the same thing (I don't know of any C implementations that have padding bits), but we should be explicit if we want to ask what the standard guarantees.

Given that assumption, the constant 1000000u is of type unsigned int, and the result of the multiplication is 3567587328u, also of type unsigned int. That value is converted to uint64_t (with no loss of information) and stored in x.

uint64_t is guaranteed to be exactly 64 bits wide with no padding bits. An implementation that doesn't have a type that satisfies those conditions will not define uint64_t, so the above wouldn't compile. (I'm assuming, of course, that this refers to the uint64_t defined in the standard <stdint.h> or <inttypes.h> header.)

The general rule for arithmetic expressions is that the type of an expression is determined by the types of its operands, not by the values of its operands or the context in which it appears. If we drop the assumption about the upper bound of unsigned int, the constant 1000000u could be of type unsigned int or unsigned long, whichever type is big enough to hold it -- but the value of the product is the same as the type of the constants, even if that results in overflow wraparound. (Strictly speaking, unsigned operations don't overflow.)

Answer 5

It's required to do it as modular arithmetic in whatever type unsigned is on the C implementation you're using. With your assumption that it's a 32-bit type, the result must be 32-bit. This would not necessarily apply in other superficially-similar examples where different type promotion rules might apply.