7

I know that (INT_MIN / -1) overflows, but (INT_MIN % -1) does not. At least this is what happens in two compilers, one pre-c++11 (VC++ 2010) and the other post-c++11 GCC 4.8.1

int x = INT_MIN;
cout << x / -1 << endl; 
cout << x % -1 << endl;

Gives:

-2147483648
0

Is this behavior standard defined or this is implementation defined? Also is there ANY OTHER case where the division operation would overflow? and is there any case where the modulus operator would overflow?

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
Red
  • 171
  • 5
  • 13

3 Answers3

11

According to CERT C++ Secure Coding Standard modulus can can overflow it says:

[...]Overflow can occur during a modulo operation when the dividend is equal to the minimum (negative) value for the signed integer type and the divisor is equal to -1.

and they recommend the follow style of check to prevent overflow:

signed long sl1, sl2, result;

/* Initialize sl1 and sl2 */

if ( (sl2 == 0 ) || ( (sl1 == LONG_MIN) && (sl2 == -1) ) ) {
  /* handle error condition */
}
else {
  result = sl1 % sl2;
}

The C++ draft standard section 5.6 Multiplicative operators paragraph 4 says(emphasis mine):

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined. For integral operands the / operator yields the algebraic quotient with any fractional part discarded;81 if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a; otherwise, the behavior of both a/b and a%b is undefined.

The C version of the CERT document provides some more insight on how % works on some platforms and in some cases INT_MIN % -1 could produce a floating-point exception.

The logic for preventing overflow for / is the same as the above logic for %.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
  • 1
    Are they adding the "otherwise" portion to the next standard? The current C++11 standard does not include it (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf). – Zac Howland Oct 10 '13 at 13:56
  • 2
    @ZacHowland It looks like the *otherwise* portion was added since `N3485`, all the drafts forward have the same language. This [previous thread](http://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-c-standard-documents) has a nice collection of links to drafts. – Shafik Yaghmour Oct 10 '13 at 15:25
  • @Pacerier it seems like they have moved the content so, maybe it was unavailable while that was going on. I fixed the linked. – Shafik Yaghmour Sep 11 '14 at 06:17
1

It is not the modulo operation that is causing an overflow:

int x = INT_MIN;
int a = x / -1; // int's are 2's complement, so this is effectively -INT_MIN which overflows
int b = x % -1; // there is never a non-0 result for a anything +/- 1 as there is no remainder
Zac Howland
  • 15,777
  • 1
  • 26
  • 42
0

Every modern implementation of the C++ language uses two's complement as the underlying representation scheme for integers. As a result, -INT_MIN is never representable as an int. (INT_MAX is -1+INT_MIN). There is overflow because the value x/-1 can't be represented as an int when x is INT_MIN.

Think about what % computes. If the result can be represented as an int, there won't be any overflow.

Steve Kass
  • 7,144
  • 20
  • 26
  • (OP's asking in C++, not C) – Dennis Meng Oct 10 '13 at 00:44
  • Thanks, Dennis. The reason is the same, so I edited to say C++. – Steve Kass Oct 10 '13 at 00:46
  • This should say something like “every modern mainstream implementation”. Certainly there are odd implementations out there for peculiar or niche systems. And anybody can check out the GCC sources, modify the behavior to differ but still be conforming (to the extent GCC is to start with), and truthfully claim they have a C implementation that differs from your assertion. – Eric Postpischil Oct 10 '13 at 00:51
  • True. Better yet, I might have said the observed overflow behavior suggests that "your C++ implementation, like all mainstream implementations, uses two's complement..." – Steve Kass Oct 10 '13 at 00:55