4 ms·

What is the reasoning behind the fact that, say, (INT_MAX + 1) != INT_MIN?

Tuna-Fish 14y ago
At the time of the introduction of C, there were plenty of different architectures that used different kinds of signed integer representations. C was evolved to be the "lowest common denominator", so things that operated differently on different hardware were made undefined to preserve portability.
- vilda 14y ago
  Fair to say the number of architectures increased since the introduction of C...
rpearl 14y ago
Two's complement is not required; there might be systems that use saturating signed arithmetic for example.
- matheusalmeida 14y ago
  That is true but it's not the reason... INT_MAX + 1 must be 0 for unsigned int because the C standard defines wrap-around behavior for unsigned data types. Saturated data types are only defined in Embedded C. E.g.: Sat Fract
  - jacquesgt 14y ago
    That is the entire reason. Because the representation of signed numbers could vary from implementation to implementation, making INT_MAX + 1 (or any signed integer overflow) undefined allows for more efficient generated code. If it were defined in some way, the generated code would need checks for overflow wherever it was possible, which would lead to bigger and slower code. INT_MAX + 1 is never 0 for unsigned int. (unsigned)INT_MAX + 1 is equal to INT_MAX + 1. You're thinking of UINT_MAX + 1, which is always 0.
    - caf 14y ago
      It's not true that (unsigned)INT_MAX + 1 is never 0 - it's allowed for UINT_MAX == INT_MAX (leaving the sign bit unused in the unsigned representation). I've never seen such an implementation, though.
      - jacquesgt 14y ago
        Yep, you're right.
    - matheusalmeida 14y ago
      Yes, my mistake. I meant UINT_MAX + 1.
  - gegenschall 14y ago
    There is a somewhat related text by Fefe: http://www.fefe.de/intof.html http://www.fefe.de/intof.html
deleted 14y ago
[deleted]
matheusalmeida 14y ago
That would be true for unsigned data types. The C Standard specifies as 'undefined behavior' overflow for signed types. The C compiler can do whatever it wants...
Someone 14y ago
Some reasons (the first one being the most important one): 1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...) 2. To make C usable for those worried about erroneous overflows in their code. 3. To make it easier to write C compilers for CPUs that trap on integer overflow. 4. To allow for performant C compilers on CPUs that use one's complement arithmetic.
- cliffbean 14y ago
  > 1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-... http://blog.llvm.org/2011/05/what-every-c-programmer-should-...) I'm curious about this. See below. > 2. To make C usable for those worried about erroneous overflows in their code. I think you're saying that the rule allows compilers to implement -fwrapv if they choose, which sounds reasonable. > 3. To make it easier to write C compilers for CPUs that trap on integer overflow. > 4. To allow for performant C compilers on CPUs that use one's complement arithmetic. I wonder how much these matter nowadays. For optimization, the blog post you cite describes the following examples: - "X+1 > X" to true - "X*2/2" to "X" - "<= loops" and "int" induction variables On the first two, presumably these usually only come up after macro expansion and inlining, however they're still suspicious. If a function is scaling its return value and its caller is de-scaling it, it's usually a sign that the API isn't designed quite right. I'd be curious to know how often these come up. Code using "int" induction variables to step through arrays on 64-bit targets is often sloppy. Such code won't handle very large arrays properly, due to the limited range of "int", which is a bug that may not be quickly noticed. And for the "<= loop" itself: for (i = 0; i <= N; ++i) { ... } it's really unlikely that the code is actually intended to be an infinite loop in the case where N happens to be INT_MAX. Code like this would usually be clearer written as "i < N + 1" to emphasize that it really does intend to iterate N+1 times rather than just N times, and it just so happens that this form makes optimizers happier as well. Instead of having compiler writers sit around and think up clever ways to repurpose anachronistic language rules, I might prefer to have them focus instead on ways they can help me write better code instead :-).

At the time of the introduction of C, there were plenty of different architectures that used different kinds of signed integer representations. C was evolved to be the "lowest common denominator", so things that operated differently on different hardware were made undefined to preserve portability.

vilda 14y ago
Fair to say the number of architectures increased since the introduction of C...

rpearl 14y ago

Two's complement is not required; there might be systems that use saturating signed arithmetic for example.

matheusalmeida 14y ago
That is true but it's not the reason... INT_MAX + 1 must be 0 for unsigned int because the C standard defines wrap-around behavior for unsigned data types. Saturated data types are only defined in Embedded C. E.g.: Sat Fract
- jacquesgt 14y ago
  That is the entire reason. Because the representation of signed numbers could vary from implementation to implementation, making INT_MAX + 1 (or any signed integer overflow) undefined allows for more efficient generated code. If it were defined in some way, the generated code would need checks for overflow wherever it was possible, which would lead to bigger and slower code. INT_MAX + 1 is never 0 for unsigned int. (unsigned)INT_MAX + 1 is equal to INT_MAX + 1. You're thinking of UINT_MAX + 1, which is always 0.
  - caf 14y ago
    It's not true that (unsigned)INT_MAX + 1 is never 0 - it's allowed for UINT_MAX == INT_MAX (leaving the sign bit unused in the unsigned representation). I've never seen such an implementation, though.
    - jacquesgt 14y ago
      Yep, you're right.
  - matheusalmeida 14y ago
    Yes, my mistake. I meant UINT_MAX + 1.
- gegenschall 14y ago
  There is a somewhat related text by Fefe: http://www.fefe.de/intof.html http://www.fefe.de/intof.html

deleted 14y ago

[deleted]

matheusalmeida 14y ago

That would be true for unsigned data types. The C Standard specifies as 'undefined behavior' overflow for signed types. The C compiler can do whatever it wants...

Someone 14y ago

Some reasons (the first one being the most important one): 1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...) 2. To make C usable for those worried about erroneous overflows in their code. 3. To make it easier to write C compilers for CPUs that trap on integer overflow. 4. To allow for performant C compilers on CPUs that use one's complement arithmetic.

cliffbean 14y ago
> 1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-... http://blog.llvm.org/2011/05/what-every-c-programmer-should-...) I'm curious about this. See below. > 2. To make C usable for those worried about erroneous overflows in their code. I think you're saying that the rule allows compilers to implement -fwrapv if they choose, which sounds reasonable. > 3. To make it easier to write C compilers for CPUs that trap on integer overflow. > 4. To allow for performant C compilers on CPUs that use one's complement arithmetic. I wonder how much these matter nowadays. For optimization, the blog post you cite describes the following examples: - "X+1 > X" to true - "X*2/2" to "X" - "<= loops" and "int" induction variables On the first two, presumably these usually only come up after macro expansion and inlining, however they're still suspicious. If a function is scaling its return value and its caller is de-scaling it, it's usually a sign that the API isn't designed quite right. I'd be curious to know how often these come up. Code using "int" induction variables to step through arrays on 64-bit targets is often sloppy. Such code won't handle very large arrays properly, due to the limited range of "int", which is a bug that may not be quickly noticed. And for the "<= loop" itself: for (i = 0; i <= N; ++i) { ... } it's really unlikely that the code is actually intended to be an infinite loop in the case where N happens to be INT_MAX. Code like this would usually be clearer written as "i < N + 1" to emphasize that it really does intend to iterate N+1 times rather than just N times, and it just so happens that this form makes optimizers happier as well. Instead of having compiler writers sit around and think up clever ways to repurpose anachronistic language rules, I might prefer to have them focus instead on ways they can help me write better code instead :-).