This is the second part of my "Everything you always wanted to
know, expressed in painstaking detail, about two's-complement
binary math". As before, scroll down to the bottom of this
message and make sure you can read the line:
"If you can read this, you got the whole message".
REVIEW:
-------
By walking through the tedious steps required to build an 8-bit
adder, we've seen what a thankless job microprocessor ALU designers
have: They need to build circuits to perform relatively-complex
mathematical functions, they're given only the most rudimentary
building blocks (two-input logic gates) to work with, and their
employers insist that every circuit be constructed using the
absolute minimum number of those gates.
What we HAVEN'T done yet is explain what "1's-complement" and
"2's-complement" mean, and what they're good for.
We've already built an 8-bit adder; it takes two 8-bit numbers and a
carry-in bit, adds them all together, and produces an 8-bit result
plus a carry-out.
Unfortunately, this won't fully satisfy our customers; the ungrateful
buggers want SUBTRACTION, too.
Our first thought is that we'll just build a separate binary
"subtractor". After all, addition didn't require too many gates;
maybe subtraction won't take many, either.
If we build that subtractor, however, we introduce a new problem:
Subtracting a large number from a smaller one gives a NEGATIVE
result. So far, we've been treating 8-bit numbers as positive
values in the range [0-255]; building a subtractor will require us to
decide on some way to represent negative numbers, as well.
A moment's thought shows how we can turn this requirement to our
advantage: If we can come up with a way to represent negative
numbers, we can perform subtraction by simply negating the subtrahend
and ADDING it to the minuend. That is:
"A - B" is equal to "A + (-B)".
This is an Exceedingly Good Thing; it means that we can use our
existing 8-bit-adder circuit to perform both addition AND
subtraction.
All we have to do is find a way to represent negative numbers...
SIGN/MAGNITUDE
--------------
Obviously, we won't be able to represent the full range of integers
from -255 to 255 in only 8 bits; 8 bits is sufficient for only 256
discrete values.
We can live with this, though... So we'll first try using only the
low (rightmost) 7 bits of each number to represent the magnitude, and the
leftmost bit of each number (the "Most Significant Bit", or "MSB") to
represent the number's sign (0 = positive, 1 = negative).
This means that an 8-bit number will be able to represent values in
the range [-127 - +127]:
That's enough... I think we can give up on the "sign/magnitude"
representation now.
ONE'S COMPLEMENT
----------------
Ok... Let's try something else. Rather than simply setting the MSB
to 1 to represent negative numbers, let's try inverting the entire
byte. This is the "one's complement" representation of signed binary
values.
Like the "sign/magnitude" representation, "one's-complement" will
allow an 8-bit number to represent values in the range [-127 - +127}.
This is more promising than the "sign/magnitude" representation we
first tried... If you look closely, you'll see that the results that
DON'T set the Cout bit are correct, while the results that DO set the
Cout bit are only off by one.
Maybe we can add a little circuitry to add the Cout bit to the sum?
-3 - 2 = -3 + (-2) 11111100
= -5 +11111101
_________
Cout + 00000001 (1) NOT CORRECT! (and not just "off
by one", either)
These last two examples indicate that using the one's-complement
representation is likely to cause problems. While we may get the
correct results for MANY of the possible combinations of inputs, we
won't get the correct results for ALL of them.
Correcting the results that don't work will require a fair amount of
circuitry; it's obvious now that we can't correct the result by
simply adding the carry-out bit to it. Besides, that "negative-zero"
thing is sort of annoying, anyway.
So... Now what?
Well, for starters, let's get rid of the "negative zero".
To accomplish this, we'll use something called the "two's
complement".
TWO'S COMPLEMENT
----------------
To generate the 2's-complement of a number, you first find the
1's-complement (by inverting the entire byte), then add 1.
Zero is still represented by "00000000", but something interesting
happens when you calculate its two's complement: Inverting the byte
gives "11111111", and adding 1 to that gives "00000000" again.
Voila! No "negative zero"!
Now, since an 8-bit number can represent 256 unique values and
"zero" takes only one of those values, this means that we can
represent numbers in the range [-128 - +127] in our two's-complement
number system:
It looks as though the two's complement representation is the way to
go... There's only one representation for "zero", all the positive
numbers look the way they used to, the math seems to work (if we
ignore the carryout), and we even get an extra negative number
(-128) to play with.
Unfortunately, this is all for naught if we can't build the
appropriate circuitry with only a small number of gates.
Let's see what it takes.
BULDING A CHEAP TWO'S-COMPLEMENTOR
----------------------------------
Remember that the two's complement is obtained by inverting the
original number and adding 1 to it.
The inversion part is easy; a NOT gate for each of the eight bits
accomplishes it.
Adding 1, however, is more difficult. As we saw earlier, addition
requires 40 gates... We don't want to practically double our
gate-count just to do this one simple operation.
So what can we do?
Well, let's see... We're trying to calculate A - B, and this is
equivalent to A + (-B). In our two's-complement notation, -B is
equal to (NOT B) + 1, so we need to calculate A + ((NOT B) + 1).
Since addition is associative, this is the same as (A + (NOT B)) + 1.
Hmm... What if we use our existing "A + B + Cin" 40-gate adder, but
we explicitly set the Cin bit to 1 and run the B input through an
inverter? We'll end up calculating A + (NOT B) + 1, exactly what we
want!
So...
By adding only eight NOT gates and requiring the user to set the
carry-in before performing a subtraction (a la the 6502 and other
microprocessors) or just setting the carry-in internally (a la the
PIC), we've made our adder do double-duty as a subtractor.
Ok... At this point, I KNOW you're thinking, "So we saved a few
gates... Big deal," but for an ALU designer, saving 30-odd gates is
cause for a major celebration.
Sad but true.
Anyway...
MULTI-BYTE ARITHMETIC
---------------------
Ok, so let's say that the guy who buys our microprocessor will want
to add numbers larger than 8 bits. Specifically, let's say that he
wants to add two 16-bit numbers. How does that work?
It's easy... He clears the carry-in, adds the two low-order
(rightmost, or "least-significant") bytes, then adds the two
high-order (leftmost, or "most-significant") bytes; any carry-out
that's generated by the first addition will become the second
addition's carry-in.
1000 + 1000 = 2000 00000011 11101000 (1000)
+00000011 11101000 (1000)
-----------------
1 11010000 (adding the two low
bytes gives 11010000,
plus a "1" Cout)
00000111 (The low-byte's Cout is
used as the high-byte's
Cin; adding it to the
two high bytes gives
00000111, with no Cout)
-----------------
00000111 11010000 (2000) CORRECT!
What about multi-byte SUBTRACTION? Will the two's-complement
representation still work there? What about that "set the Cin to 1"
trick? Will it affect the results?
2000 - 1000 00000111 11010000 (2000)
= 2000 + (-1000) +11111100 00010111 (NOT 1000)
= 2000+(NOT 1000)+1 + 00000001 (Cin = 1)
= 1000 ------------------
0 11101000 (adding the two low
bytes, plus the "1"
Cin, gives 11101000,
with a "0" Cout)
1 00000111 (The low-byte's Cout (0)
is used as the high-
byte's Cin; adding it to
the two high bytes gives
00000011, with Cout = 1)
-----------------
Cout + 00000011 11101000 (1000) CORRECT!
It works.
Note that we always ignore the final carry-out when we're performing
two's-complement math.
OVERFLOW, UNDERFLOW, AND OTHER ESOTERICA
----------------------------------------
Ok... Two's complement DOES have some problems. I've avoided them
here so far, but you can get an idea by adding 64 to 65:
Damn... And just when things were going so well, too.
In both cases, the correct result is too large to fit in 8 bits, so
our 8-bit result appears incorrect.
Fortunately, most microprocessors include an "overflow" bit that can
alert you to this situation.
Unfortunately, no PICs except the 17Cxx series include that
"overflow" bit.
Oh, well... If you're ever lucky enough to use a micro that contains
an "Overflow" flag, you should know that it signals one of the
following two conditions, each of which indicates that the result is
too large to fit in eight bits:
Overflow Condition #1:
There was an internal carry generated between bit 6 (second from
the left) and bit 7 (leftmost) of the result, but NO carry was
generated out of bit 7 of the result.
Overflow Condition #2:
There was NO internal carry generated between bit 6 and bit 7 of
the result, but there WAS a carry generated out of bit 7.
If neither of these conditions is true, the overfow flag is not set
and the carry-out of the result may be safely ignored. If one or the
other is true, your software needs to recognize the overflow (or
"underflow" if the too-large result is a negative number), and
compensate somehow.
Note, by the way, that the overflow flag is simply an XOR of bit 6's
Cout and bit 7's Cout... That's the extra gate that I mentioned in my
last message -- the one that turns our 40-gate adder into a 41-gate
adder.
I'm certainly not going to reply to the message and quote the original!
Thanks very much for this and for helping in the past too. The information
is really useful. The pseudo random system you sent me earlier is also
working with only one modification - as the device will be reset quite often
the timer value is used as a seed which is called checking the POR bit
(resets in the product are POR) so seeding only happens once. This gives
great results.
> I'm certainly not going to reply to the message and quote the
> original! Thanks very much for this and for helping in the past too.
No problem, Tim... I live to serve.
By the way, I forgot to mention that the PIC16's Carry flag is
actually a combination of the Cout bit and an internal "overflow"
bit... This means that, after an addition or subtraction, you
can use the state of the Carry flag as an under/overflow
indicator.
Also, the PIC16 has no "Add with Carry" or "Subtract with Borrow"
instructions, so setting the Carry flag before a PIC16 addition
or subtraction has no effect; the Carry flag is NOT used as the
first adder stage's "Cin". This means that if you're doing
multi-byte arithmetic, you have to manually adjust (in your
software) the higher-order bytes based on the Carry state after
the lower-order additions or subtractions.
I have to go to a meeting now, so I can't explain further; if
anyone needs assistance with this concept, let me know and I'll
try to post an explanation later.
> the PIC16's Carry flag is actually a combination of the Cout bit
> and an internal "overflow" bit... This means that, after an
> addition or subtraction, you can use the state of the Carry flag as
> an under/overflow indicator.
Please forget that I said that... It's not accurate. Everything
else in that message is fine, though.
Also, Jonathan King suggested reading the following two articles:
> "A minus B = A + not(B) + 1 (Part 1)" EDN Dec 5 1996, p199-204
> "A minus B = A + not(B) + 1 (Part 2)" EDN Jan 2 1997, p119-128
I took Honathan's advice and read those articles today... They're
pretty good. The author doesn't explain two's-complement math in
much detail, but he does give an interesting overview of ALU
design.
ix.netcom.com ===
