Path: ccrwest.org!not-for-mail
From: dmoews@xraysgi.ims.uconn.edu (David Moews)
Newsgroups: comp.lang.c,sci.math
Subject: Re: Contest: C BIGNUM BAKEOFF; clarification by the proposer (II)
Date: 12 Dec 2001 13:36:13 -0800
Organization: University of Connecticut IMS
Lines: 118
Message-ID: <9v8ikd$dbv$1@lydian.ccrwest.org>
References: <200112120215.VAA19937@xraysgi.ims.uconn.edu> <9v8dpv$bv4$1@lydian.ccrwest.org>
NNTP-Posting-Host: lydian.ccrwest.org
X-Trace: lydian.ccrwest.org 1008192973 13696 192.203.205.93 (12 Dec 2001 21:36:13 GMT)
X-Complaints-To: usenet@ccrwest.org
NNTP-Posting-Date: 12 Dec 2001 21:36:13 GMT
Xref: ccrwest.org comp.lang.c:435139 sci.math:420205
In Rule 7 I attempted to define a natural virtual machine that would allow
unsigned types but render useless the sorts of tricks with casts, shifts, etc.
that people have been trying to play. In this virtual machine, all integral
types have the same size (1 byte), and are represented as strings of bits
which are infinite to the left. These strings are always either 0 in all
except finitely many positions, or 1 in all except finitely many positions.
They can be viewed as (signed) integers by taking the bit string to be the
2s-complement representation of an integer; or they can be viewed as unsigned
quantities. Casts from one integral type to another do not change the
underlying bit string; therefore,
(int)(unsigned)-1 == -1 : (1)
-1 is represented by .......11111111111111;
(unsigned)-1 is represented by .......11111111111111;
(int)(unsigned)-1 is represented by .......11111111111111.
The logical operations ~, |, ^, and binary & are done bit by bit, and therefore
(int)~0U == -1 : (2)
0U is represented by .......00000000000000;
~0U is represented by .......11111111111111;
(int)~0U is represented by .......11111111111111.
Shifts are also done on the bit string representation. (This was not made
completely precise in rule 7 because I neglected to define the result of
a >> b or a << b where one of a and b was unsigned and the other was signed.
I apologize for this.) However, you should not think that computing ~0U >> 1
will shift 0 into the most significant bit, because there is no most
significant bit in an infinite bit string. This means that arithmetic and
logical right shifts are the same, so for a and b of types int, the
identity
(int)((unsigned)a >> b) == a >> b (3)
holds. This means that
(int)(~0U>>1) == -1 : (4)
0U is represented by .......00000000000000;
~0U is represented by .......11111111111111;
~0U>>1 is represented by .......11111111111111
(each 1 bit is replaced by the 1 bit to its left);
(int)(~0U>>1) is represented by .......11111111111111.
For another example,
(int)((unsigned)-3>>1) == -2 : (5)
-3 is represented by .......11111111111101;
(unsigned)-3 is represented by .......11111111111101;
(unsigned)-3>>1 is represented by .......11111111111110;
(int)((unsigned)-3>>1) is represented by .......11111111111110,
which is the 2s-complement representation of -2.
If the right operand of a shift is unsigned, you should consider it to
be cast to a signed type before the shift is done. Also, I took the
liberty of making the identity
(a >> -b) == (a << b) (6)
true.
The arithmetic operators unary +, unary -, binary +, binary -, binary *,
and / give the mathematically expected result on signed integral types;
/ always rounds down towards -infinity. Their result on unsigned types is
illustrated by the identities, for a and b of type unsigned,
(int)(-a) == -(int)a , (7)
(int)(a + b) == (int)a + (int)b , (8)
(int)(a - b) == (int)a - (int)b , (9)
(int)(a * b) == (int)a * (int)b , (10)
(int)(a / b) == (int)a / (int)b . (11)
Finally, the relational operators order signed types in the mathematically
expected way, and unsigned types lexicographically on their bit strings.
In Rule 7 I also was not completely precise about which types could represent
values of which other types and the consequent rules for integral promotions.
My intent was as follows:
(i) All signed integral types represent a set of nonnegative
values and a set of negative values.
(ii) All unsigned integral types represent the same set of
nonnegative values as in (i) together with a set of
casted negative values.
(iii) The set of casted negative values is disjoint from the set
of negative values; so, no unsigned integral type can
represent all values of a signed integral type, and no signed
integral type can represent all values of an unsigned
integral type.
Therefore,
(iv) When an integral promotion is made, the types char, signed
char, and short int are converted to type int; the types unsigned
char and unsigned short int are converted to type unsigned int.
(v) If, during the usual arithmetic conversions, one operand
has type long int and one operand has type unsigned int,
both operands are converted to type unsigned long int.
I hope that this clarifies the virtual machine. Use of limits.h is
prohibited but some entries in it could nonetheless be defined:
CHAR_BIT is undefinable,
INT_MIN is undefinable,
INT_MAX is undefinable,
UINT_MAX is (~0U),
and so forth.
Finally, I claim that this virtual machine is not particularly outlandish.
Many real implementations of C already satisfy identities (1), (2), (7), (8),
(9), and (10).
--
David Moews dmoews@xraysgi.ims.uconn.edu