Designing The MiniMips – Part 2 Subtraction and Negative Numbers
Last time we discussed binary addition and how we could use a few logic gates to do arithmetic. I showed you a few simple circuits and left you with a simple assignment to use the full adder circuit to build a multi-bit full adder. I told you I’d show you a solution to the exercise. So here it is:
As you can see the full adders are simply cascaded by connecting the carry-out of the previous stage to the carry-in on the next stage. This cascading can be continued until the propagation delay of the carry signal become intolerable. If that happens there are techniques for improving the circuit. Checkout the Carry Lookahead Adder circuit.
We’ve seen how binary adders can be built from simple logic gates. Now let’s look at binary subtraction. The binary subtraction rules are very simple:
|0-0 = 0||1-0=1||1-1 = 1||10-1 = 1|
Binary subtraction is similar to decimal subtraction with the difference that when 1 is subtracted from 0, it is necessary to borrow 1 from the next higher order bit. That bit is reduced by 1 and the remainder is 1. The one thing that confuses most people when doing a binary borrow is that when you borrow in decimal you add it as 10 to the previous column. In binary we are using powers of 2. So when we borrow we must add the borrow as two bits of half the original value:
In the above, starting from the left most bit. First we can’t subtract 1 from 0 so we try to borrow 1 from the next column to the right (the tow’s column). However, it too is 0. We can’t borrow 1 from 0 so we move on to the third column left (the fours column). Next, in the fourth column left we find a 1 in the eights column. Now this one represents an 8 in decimal. So when we move it to the fours column. We have to split that 8 into two 4s. So we place two 1’s above the fours column. Next we borrow one of them and move it to the two’s column as two 2s. Again, we borrow a two from the 2s column and move it as two ones and place them in the 1s column. Now we can subtract the 1 in the right most the two ones we placed there. This leaves a one which we bring down. In the two’s column we can now subtract 0 from the remaining 1 and get 1. We then move left to the fours column and subtract 1 from the remaining 1 we carried over and get 0. The eights column is now 0 and being a leading 0 we don’t really need to bring it down as it adds no value to our answer. Now to check our answer we can see that our original problem was: 8-5=3. And indeed 11 in binary is 3 in decimal.
Now let’s look at the logic needed to do a single bit binary subtraction. The truth table for subtraction is:
Looking at the table we can see that the difference is computed using an XOR gate. The borrow out however is a slightly more complex. Borrow out is only 1 when A is 0 and B is 1. This looks like and AND gate with an inverter on B. Let’s try it out in logisim. Build the following circuit in logisim and see if it matches the truth table above:
Now this circuit is called a half subtractor. Just as the half adder is missing a carry in, the half subtractor is missing a borrow in. However, a similar cascading trick like that used for the half adder can be used to build a full subtractor. Let’s try this out. Build the circuit below in logisim and give it a try:
Now this kind of subtractor is great if you are only working with positive numbers. But if we ever need to work with a negative value as an operand or a resulting value, we are out of luck. So how do we handle negative numbers? Well, the most typical way is to reserve the left-most bit for use as a sign bit. The sign bit is set to 1 to indicate a negative value and 0 to indicate a positive value. So if we have 8 bits we can represent -127 through +127. There is an issue however, To demonstrate it let’s reduce this to a bit bit signed number. So we can represent -7 to +7 with the three bits know as the magnitude and the fourth bit as the sign bit.
Notice anything odd about this arrangement? Look closely, there are two zero values. Zero and negative zero. Who ever heard of negative zero? Sign magnitude presents it’s own issues. A program or hardware would have to check for two values of zero if this was implemented in our microprocessor. So what can we do about this? How about flipping the bits and using one’s complements. This too has it’s own issues. The issues with negative numbers is solved by something called two’s-complement. I found a Computerphile video that I think gives one of the best explanations available. Watch the video to learn more about binary math and negative numbers:
Now I am sure you have a good grasp on the problems and solutions to binary mathematics. I’ll leave you with this: How can we modify our multi-bit adder for use in both addition and subtraction? I’ll show you my solution next time. Until then, play around with your own ideas in logisim and try to build an adder/subtractor circuit using 2’s-complement.