In the last two units, we've seen how to represent integers as binary numbers using bits and how to manipulate them, how to add them. But so far, we only discussed positive numbers. And of course, our computers will have to deal also with negative numbers. So how can we deal with them? So let's take for an example the case of 4 bits. So we know there are 16 possible value there and what we done so far we manage, we, we presented the integers between 0 and 15. All 16 numbers of them using the 4 bits. In general, so far if we had N bits. We try, we use them to represent the positive integers between 0 and 2 to the N minus 1. If we want to represent negative numbers, we will need to give up part of these 16 possibilities in order to represent negative numbers. So maybe eight of them will be positive and eight of them will be negative or something like that. So how can we do that? Well the simplest thing you may consider and it was used at sometimes was to basically take the first bit and use it as a sign bit. And then you remain, you have three more bits or n minus 1 more bits in general to represent the actual number. So this way, if it starts with 0, it's going to be just positive numbers. If the first bit is 1, then the next three bits, and it's going to be a negative number, that is represented by the next three bits. In this case, we can represent 0, 1, 2, all the way up to 7. And then, negative 0, negative 1, all the way up to negative 7. So, this would be one possibility of representing negative numbers. A possibility that is not very popular. Why? There are a bunch of problems with it. One thing that you may immediately notice, this is very inelegant. We have negative 0. What is this negative 0 and why is it different than 0. What we learned in math was that 0 equals negative 0. So of course, we may in principle decide to have two representations of 0 in our computer, but that is inelegant and probably means that there's going to be prob, trouble. Usually, if you have something that's not elegant, it's going to bite you. And in fact here, if you actually try to manipulate these kind of negative numbers. Using some kind of hardware, you'll get into trouble. You'll need to explicitly deal with pluses and minuses, and the whole thing will be a mess. So hardly anyone uses thispossi, this anyti, anymore. Here is what people use instead. They use a system called 2's complement, and it has a very simple idea. If you want to represent a negative number, negative x, you just instead repre, use, repre, represent a positive number, 2 to the n minus x. In our case of 4 bits, 16 minus x. Which is going to be a num, a positive number and you are going to present it like we've seen so far. So, for example, in our case here are the numbers. You have 0, 1, 2, all the way up to 7 as usual. Now, if you want to represent, let's say negative 3. Well you represent negative 3 by the integer 16 minus 3, which is 13, so if you look at the place 1101, which is really the binary number 13, the value of that is negative 3. So this is basically the table that we have so far, and this system is called 2's Complement representation. So let's look what we get in this representation. First of all, the positive numbers that we have are half of what we previously had. Basically, we're missing a bit, so we can represent on that the numbers up to 2 to the n minus 1, but rather up to 2 to the n minus 1, all that minus 1. The negative numbers, in this system, we get one more of them. So we get all of the negative numbers between negative 1 and negative 2 to the n minus 1. And in our case, we get the negative numbers between negative 1 and negative 8. But we get only the positive numbers between 0, 1 and 7. And of course we have the 0 as usual. So the main thing that's nice about this trick is that we will basically get our addition and subtraction and almost all the operation that we need to do with numbers almost for free. So let's see what does that mean. Suppose that we want to add two numbers. What we're, what I'm going to show now that if we just use the same addition circuitry that we built so far. We'll magically get the correct result. And this is true not only of this example but in general. So let's look what happens if we just take negative 2 plus negative 3 using our circuitry that was not designed for, for negative numbers but just designed for positive numbers as we've done in the last unit. So here's what happens. So negative 2 plus negative 3 is, if we use 2's complement, that's really 14 plus 13. So, 14 plus 13, we know how to add in binary. We get the two binary numbers and just we add them using the previous circuitry. So here is the sum, if we just use the previous thing, here is the usual sum of these two numbers. Now notice that there was a carry bit, the one that is in green there, that usually in our circuit we threw away. So what does that mean? So really the output that we get is 1011, and the most significant 1 was thrown away. So what does that mean? [COUGH] Well, the original result without throwing the carry bit is really the number 27. Which is what it should be, the sum of 14 and 13. Once we threw that away, we lost 16, because the next bit that was thrown away, equals16. So what we get is only 11. Now what's nice about 11? So basically what our hard work computed was that 14 plus 13 equals 11. What is nice about 11? Well 11 in 2s compliment really represents the number negative 5. And this is exactly what we needed to do. So amazingly we got the correct result without doing anything new. Now how does that happen? Why does this magic happen? Will it always happen? Well as we saw in the last unit, our addition is anyway modulo 2 to the n. That is because we throw the overflow bits. The result that we get is correct up to an additive 2 to the n at the additive factor. And our representation is also modulo 2 to the n in the sense that we represent two numbers as equal. Negative 3 and 13 are equal up to an addition of exactly the same 2 to the n. And since both the representation and addition have the same convention, then they exactly fit and we don't need to do anything else. But immediately our hardware that was designed as previously just for positive numberage, just works like it is. So one thing we may still need to do is given the number gets its negation. So given is input x and the binary number could output its negative, the number negative x, again it 2s complements. Why would we want to do that? Well for one thing, remember that we still didn't see any circuit that does subtraction. But once we can solve this problem then definitely we have already solved the subtraction problem. because if you want to do y minus x, you just need to add negative x to y. And addition we already know how to do. So once we can compute negative x from an input x, we've already solved the subtraction problem, and that's a good thing, because we don't have to build new hardware for it. So the basic idea of how to do this kind of neg, negation in 2s complement is very simple. It uses a mathematical trick that 2 to the n is actually 2 to the n minus 1 plus 1. And thus we can rewrite negative x, which is really 2 to the n minus x in 2s compliment as 1 plus 2 to the n minus 1 minus x. That may seem completely crazy. What have we gained so far? But here is one very nice thing about this. 2 to the n minus 1. If you look at that as an integer number, better as a binary number, better presented as bits as all one bits. So with just one 1111 and bits of 1. What's so nice about that? It's very easy to subtract a number from this because you never need to borrow anything. So, in order to represent 11111 in binary minus any x. You just need to flip each one of the bits. It's very simple. You never need to borrow from the next time. So, this is a very simple boolean operation, just negation. Once you've done that, now we only need to add 1 and this is very nice because we already know how to add in general. So, of course, we know how to add 1. So now we've seen that using this very simple trick, basically we can now do subtraction. Again, just by the fact that we know how to do addition. So let's see an example. Let's see how we can design a boolean, boolean hard circuitry that takes as input x and produces as output negative x in 2s compliment. For example, takes 4 as input and produces negative 4. So again, what would negative 4 be in 2s complement? It would be the bits 1100, which would represent 12, which is 16 minus 4, is the way we are going to represent negative 4 in 2s complement. So, how are we going to do that? Well, our input is 0100. That's 4. Remember the first thing that we did, we needed to do to the n minus 1, the all 1s bit and subtract our number from it. So this is the first thing we do. We take the all 1s and subtract the number from it and then we just flip the bits and we get the result. Now we need to add 1. So we just add 1 to it. And we know how to add 1, and we got the new number, exactly what we needed to get. Our num, the number 12 that is the number -4. Now, in general we need not worry too much how to add 1 to a given number, because we know how to add any, a, a, the any numbers. But this is a special case, so it may be worthwhile to actually note what happens, how do we add a sin, 1 to a number. Well, if you look what happens if you just do addition, well, you start adding 1, if the left, rightmost bit is 0, you just turn 0 to 1 and you've got your new number. If it's 1, you turn the 1 to a 0 because you add 1 plus 1, and then you have a carry. And you move to the next bit from the right. And again, if it's 0, you turn it to 1. If it's 1 you turn it to 0, but you need to keep on going because you have another carry. So in general basically, in general what you do for the special case of adding 1 to a given number, you start from the rightmost bit. You keep on flipping bits until you reach a 0 that you flip to 1. And at that point you stop. And that's the very simple hardware to manipulate, you don't, to actually build. You don't need to write the completely general addition circuitry although you may. And we got our result. So, we finished now to say how we deal with negative numbers. And the most important point is, that we don't need to new, do anything new really. We just need to understand what we're doing. And everything that works for positive numbers will keep on working, as long as we're careful enough about that. And now we're ready to actually design the arithmetic logic unit of the computer, and we will not really need to do any special thing, neither to subtract numbers nor to have the negative numbers. They will all be taking care of themselves once they, we understood these ways to represent negative numbers
