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".
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
All we have to do is find a way to represent negative numbers...
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
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"
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
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
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
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
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
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.
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
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
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
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
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
> 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
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