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