473,320 Members | 1,883 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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

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.
Nov 14 '05 #1
6 2679
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.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 14 '05 #2
In article <e8********************************@4ax.com>,
Jack Klein <ja*******@spamcop.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.
Nov 14 '05 #3
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.
Nov 14 '05 #4
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 "representable" 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 "representable" 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)
Nov 14 '05 #5
In article <a5**************************@posting.google.com >,
k_*****@yahoo.com (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 "representable" 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 "representable" 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.
Nov 14 '05 #6
In article <a5**************************@posting.google.com > k_*****@yahoo.com (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, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Nov 14 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

17
by: Sean Kenwrick | last post by:
I am writing a byte-code interpreter/emulator for a language that exclusively uses strings for variables (i.e all variables are pushed onto the stack as strings). Therefore for arithmetic...
29
by: RoSsIaCrIiLoIA | last post by:
write the function int readINT(FILE* fp); that read an int from fp and return it. given the following conditions a. Do not use arrays b. Do not use any comparison function like if/then or...
15
by: Jordan Abel | last post by:
Say int is a 16-bit twos-complement type. Is the expression (-32768) actually negative? Or is it the unsigned int literal 32768 with the unary minus operator applied to it, resulting in the...
10
by: pemo | last post by:
As far as I understand it, a trap representation means something like - an uninitialised automatic variable might /implicitly/ hold a bit-pattern that, if read, *might* cause a 'trap' (I'm not...
2
by: jzhang918 | last post by:
Hi, Should f(INT_MIN) return 0 according to the C99 for the following function f (), or its result is undefined? int f(int i) { i = i 0 ? i : -i; if (i<0) return 0;
41
by: p_cricket_guy | last post by:
Please see this test program: 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <limits.h> 4 5 int main (void) 6 { 7 int y = -2147483648; 8 int x = INT_MIN;
166
by: Nimmi Srivastav | last post by:
Apologies if my cross posting has offended anyone.... For a pure hobbyist C/C++ programmer, who wants to develop applications to run on Windows, what would be a better choice to install: Visual...
173
by: Ron Ford | last post by:
I'm looking for a freeware c99 compiler for windows. I had intended to use MS's Visual C++ Express and use its C capability. In the past with my MS products, I've simply needed to make .c the...
30
by: viza | last post by:
Hi all int i= INT_MIN; unsigned int u= -i; Is u guaranteed to have the absolute value of INT_MIN? Why it might not: -i has type (int), and -INT_MIN might be more than INT_MAX.
42
by: polas | last post by:
Afternoon all, I have some code (which I thought was OK, but now appreciate is probably not by the standard) which contains int a; ...... if (a==NULL) { ....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.