So there are four basic arithmetic operations: addition, subtraction, multiplication, and division. We've already covered addition, so the next logical (pun intended) step is to handle subtraction.
But before we go into subtraction, we need to remember something: it's always possible to get a subtraction like 3 - 5, which is negative 2. So far, we haven't really thought about negative numbers. let's consider the problem of how to represent a negative number.
Before I get into anything specific, I want to highlight a key point about computers and binary. You may have already guessed or intuited this, but for those who are new to binary, it is helpful to remember this:
The meaning of a series of binary digits (bits) is whatever we (meaning whoever makes the software or hardware) want it to be.
What that means is that 01100010 has no inherent meaning in and of itself. It could represent the number 64 + 32 + 2, or 98. It could also represent the letter "b" (this is based on ASCII, which assigns each letter, digit, and many symbols its own sequence of 8 bits). It might also be part of a larger number. There might even be a situation where each bit is tracking some property of a piece of data (perhaps there are 8 different actions users can do on some system, and one particular user has permission to do the 2nd, 6th, and 7th actions counting from the right). The meaning comes from how the bits are used. The binary that contains this webpage file has meaning because a program (your web browser) converts the bytes into text, and that text is turned into a pattern of pixels (your screen), which ultimately your eyes recognize as words.
OK, so enough abstraction. Why did I go there? Mostly because when we think about how to represent negative numbers, the only thing we have are bits. If we want to indicate if a number is positive or negative, that information has to be encoded as a bit. We're not obligted to consider 1101 as representing 8+4+1 = 13.
It could mean anything we want, but if we're trying to make a simple system for numbers, the easiest thing to do is just use one of the bits to mean positive or negative. The bit string 1101 would then mean... well, it could mean 5, 6, -5, or -6, depending on whether we use the left or right bit as the sign bit, and whether "1" means positive or negative. We'll have to pick one, so let's put the sign bit on the left, just like how -25 has the minus sign on the left. Also, we'll use 0 to mean positive, so that positive numbers look the same as before. (I have a hidden motivation for this, which you'll see later.)
By the way, we could use an extra bit for the sign, so that we'd still have the full range of values up to 232-1. But since in practice there are certain advantages to using a specific number of bits, like 32, it is more common to use "only" 31 for the value. For this exploration, I'll use six bits in total, including the sign bit. This means that instead of having range [0, 63], our signed numbers have a range of [-31, 31]. On a 32-bit computer, the range of unsigned integers is up to 4.3 billion, while signed integers can reach ±2.1 billion. That's not a bad tradeoff to get negative numbers! (For 64-bit computers, the ranges are in the quintillions.)
There is one annoying feature of this setup. Did you notice you can make negative zero? The bit patterns 100000 and 000000 both represent zero, but one is positive and the other is negative!
Anyway, let's ignore that for the moment and think about subtraction. Actually, both addition and subtraction are going to need new circuits, because adding a negative number is the same as subtracting a positive. We can't get away with just re-using the addition hardware. You're welcome to try!
Note: Try to find a case where the correct answer to the addition is between -7 and +7. While something like 6 + 3 does give the wrong answer -1, that's just due to overflow. The purpose here is to show that our normal adder circuit cannot handle the sign bits.
OK, so clearly that was too naive. What we really need is a circuit that can do subtraction. Then computing 5 + (-2) is as easy as doing 5 - 2. So how would you build a subtractor? The easiest way to start would be to consider base-ten subtraction. Here's an example:
16 26123729 - 8 8 8 -------- 1 [ 9 - 8 = 1] 6 1 [12 - 6 = 6] 8 6 1 [16 - 8 = 8] 2 8 6 1 [ 2 - 0 = 2]
As you can see, borrowing can get fairly hectic; the 7 got scratched out not once, but twice. In binary it's not that much better. One way to get started is to think about it the same way we did addition. Let's look at the possible options for a "half subtractor":
As you can see, the "digit" part is exactly the same as for an adder. The only difference is that instead of carrying on 1+1, we borrow on 0-1.
For a full subtractor, we need to consider the possibility of a second subtraction from the borrow. (Remember that borrowing is really just subtracting 1 from the next higher digit.)
| Input A (+) | Input B (-) | Borrow In (-) | Output Digit | Output Borrow |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
I'm not sure if you noticed this, but the "output digit" column is exactly the same as the 1's column for addition. So that entire part of our circuit can remain the same. For the borrow, it looks like it's going to be more complicated. I'll call the borrow bit "C" just because it's the third input and the first letter of "borrow" is already taken.
The four instances of a "1" in the rightmost column are in rows B, C, BC, and ABC. There are a few ways to build this circuit, but I'm actually going to go through how I would do it. (You may be starting to sense some hidden motives in me...)
That's certainly not the only way to think about it. Why did I go about it the way I did? Why didn't I let you just build the circuit yourself? Well, just take a look at what the subtractor ends up being:
Does that remind you of anything? Take a look at a circuit we used in part 1 not too long ago...
There are only two things that are different! There are two NOT gates, one on the "A" input and one coming off the top XOR gate. Why is subtraction so similar to addition? Well, there are two outputs: the 1's digit and the carry/borrow digit. For the 1's digit, I think it is similar to how turning 180° to the left is the same as turning 180° to the right. If a knob only has two positions, you can only either "keep it as is" or "change to the other position". It doesn't matter if you turn it clockwise or counterclockwise. But if it had ten positions, for instance, then the direction would matter (3 left is different from 3 right, although 5 still wouldn't matter).
Binary arithmetic is similar; you can only keep the bit as is, or flip it (0 -> 1 -> 0 -> 1 -> ...), possibly with a carry or borrow in the sequence. And even those both only happen in one circumstance each (carry at 1+1; borrow at 0-1). This is why the borrow part was so similar — in both cases, there are four ways to change the following bit (by carrying or borrowing).
It almost looks like the only thing different between addition and subtraction is that the "A" input gets inverted. In fact, if you flip A before sending it through, that gets rid of both NOT gates... but unfortunately it messes up the "1" bit. Because of how XORs work, though, all we need to do is put a NOT gate right after the second XOR gate.
What this all means is that we've essentially declared that to subtract, we need only invert both "A" and "1". So we could just re-use the same exact adder circuit, but just put NOT gates around the entire A input and... well, the entire output, because the borrow bits don't ever leave the circuit the way the digits do.
Now, I don't know about you, but to me that suggests a rather crazy idea. I said earlier that we are totally free to give bits whatever meaning we want. Here's my crazy idea: What if we drop the "left bit means positive/negative" system altogether, and instead represent a positive number by inverting all the bits? We'll still use the convention that the left-most bit being "1" means negative, but now, the remaining bits have to be inverted to make the number positive.
Then we might just be able to throw both positive and negative numbers through the same adder circuit as before! We would only need one circuit; if you want to subtract, you just put NOT gates before the second input. There might be some subtleties, though, so let's not get too excited too quickly.
We call this system 1's complement. Complements refer to two things that add up to a whole; for example, 35% and 65% are complements because they add up to 100%, and in geometry, "complementary angles" add to a right angle, 90°. The "1" in 1's complement refers to the fact that inverting a bit is like subtracting it from 1 (1-1 = 0, 1-0 = 1). You could also imagine a similar "9's complement" for base ten numbers, if you had a four-digit adding machine that could only go from 0000 to 9999; the 9's complement of 3763 would be 6236.
So instead of 6 being 0110, we write it as 1001. Then when we want to subtract 3, we add the bits 1001 and 0011 (the normal 3 for negative). Let's see, does that work? We get 1100... which corresponds to 3... yes, I think it worked!!
Actually, it's more common (and more reasonable) to represent the negative numbers by inverting them. So that subtraction of 6 minus 3 would really be 0110 + 1100, or 10010. Wait a second... even if we ignore that extra "1" on the front, that's 2, not 3!
What about addition of negative numbers? Let's try (-2) + (-3): 1101 + 1100 = 11001. That unfortunately looks like the inverse of 6, which is not what we wanted either. Hmmm... this isn't looking as good as we thought. But we're so close... maybe there's a way to fix it?
This inversion thing looked so promising, what went wrong? Well, how about you investigate this. Here's an exploration with 1's complement. (It's a normal unsigned adder that we're pretending handles signed numbers.) When does it give wrong answers? What wrong answers does it give?
Go on, experiment. There's a case that I almost missed myself when I was writing this. You don't have to try every combination, but at least experiment with numbers of different sizes...
So if you've earnestly experimented with that, you probably found either three or four possible Error values. It turns out that there are four: 0, -1, +14, and -15.
The +14 and -15 cases are suspiciously close to 16, which suggests overflow might be an issue. (You might have noticed the carry bit on the left side of the adder would signal a problem if overflow did happen.) If you haven't discovered the +14 case, it's okay; I almost didn't notice it myself. Go back to the exploration now and see if you can make it happen.
In fact, now might be a good time to make sure you know roughly when all of the four possibilities happen. Go ahead, try to put it in your own words. I'll even give you a hint for one of them.
Scroll down when you're ready. You won't be graded, but I encourage you to think about this and answer it yourself. Active learning is so much more beneficial than just passively reading an article and going "oh, yeah, okay, that makes sense..."
Here's what I found.
While I normally wouldn't care too much about overflow, I find it interesting that negative overflow is off by 14, not 15. When we add two negative numbers that overflow, we seem to be off by 2, but when we overflow once or cross into negative territory, we are off by 1.
There are two ways we can correct this problem. The first is what is known as the "end-around carry". Notice that there were two ways to get the -1 error: (negative + negative), or (positive + negative) with the positive number having larger size. In both of those cases, notice that the carry bit always seems to be green (it's on the left side of the adder, but we've been ignoring it). So real 1's complement hardware usually detects that carry, and if it is on, it gets added to the result. That is enough to fix the error in the non-overflow case, and 1's complement has been used by some computer systems. (The +14 error won't be fixed, but since there was overflow, there's nothing we can do about it anyway.)
The problem is that you need a second adder to do that. There's a second possibility, which is that we can adjust our negation process. Remember when I brought up the analogies of complementary percents? The complement of 35% is 65%, but the (two-digit) 9's complement of 35 is 64. If you think about a two-digit (base ten) adding machine, you don't want a number plus its negative to add to 99, you want them to add to 00.
So that leads to the second crazy idea: What if we correct for this by adding 1 when we invert all the digits? For instance, to form the negative of 35, we first take the 9's complement, 64, and then we add 1 to get 65. This would be called the "ten's complement"; its binary equivalent is the two's complement. Now notice that 35 + 65 = 100, which would be 00 if you only had two digits. Hey! No "end-around carry" required!
In binary, this means that to negate 3 = 0011, we first invert it to 1100, then add 1 to make 1101. This would definitely fix the problem of 3 + (-3), but what happens when we put other numbers through our "dumb adder"? Do they work as well?
I encourage you to enter some negative numbers. Here's a scratch textbox if you need to calculate the 2's complement of a number (I encourage you to do it yourself!)
Go ahead, try as many different special cases as you can...
You'll find this is a lot better! All we have are 0s and ±16s in the error field. We'll never be able to eliminate the 16s because of overflow, but at least it's a nice power of 2.
You might have also noticed we somehow have the number -8, but positives still only go up to 7. You also might have noticed that negative zero doesn't exist anymore:
-(0000) = (1111) + 1 = 10000 = 0000 (in 4-bit arithmetic)
But wait, there's more! There's a much simpler way of thinking about two's complement that explains why subtracting works the same way as adding. I don't want to overwhelm you with algebra, though, so we'll start with the simpler 9's and 1's complements.
0110 (6) and its 1's complement 1001 add up to 1111 (15). In other words, A+B = 15, or B = 15 - A.0110 (6) and turn the left bit on, giving us 1110. As a positive number this is 6 + 8 = 14, because we've turned the 8's bit on.1110 is negative 1.So what this means is that we can think of 1's complement as saying the leftmost bit represents negative 7. For two's complement, in addition to inverting the bits we are adding 1, so the complement equation becomes A + B = 16, and so 1110 is -2 = 14 - 16 = (6 + 8) - 16 = 6 - 8. So the leftmost bit has value -8.
It's important to remember that in 1's and 2's complement, all of the other bits always have POSITIVE value. 1010 in 2's complement is -8 + 2, or -6; in 1's complement the same bits would be -5.
This works for any number of bits. For example, in 8-bit two's complement, the leftmost bit has value -128, followed by positive 64, 32, 16, 8, 4, 2, and 1! Then 11001001 = (-128) + 64 + 8 + 1 = -55. (If you know that 11001001 as a normal positive number is 201, you can just subtract 28 = 256 to get the same answer -55.) That can store any number between -128 and +127 inclusive. (The extra negative number isn't usually that helpful, but the simplicity of the circuits definitely is.)
All right, so enough of me rambling. Here is a simple adder that's been turned into a subtractor. Notice it starts out by saying "0 + 15 (+1 carry in)". I've used the carry input (notice it has a NOT attached to nothing, i.e. NOT zero, i.e. 1) to get the "add 1" after inverting the second input, so we don't need a second adder. The text inside the adder is left as an addition, to emphasize that the adder doesn't know it's being used for subtraction. It's all about interpretation...
In fact, we can go one step further. Because we're using the exact same component for the tough work, we can add a simple extra bit to choose between addition and subtraction. I'll leave it up to you to figure out the finishing touches. You want Red to add, and Green to subtract. (Note that you can't avoid overflow. An asterisk, like Answer: -4*, means you should get -4 due to overflow.)
Hint: For the left four gates, you want to invert B if OPER is 1. Which gate does this? Remember to set all four to the same thing!
Oh, and there's no automated test here. I wanted to sort of take the pressure off because we've gotten so far already. In fact, if you just want to remember that this is possible and move on to part 3, that's fine.