30 Sep
2001
30 Sep
'01
9: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
30 Sep
30 Sep
1:06 p.m.
On Sun, 30 Sep 2001, Pete Turnbull wrote:
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.
This works itself out exactly like that below.
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.
Bingo! That fixed it:
* I get correct overflow flag values.
* The correct borrow flag value is the opposite of the carry out of the
addition.
Now what's disturbing is that the same wrong ideas that I was taught were
taught to an entire roomful of college students a few years ago, by a
professor in the School of Electrical and Computer Engineering.
Thanks for the help.
--
Jeffrey S. Sharp
jss(a)subatomix.com
6:09 p.m.
And likely STILL being taught wrong...had the same experiences in COBOL and
PASCAL programming classes in college, but we got professor's assistants
instead of the actual prof we paid for. Assistants are a fancy name for grad
students that have free time and get sucked into doing the prof's work when
he/she wants to goof off on the clock - at least at UI Champaign/Urbana and
Parkland College (community college) anyway.
-> -----Original Message-----
-> From: owner-classiccmp(a)classiccmp.org
-> [mailto:owner-classiccmp@classiccmp.org]On Behalf Of Jeffrey S. Sharp
-> Now what's disturbing is that the same wrong ideas that I was taught were
-> taught to an entire roomful of college students a few years ago, by a
-> professor in the School of Electrical and Computer Engineering.
->
-> Thanks for the help.
->
-> --
-> Jeffrey S. Sharp
-> jss(a)subatomix.com
->
->
5:41 p.m.
On Sun, Sep 30, 2001 at 01:38:13PM +0000, Pete Turnbull wrote:
On Sep 29, 23:32, Jeffrey S. Sharp wrote:
And (on the 6502) if you want to get a given result using addition vs.
subraction, the carry flag must be set differently. i.e., if you have
LDA #$FF LDA #$FF
ADC #$01 vs. SBC #$FF
and you want A to end up with $00, then you must put before the LDA:
CLC vs. SEC
I might never have known this except that I wanted to check my post
before posting it.
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
Well, as one of those people I may as well ask you how much of my post is
corect and how much is junk.
-- Derek
8269
days inactive
8269
days old
3 comments
4 participants
participants (4)
-
dpeschel＠eskimo.com -
jss＠subatomix.com -
pete＠dunnington.u-net.com -
rhblakeman＠kih.net