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. Here goes. SUBTRACTION: ADDITION'S EVIL TWIN --------------------------------- 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]: Decimal: Sign/Magnitude: -------- --------------- 1 = 00000001 -1 = 10000001 2 = 00000010 -2 = 10000010 127 = 01111111 -127 = 11111111 0 = 00000000 -0 = 10000000 Uh-oh. "Negative zero"? What's THAT? Let's gloss over it for now and see whether our math works: Decimal: Sign/Magnitude: -------- --------------- 3 - 1 = 3 + (-1) 00000011 = 2 +10000001 --------- 10000100 (-4) NOT CORRECT! 1 - 3 = 1 + (-3) 00000001 = -2 +10000011 _________ 10000100 (-4) NOT CORRECT! -3 - 1 = -3 + (-1) 10000011 = -4 +10000001 --------- Cout + 00000100 (4) NOT CORRECT! (but sorta close) -3 - (-1) = -3 + 1 10000011 = -2 +00000001 --------- 10000100 (-4) NOT CORRECT! 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}. It looks like this: Decimal: 1's complement: -------- -------------- 1 = 00000001 -1 = 11111110 2 = 00000010 -2 = 11111101 127 = 01111111 -127 = 10000000 0 = 00000000 -0 = 11111111 We still have the same 0/-0 problem, but again, we can gloss over it temporarily. Let's try some math: Decimal: One's complement: -------- ----------------- 3 - 1 = 3 + (-1) 00000011 = 2 +11111110 --------- Cout + 00000001 (1) NOT CORRECT! 1 - 3 = 1 + (-3) 00000001 = -2 +11111100 _________ 11111101 (-2) CORRECT! -3 - 1 = -3 + (-1) 11111100 = -4 +11111110 --------- Cout + 11111010 (-5) NOT CORRECT! -3 - (-1) = -3 + 1 11111100 = -2 +00000001 --------- 11111101 (-2) CORRECT! 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? Let's try some more examples before we do that. Decimal: One's complement: -------- ----------------- 3 - 3 = 3 + (-3) 00000011 = 0 +11111100 --------- 11111111 (-0) CORRECT! (more or less) -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: Decimal: 2's complement: -------- -------------- 1 = 00000001 -1 = 11111111 2 = 00000010 -2 = 11111110 127 = 01111111 -127 = 10000001 0 = 00000000 -0 = 00000000 (the same as 0) -128 = 10000000 Just for kicks, let's try some math: Decimal: Two's complement: -------- ----------------- 3 - 1 = 3 + (-1) 00000011 = 2 +11111111 --------- Cout + 00000010 (2) CORRECT! 1 - 3 = 1 + (-3) 00000001 = -2 +11111101 _________ 11111110 (-2) CORRECT! -3 - 1 = -3 + (-1) 11111101 = -4 +11111111 --------- Cout + 11111100 (-4) CORRECT! -3 - (-1) = -3 + 1 11111101 = -2 +00000001 --------- 11111110 (-2) CORRECT! 3 - 3 = 3 + (-3) 00000011 = 0 +11111101 --------- Cout + 00000000 (0) CORRECT! -3 - 2 = -3 + (-2) 11111101 = -5 +11111110 _________ Cout + 11111011 (-5) CORRECT! Wow. 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. For example: Decimal: Binary: ------------------ ----------------- 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? Let's try it and see... Decimal: Binary: ------------------ ----------------- 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: Decimal: Two's complement: ---------------------- ----------------- 64 + 65 = 129 01000000 (64) +01000001 (65) _________ 10000001 (-127) NOT CORRECT! A similar thing happens when you subtract, say, 65 from -64: Decimal: Two's complement: ---------------------- ----------------- -64 - 65 = -64 + (-65) 11000000 (-64) = -129 +10111111 (-65) _________ Cout + 01111111 (127) NOT CORRECT! 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. Ok... I'm tired now. Hope this helped, Tim. -Andy If you can read this, you got the whole message. === Andrew Warren - fastfwd@ix.netcom.com === === Fast Forward Engineering - Vista, California === === === === Did the information in this post help you? Consider === === contributing to the PICLIST Fund. Details are at: === === http://www.geocities.com/SiliconValley/2499/fund.html ===