30 Sep
2001
30 Sep
'01
1:38 a.m.
On Sep 29, 23:32, Jeffrey S. Sharp wrote:
Yes, I'm actually going to ask a question about
two's complement
arithmetic! I feel quite stupid for mailing this, but I just can't
figure
it out. And believe it or not, it really does have
something to do with
classic computing. All right, here goes...
While I was in class Thursday [...] I created the following table:
[ snip ]
Note that the C and V flags behave differently in each
half. This is
very
disturbing, since I'm fairly certain that
subtraction is implemented in
many processors as adding a negated subtrahend (ergo, I should see no
difference in the flags). What have I done wrong in my table?
Firstly, you're assuming (on the left) that "carry" is the same as
"borrow". Wrong! If you are subtracting, working the columns
right-to-left, a borrow from one column to the previous (on the right) is
balanced by adding the borrowed digit back to the subtrahend, so it gets
subtracted from the result, not added. This is the opposite of a carry.
That's why most of the "carry" flags you show in the left side of the
table are incorrect; they're actually "borrow" flags. If you think this is
confusing, try comparing the carry flags implemented in a Z80 and a 6502
(they do different things for subtractions!).
The other problem you have is with the overflow. It's not a problem with
signed vs unsigned numbers as some people have implied, it's with the order
you do things in. I assume you're setting the V (oVerflow) as the XOR of
the carry into the MSB and the carry out of the MSB. Well, this is true,
but for it to work with pathological cases you don't do the full two's
complement process before the addition, but do it at the same time. One of
your cases is
Subtraction Equivalent Addition
AA-BB=CC CZSV AA+BB=CC CZSV
01 10 11 x.xx 01 10 11 ..x.
The difficulty is that binary 10 is its own complement. However, you'll
get the right answer if you say that "A - B" is the same as "A + inv(B) +
1" where "inv(B)" is the ones-complement of B. "inv(10)" is
"01". Now add
"01" + "01" + "1" in a single step. You'll find the
carry out of the MSB
is a "0", of course, but the carry into the MSB is a "1". Therefore V
= 1
xor 0 = 1. Which is what we hope!
However, if you say that "A - B" is the same as "A + cpl(B)" where
"cpl(B)"
is the twos-complement of "B", ie you do "inv(B) + 1" ahead of the
rest of
the addition -- as you did -- you'll add "01 + 10" in a separate step.
Then you'll find the carry into the MSB is now a "0", and 0 xor 0 = 0,
implying no overflow. Wrong answer!
That's one of the reasons that ALU designers don't usually implemetn a
2-stage complement-and-add for subtraction, but instead do it with a
single-stage invert-add-xor operation (the xor being the addition of the
extra "1" which makes the invert arithmetically equivalent to
2s-complement).
--
Pete Peter Turnbull
Network Manager
University of York