- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Pete Turnbull <pete_at_dunnington.u-net.com>

Date: Sun Sep 30 08:38:13 2001

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).

Date: Sun Sep 30 08:38:13 2001

On Sep 29, 23:32, Jeffrey S. Sharp wrote:

figure

[ snip ]

very

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 YorkReceived on Sun Sep 30 2001 - 08:38:13 BST

*
This archive was generated by hypermail 2.3.0
: Fri Oct 10 2014 - 23:34:26 BST
*