Is unsigned integer subtraction behavior defined?

Question

I met the code from someone who seems to think that the problem subtracts an unsigned integer from another integer of the same type when the result is negative. Thus, such code would be incorrect even if it works on most architectures.

unsigned int To, Tf; To = getcounter(); while (1) { Tf = getcounter(); if ((Tf-To) >= TIME_LIMIT) { break; } } 

This is the only vaguely relevant quote from standard C. I could find.

Computing using unsigned operands can never exceed the stream, because a result that cannot be represented by an unsigned integer type decreases modulo a number that is greater than one largest value that can be represented by the resulting type.

I suggest that this quote can be taken to mean that when the right operand is larger, the operation is adjusted to make sense in the context of truncated numbers modulo.

i.e.

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

as opposed to using implementation-dependent semantics:

0x0000 - 0x0001 == (unsigned) (0 + -1) == (0xFFFF, as well as 0xFFFE or 0x8001)

Which or which interpretation is correct? Is it determined at all?

Answer 1

A subtraction result generating a negative number in an unsigned type is clearly defined:

• [...] Computing using unsigned operands can never overflow, because a result that cannot be represented by an unsigned integer type is equal in absolute value to a number that is greater than one largest value that can be represented by a result type. (ISO / IEC 9899: 1999 (E) §6.2.5 / 9).

As you can see, (unsigned)0 - (unsigned)1 is -1 modulo UINT_MAX + 1, or, in other words, UINT_MAX.

Please note that although he says: “Computing using unsigned operands can never overflow”, which may make you believe that it is only used to exceed the upper limit, this is presented as a motivation for the actual mandatory part of the sentence: “a result that does not can be represented by a resultant unsigned integer type, equal in magnitude the number is reduced, which is greater than one largest value that can be represented by the resultant type. " This phrase is not limited to overflowing the upper bound of the type and applies equally to values ​​too low for presentation.

Answer 2

When you work with unsigned types, modular arithmetic (also known as the wrap behavior) occurs. To understand this modular arithmetic, just take a look at this watch:

9 + 4 = 1 (13 mod 12), so in the other direction it is: 1 - 4 = 9 (-3 mod 12). The same principle applies when dealing with unsigned types. If the result type unsigned , then modular arithmetic takes place.

---

Now, consider the following operations that save the result as an unsigned int :

 unsigned int five = 5, seven = 7; unsigned int a = five - seven; // a = (-2 % 2^32) = 4294967294 int one = 1, six = 6; unsigned int b = one - six; // b = (-5 % 2^32) = 4294967291 

If you want to make sure the result is signed , then save it in the signed variable or translate it into signed . If you want to get the difference between numbers and make sure that modular arithmetic is not applied, you should use the abs() function defined in stdlib.h :

 int c = five - seven; // c = -2 int d = abs(five - seven); // d = 2 

Be very careful, especially when recording conditions, because:

 if (abs(five - seven) < seven) // = if (2 < 7) // ... if (five - seven < -1) // = if (-2 < -1) // ... if (one - six < 1) // = if (-5 < 1) // ... if ((int)(five - seven) < 1) // = if (-2 < 1) // ... 

but

 if (five - seven < 1) // = if ((unsigned int)-2 < 1) = if (4294967294 < 1) // ... if (one - six < five) // = if ((unsigned int)-5 < 5) = if (4294967291 < 5) // ... 

Answer 3

Well, the first interpretation is correct. However, your discussion of "signed semantics" in this context is incorrect.

Again, your first interpretation is correct. Unsigned arithmetic follows the modulo arithmetic rules, which means that 0x0000 - 0x0001 is evaluated to 0xFFFF for 32-bit unsigned types.

However, a second interpretation (based on "signed semantics") is also required to obtain the same result. That is, even if you evaluate 0 - 1 in a domain of a signed type and get -1 as an intermediate result, this -1 is still required to create 0xFFFF , when it is later converted to an unsigned type. Even if an exotic representation for signed integers is used on any platform (1 addition, signed value), this platform should still apply modular arithmetic rules when converting signed integer values ​​to unsigned ones.

For example, this rating

 signed int a = 0, b = 1; unsigned int c = a - b; 

still guaranteed to create UINT_MAX in c , even if the platform uses an exotic representation for signed integers.

Answer 4

With unsigned numbers of type unsigned int or more, in the absence of type conversions, ab is defined as specifying an unsigned number that, when added to b will give a . Converting a negative number to unsigned is defined as specifying a number that, when added to the original number with the opposite sign, will be zero (therefore, converting -5 to unsigned will lead to a value that, when added to 5, will lead to zero).

Note that unsigned numbers smaller than unsigned int can be upgraded to int before subtraction, the behavior of ab will depend on the size of int .