C99: Is "INT_MIN % -1" well defined?

[M Welinder]

The title more or less says it all: in C99, is the value of

INT_MIN % -1

well defined (when performed as signed integers) under the assumption of
two-complement representation.

Note, that this is not the usual negative-values-and-% question -- the problem
here is that the corresponding signed division, INT_MIN / -1, overflows. Thus
I don't see what use a%b = a-(a/b)*b can be here.

[Jack Klein]

On 5 Aug 2004 06:57:20 -0700, te***@gnome.org (M Welinder) wrote in
comp.lang.c:

The title more or less says it all: in C99, is the value of

INT_MIN % -1

well defined (when performed as signed integers) under the assumption of
two-complement representation.
No version of the C standard assumes two's complement representation,
nor makes any additional exceptions or requirements for platforms that
use this representation as opposed to the other two allowed choices.
Note, that this is not the usual negative-values-and-% question -- the problem
here is that the corresponding signed division, INT_MIN / -1, overflows. Thus
I don't see what use a%b = a-(a/b)*b can be here.

The division does not necessarily overflow. You are assuming that
INT_MIN is -(pow(2,n)) for some typical value of 'n' such as 15 or 31.
While this is common on 2's complement platforms, the C standard does
not require that this value be supported. INT_MIN is allowed to be
-(INT_MAX), even on 2's complement systems. The binary value
containing only the sign bit set may be an invalid bit-pattern, what
the standard calls a trap representation.

So if INT_MIN is equal to -(INT_MAX), both the division and mod
operation are well-defined.

On the other hand, if INT_MIN is equal to -(INT_MAX)-1, I would say
that it produces overflow, which makes it undefined behavior.
The definition of the '%' is specifically defined as the remainder of
the division of the two operands. If the division overflows, so does
the modulus.

See 6.5.5 para. 5 and 3.4.3 para 3.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Christian Bau]

In article <e8************ *************** *****@4ax.com>,
Jack Klein <ja*******@spam cop.net> wrote:

On the other hand, if INT_MIN is equal to -(INT_MAX)-1, I would say
that it produces overflow, which makes it undefined behavior.
The definition of the '%' is specifically defined as the remainder of
the division of the two operands. If the division overflows, so does
the modulus.

Behavior of arithmetic operations is undefined if the result cannot be
represented. The remainder of (-INT_MAX - 1) / (-1) can be represented
without any problems, even though the result of the division can't be
represented.

However, the C Standard says "If a/b can be represented, then (a/b)*b +
(a%b) == a". This is supposed to define the result that a%b should
produce, and it doesn't define the result in the case above. On the
other hand, I would say that the "remainder" is a well-defined
mathematical term except in cases like (-10) % (-3), where it is not
obviously clear whether the result should be -1 or +2. If a is a
multiple of b, then the remainder is always 0, and that is the case
here.

So I would say the result of x % (-1) is well-defined and zero in all
cases.

[M Welinder]

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

So I would say the result of x % (-1) is well-defined and zero in all
cases.

Ok, but if that is the case, then all i86 compilers need to generate code
like morally equivalent to

a C99% b = (b == -1) ? 0 : (a machine% b)

because the machine% (aka the division instruction) will not work for INT_MIN
and -1. (And forget about multiple evaluation of b or missing evaluation of
a -- that's not the point here.)

It was my impression that C99 intended to shore up the semantics while still
allowing for an efficient implementation on i86. I had sort-of hoped for the
answer "clearly undefined under the assumptions".

M.

[kal]

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

Behavior of arithmetic operations is undefined if the result cannot be
represented. The remainder of (-INT_MAX - 1) / (-1) can be represented
without any problems, even though the result of the division can't be
represented.
Depends on what "representa ble" means.
However, the C Standard says "If a/b can be represented, then (a/b)*b +
(a%b) == a".
This is true, though the actual statement is:

6 When integers are divided, the result of the / operator is
the algebraic quotient with any fractional part discarded.
If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

The question is what does the word "representa ble" mean. The
result of the expression (-INT_MAX - 1) / -1 can certainly be
represented as an unsigned int, though you may have a problem
if you tried to assign the value to a signed int.
This is supposed to define the result that a%b should
produce, and it doesn't define the result in the case above.
Ok but see below. (1)
On the other hand, I would say that the "remainder" is a
well-defined mathematical term except in cases like
(-10) % (-3), where it is not obviously clear whether the
result should be -1 or +2.
Mathematically it should be -1 and never +2.
So I would say the result of x % (-1) is well-defined and
zero in all cases.

This contradicts your statement above. (1)

[Christian Bau]

In article <a5************ **************@ posting.google. com>,
k_*****@yahoo.c om (kal) wrote:

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message
news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

Behavior of arithmetic operations is undefined if the result cannot be
represented. The remainder of (-INT_MAX - 1) / (-1) can be represented
without any problems, even though the result of the division can't be
represented.

Depends on what "representa ble" means.

However, the C Standard says "If a/b can be represented, then (a/b)*b +
(a%b) == a".

This is true, though the actual statement is:

6 When integers are divided, the result of the / operator is
the algebraic quotient with any fractional part discarded.
If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

The question is what does the word "representa ble" mean. The
result of the expression (-INT_MAX - 1) / -1 can certainly be
represented as an unsigned int, though you may have a problem
if you tried to assign the value to a signed int.

This is supposed to define the result that a%b should
produce, and it doesn't define the result in the case above.

Ok but see below. (1)

On the other hand, I would say that the "remainder" is a
well-defined mathematical term except in cases like
(-10) % (-3), where it is not obviously clear whether the
result should be -1 or +2.

Mathematically it should be -1 and never +2.

So I would say the result of x % (-1) is well-defined and
zero in all cases.

This contradicts your statement above. (1)

What makes you think that? The remainder of division of an integer by
minus one is always zero, no matter what exact definition of remainder
you use (and there are several possibilities). If x is a multiple of y,
then the remainder of x/y is zero. And every integer is a multiple of
-1.

So the C Standard gives one definition which is not quite complete,
because "remainder" as a mathematical term does not have a well defined
meaning in all cases, but it has a well defined meaning in the case we
discuss. The C Standard gives another definition which explicitely
excludes the case we are discussing but clarifies the first definition
in many cases. Since Definition 1 applies and defines the result as 0,
and Definition 2 does not apply, the result must be 0.

[Dik T. Winter]

In article <a5************ **************@ posting.google. com> k_*****@yahoo.c om (kal) writes:

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

....

On the other hand, I would say that the "remainder" is a
well-defined mathematical term except in cases like
(-10) % (-3), where it is not obviously clear whether the
result should be -1 or +2.

Mathematically it should be -1 and never +2.

Mathematics does not know the operator '%'. Nor is there a well-defined
mathematical term "remainder" . Mathematics talks about residue classes,
and in that case the results "-1" and "+2" are the same. That is:
-10 == -1 == 2 (mod -3).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/