tedj@hpcilzb.HP.COM (Ted Johnson) (01/25/88)
Could someone please explain why the following statements both give the same answer? short int x, y = 12; x = -y -1; vs. short int x, y = 12; x = ~y; Both ways end up assigning x the value of -13. K&R say something about the ~ operator taking the one's complement of a number, but I didn't follow their explanation... The only reason I ask is because I saw two different programs compute the same function in two different ways, and I want to know if they are really doing the same thing or if this is a special case where both functions give the same answer. Thanks in advance! -Ted P.S. This was on a machine where a short int is 16 bits.
boemker@hpfcdc.HP.COM (Tim Boemker) (01/27/88)
> Could someone please explain why the following statements both give the > same answer? x= -y -1; vs. x = ~y; On most computers, integers are stored in two's complement form. For a positive integer, that's the normal representation. For a negative integer, the two's complement is the one's complement plus one. (Adding one may seem curious, but it has an important advantage: there's only one representation for zero. In a one'c complement scheme, both a word of 1's and a word of 0's represent zero.) Let y be a positive integer. -y = ~y + 1 by definition of two's complement -y - 1 = ~y QED.
scjones@sdrc.UUCP (Larry Jones) (01/27/88)
In article <1620006@hpcilzb.HP.COM>, tedj@hpcilzb.HP.COM (Ted Johnson) writes: > > Could someone please explain why the following statements both give the > same answer? > > x = -y -1; > x = ~y; Congratuations! You've just discovered "two's complement". This is the system that most current computers use for representing integer values. To fully understand it, you need to first understand "one's complement". In the one's complement, the negative of a number is represented by negating each bit of the number. For example, if you have the number 12 (00001100) then -12 is (11110011). This is called one's complement since adding a number to its negative results in a one in each bit position. This is what the ~ operator does, it complements each bit in a number. Although one's complement is a simple and easily understandable system, it has a number of disadvantages, not the least of which is that +0 and -0 each have representations. Since most people expect to have a single representation for zero, two's complement has become more popular. Two's complement is just like one's complement except that after you complement each bit, you add one to the result. Thus in two's complement notation -12 is (11110100). So, on a two's complement machine, -y == ~y + 1 which can be rearranged into the identity you discovered ~y == -y - 1. Please note, however, that this is NOT portable since there are still a few machines that use one's complement arithmetic rather than two's complement. -- ---- Larry Jones UUCP: uunet!sdrc!scjones SDRC MAIL: 2000 Eastman Dr., Milford, OH 45150 AT&T: (513) 576-2070 "When all else fails, read the directions."
tedj@hpcilzb.HP.COM (Ted Johnson) (01/28/88)
Thanks for the info., I get it now! (I am posting this so that people will stop e-mailing me explanations!) -Ted
bright@Data-IO.COM (Walter Bright) (01/28/88)
In article <1620006@hpcilzb.HP.COM> tedj@hpcilzb.HP.COM (Ted Johnson) writes:
<Could someone please explain why the following statements both give the
<same answer?
< x = -y -1; vs. x = ~y;
For a two's complement machine, the following identity is true:
-y == ~y + 1
This property is frequently exploited in assembly language programs.jrl@anuck.UUCP (j.r.lupien) (01/28/88)
In article <1620006@hpcilzb.HP.COM>, tedj@hpcilzb.HP.COM (Ted Johnson) writes: > Could someone please explain why the following statements both give the > same answer? > short int x, y = 12; > x = -y -1; > vs. > short int x, y = 12; > x = ~y; > > Both ways end up assigning x the value of -13. > P.S. This was on a machine where a short int is 16 bits. Ones complement means "change the state of each bit in the word", 1's => 0, 0's => 1. Most C implementations use "twos complement" for negative integers. This means that, for your machine, a -1 is represented as: 0xFFFF or b1111111111111111 So, if we do -1 -y, you have b1111111111111111 - b0000000000001100 -------------------- b1111111111110011 which happens to be the one's complement. As you can see, whatever pattern of bits appears as the diminuend in this subtraction is going to be inverted. If y is negative, you should still get the inverted bit pattern, but you may get an overflow. Actually, this is a somewhat simple way to look at things, in that it only answers the question that was asked, and fails to appropriately expand on the implementation issues that arise. For instance, the "subtract" operation may exist as an opcode on the machine, or it may not. If not, it is implemented as a special form of "add the twos complement of the diminuend", a sort of "to subtract, add the negative" implementation. To get back to the question, I use ~ for bitwise inversion. It is probably best to stick with bitwise operators for bitwise operations and arithmetic operators for arithmetic operations. This way, the vagaries of implementation are sidestepped. Implementors are responsible for assuring that these operations work correctly, whereas "tricks" have to be tested anew each time you port. John R. Lupien ihnp4!mvuxa!anuxh!jrl
nevin1@ihlpf.ATT.COM (00704a-Liber) (01/28/88)
In article <1620006@hpcilzb.HP.COM> tedj@hpcilzb.HP.COM (Ted Johnson) writes:
.
.Could someone please explain why the following statements both give the
.same answer?
.
. short int x, y = 12;
.
. x = -y -1;
.vs.
.
. short int x, y = 12;
.
. x = ~y;
.
.
.Both ways end up assigning x the value of -13. K&R say something about
.the ~ operator taking the one's complement of a number, but I didn't
.follow their explanation...
.
.P.S. This was on a machine where a short int is 16 bits.
This is because you are working on a 2's complement machine.
To take the negative of a 2's complement number, you
invert all the bits (ie, take the 1's complement of the number which is
using '~'), then you add 1 to the result.
Therefore, on a 2's complement machine, ~y +1 === -y or, as you stated,
~y === -y - 1.
This is a machine dependent feature and is NOT guaranteed to be consistent
under all implementations of C.
--
_ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194
' ) ) "The secret compartment of my ring I fill
/ / _ , __o ____ with an Underdog super-energy pill."
/ (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blahdag@chinet.UUCP (Daniel A. Glasser) (01/28/88)
In article <1620006@hpcilzb.HP.COM> tedj@hpcilzb.HP.COM (Ted Johnson) writes: > >Could someone please explain why the following statements both give the >same answer? > short int x, y = 12; > x = -y -1; >vs. > short int x, y = 12; > x = ~y; >Both ways end up assigning x the value of -13. K&R say something about >the ~ operator taking the one's complement of a number, but I didn't >follow their explanation... in two's complement arithmetic, the additive inverse (negative) of a number is computed by taking the 1's complement (all 1's become 0's, 0's become 1's) of the bit pattern and adding 1. An example of this is: Decimal Binary 1 0000000000000001 start with the number -2 1111111111111110 take one's complement -1 1111111111111111 add 1 So, -x is the two's complement, ~x is the one's complement. -x - 1 is the one's complement, ~x + 1 is the two's complement. Does any of this make sense? (CS -101) -- Daniel A. Glasser ...!ihnp4!chinet!dag ...!ihnp4!mwc!dag ...!ihnp4!mwc!gorgon!dag One of those things that goes "BUMP!!! (ouch!)" in the night.
decot@hpisod2.HP.COM (Dave Decot) (01/29/88)
The most important advantage of two's complement (why do they call it that?) is that adding and subtracting integers is easier (you just add normally), and this makes hardware to build: 111010 (-6) + 001001 ( 9) -------------- 000011 ( 3) Dave Decot hpda!decot
amos@taux01.UUCP (Amos Shapir) (01/29/88)
Since no one had mentioned this yet, I guess I'll have to: In article <2148@chinet.UUCP> dag@chinet.UUCP (Daniel A. Glasser) writes: >in two's complement arithmetic, the additive inverse (negative) of >a number is computed by taking the 1's complement (all 1's become 0's, >0's become 1's) of the bit pattern and adding 1. The definition of 2's complement is actually a little different: the binary represantation of a negative value is obtained by adding to it 2**n (** means power), where n is the number of bits, and doing a 'pure' unsigned binary represantation of the result. E.g. to represent -2 in a 16-bit word: -2 + 65536 = 65534 = 0b1111111111111110 -- Amos Shapir (My other cpu is a NS32532) National Semiconductor (Israel) 6 Maskit st. P.O.B. 3007, Herzlia 46104, Israel Tel. +972 52 522261 amos%taux01@nsc.com 34 48 E / 32 10 N
tainter@ihlpg.ATT.COM (Tainter) (01/30/88)
In article <2550041@hpisod2.HP.COM>, decot@hpisod2.HP.COM (Dave Decot) writes: > > Could someone please explain why the following statements both give the > > same answer? > > short int x, y = 12; > > x = -y -1; > > x = ~y; > The one's complement means flip all bits. (~ x) > The two's complement means flip all bits and add one. (- x) In fact, given the definitions it should be obvious that (~x) == (-x - 1) A derivation for those having long since seen their intro algebra classes :-) (-x - 1) :=: ((~x+1) - 1) (-x - 1) :=: (~x + (1 - 1)) (-x - 1) :=: (~x) > Dave Decot --j.a.tainter