Question about C behaviour for unsigned integer underflow

Question

I have read in many places that unsigned integer overflow is well-defined in C unlike the signed counterpart.

Is underflow the same?

For example:

unsigned int x = -1; // Does x == UINT_MAX?

Thanks.

I can't recall where, but i read somewhere that arithmetic on unsigned integral types is modular, so if that were the case then -1 == UINT_MAX mod (UINT_MAX+1).

Solution 1

§6.2.5, paragraph 9:

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.

Edit:

Sorry, wrong reference, but the result is still pinned down. The correct reference is §6.3.1.3 (signed and unsigned integer conversion):

if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

So yes, x == UINT_MAX.

Solution 2

-1, when expressed as a 2's complement number, amounts to 0xFF...F for how ever many bits your number is. In an unsigned number space that value is the maximum value possible (i.e. all the bits are set). Therefore yes, x == UINT_MAX. The following code emits "1" on a C99 strict compiler:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main(int argc, char **argv){
  uint32_t x = -1;      
  printf("%d", x == UINT_MAX ? 1 : 0);
  return 0;
}

Comments

[WildCrustacean]

I believe that the term "underflow" is only really applicable to floating point numbers, where you can't represent some numbers very close to zero. Integers wouldn't have this issue.

[vicatcu]

@bde I agree that is a technically accurate statement, but the term is often overloaded for violation of the boundary condition on the bottom end of a number system.

[BlueRaja - Danny Pflughoeft]

Are twos-complement numbers required by the standard?

[Doug Currie]

No, 2s complement is not required by the standard, so this solution is not general; see my answer.

[Stephen Canon]

It may or may not be uncool, but it is perfectly well defined standard-conformant C.

[Doug Currie]

@Stephen Canon, Untrue. The bitwise representation of -1 is not defined. It could be ones complement, for example.

[Mark Ransom]

@Stepen, "standard-conformant" maybe, but "well defined"? That's the crux of the question.

[Doug Currie]

Your reference is fine, but not applicable since the expression -1 involves signed operands, not unsigned operands.

[Mark Ransom]

The question already admits that overflow is well defined. The question is about negative numbers, not positive.

[Stephen Canon]

The bitwise representation of -1 (or any signed integer) doesn't figure into it. §6.3.1.3 specifies the behavior.

[Stephen Canon]

@Doug, @Mark: The question is about conversions from signed to unsigned integers, which is specified by §6.3.1.3.

[BlueRaja - Danny Pflughoeft]

+1 for correct answer, §6.3.1.3 appears to be a very contorted way of requiring (unsigned int)(-1) == UINT_MAX without necessarily requiring signed numbers to use two's complement.

[Doug Currie]

@Stephen, thanks for being persistent (and for digging up 6.3.1.3); I stand corrected. Too bad about accepted answer stackoverflow.com/questions/50605/… "the internal representation of the number does not change"

[Doug Currie]

Thanks, Stephen, you are right. Lint likes my solution better, though. ;-)

[caf]

It is not required that the maximum value of uint32_t be UINT_MAX - UINT_MAX can be as small as 65535 and as large as ULONG_MAX. If you change that uint32_t to unsigned it will be correct.

[supercat]

@BlueRaja-DannyPflughoeft: It requires that the result of converting a negative number to unsigned is the same as subtracting the absolute value of that number from an unsigned zero, using the rule that X=Y-Z yields a unique value X such that X+Z==Y. Two's-complement has the useful property of being isomorphic to unsigned integers with regard to additive and multiplicative operators, but that's a case of two's-complement behavior following unsigned behavior, not vice versa.

[supercat]

Storing a negative number X in an n-bit unsigned storage space is required to store the smallest non-negative number which is congruent to X mod 2ⁿ. Since the bit pattern for any two's-complement signed number Y will either encode the unsigned value Y or Y+2ⁿ, both of which are congruent mod 2ⁿ, and one of which will be the smallest non-negative number which is congruent mod 2ⁿ, that means two's-complement numbers follow the behavior of unsigned integers--not vice versa.

[Thomas Weller]

This refers to §6.3.1.3 in which specification exactly? Sorry, I can't find it. Could we have a link, please?

[Stephen Canon]

@ThomasWeller: The prevailing C standard at the time that the answer was written: C99+TC3. (It's the same section in the newer C11 and C18 documents).