[MUSIC]. Now that we've seen a basic encoding. Let's turn our attention to encoding integers. And we're going to talk about both unsigned integers positive numbers, as well as signed integers. Integers that can represent both positive and negative values. Let's start with a basic example of binary number representation. Here we see an 8 bit value represented by 8 binary bits labelled b7 through b0. The most significant bit to the least significant bit. The reason we call them most significant and least significant, is you'll notice that b0 is a coefficient on 2 to the 0, or 1. This represents the ones column of the number. And b1 is the twos column of the number. B5 is the 32s column. And B6 is the 64s column, and so on. A useful formula to remember is that if we have an n bit quantity, then the largest number we can represent is 2 to the n minus 1. In the case of 8 bits, with n equal to 8, that would be the number 255. Namely, 128 plus 64 plus 32 all the way down to plus 1. So let's take a look at a simple example of addition and subtraction. using basically the normal carried borrow rules that we use for decimal addition and subtraction. Only in this case, since we have base-2 numbers, we'll be doing things with only the digits 0 and 1. Here's an example, 63 plus 8. Is of course equal to 71. The number 63 is represented by these bits. The number 8 is represented by these bits and you should make sure that, that makes good sense to you. And when we add them up, you'll notice we'll do a 1 and a 0 as a 1, a 1 and a 0 is also a 1. A 1 and 0 again is 1. But now a 1 plus 1 in this column yields a 0 with a carry of 1. So, we now add 1 0 plus the carry of 1 yields a 0 again, but a carry of 1. So we do 1 plus 1 plus 0, again yields a 0 with a carry of 1 that ends up in this position. And this is the number 71, our result. To do subtraction we do something very similar. Let's take, let's say we have the number 12 in binary and we wanted to subtract 7. 7 is represented by 0111. And so if we do the subtraction we would say 0 minus 1, of course is a 1 with a borrow of 1. 1 minus 1 is a 0 and a 0 now because we borrowed earlier. 0 minus 1 is a 1 again. Without and we leave this as a 0 so the result is 0101 which is in fact equal to the number 5 what we'd expect, okay. So, that's the basics of addition and subtraction in binary. So let's do the natural thing for representing positive numbers. they're going to rep, they're going to correspond to all the unsigned integers of the same value. So in 8 bits, for example, we can go from the x00 to the x7F and represent 127 different positive number. But since we need about half of them to be negative. We're going to to save the other half from 128 to 255 to really be used to represent negative numbers rather then those larger positive numbers. So we're going to use the high order bit, that b7, to indicate whether a number is negative or not. And often that most significant bit is the sign bit. This is called a sign and magnitude representation. Let me give you a few examples. Here we have the number 0 and you'll notice that it has a 0 in the most significant bit. So it's non-negative because the sign bit is 0 and the value is 0. Here we have another postitive number a non-negative number. where except for the sign bit, all the other bits of 1. That corresponds to the number 127. Okay. Now the other 2 numbers in these examples are both negative numbers. They have a 1 in the most significant bit. And can be used to represent for example a minus 5. In this case, this is the number 5 but we're saying it's negative. So we're going to basically just use that sign bit to say whether we put a minus sign in front of it or not. In this case we have minus 0. Which get's into one the problems of sign and magnitude notations. There's the 2 representations for 0. The first line here was the positive 0. This is the negative 0. Well they're both 0s so this kind of, this will cause some problems for us if we use this representation. Okay, so let's talk about sign and magnitude negative numbers in a bit more detail. Here I'm showing a number wheel for 4-bit binary numbers. It starts at 000, and as we increment by 1, we move around to 1111. And of course if we continued to increment we'd go back to 0000. Now, what I've also noted on the outside of the circle is the number corresponding to each bit pattern. So you see here, we have our 0, 1, 2, 3, all the way around to 7 and then we have the negative numbers on this side with the first bit being a 1. Alright, so a minus 1 in binary is always represented by the inside magnitude binary with a leading 1 for the sign. And then a value of 1 for the remainder of the bits. Okay, for the magnitude. All right, so, the unfortunate side effect of this, as we've said, is that we have 2 values for 2 values that correspond to 0. A negative 0 and a positive 0. So why is this an issue? Well it makes math a little cumbersome. Let's take a look at a little example. If I do 4 minus 3 that corresponds to the number 4 here 0100 minus 0011. And if we do the arithmetic for that, of course we see that the value is 1. But now if we look at the nu-, the 4 plus minus 3 which should yield the same result, we see that in fact, 4 plus a minus 3 yields minus 7. Well that's not the same as 1. so we now would have to worry about how, what order in which we do the additions and subtraction. this is not something that we want to be dealing with when we think about arithmetic in our programming languages. So instead of using sign and magnitude numbers computer systems today use what is called Two's Complement negatives. And let's go back to that representation of a minus 1. So instead of using the sign bit at the front to, the most significant bit to just represent the minus sign in front of the 1. What we're going to do is give that most significant bit a large negative weight. Alright remember each of the bits has a certain weight corresponding to the column that they're in. So bits 0 through the second to last bit represent the values 1, 2, 4, 8, 16 and so on. Well what were going to do is have the most significant bit represented as the W minus 1 bit. Or in this case would correspond to that b7 we had in our previous slide when W is equal to 8. It would actually add a na, a negative weight to the number. In this case, the negative weight would be minus 128. 2 to the 7th is 128. And then minus 128. So let's take a look at an unsigned number here. 1010, that corresponds to 1 times 2 to the 3 plus 0 times 2 to the 2 and so on to yield the number 10 decimal. In 2's complement, 1010 would be interpreted a little bit differently. You notice that now we have a minus 1 for the first bit, the most significant bit. Alright? That's that large negative weight. In this case minus 8. So that when we add this up we see that this corresponds to the negative number 6 in base 10. using two's complement notation. So a minus 1 is represented as 1111, right. Minus 8 plus 7 for the remainder, so that would add up to minus 1. All right, so that looks, a lot like, we solved our problem here because what we've essentially done is shifted our number wheel a little bit. So now the numbers are the same on the right hand side. You see we go from 0 to plus 7 but the numbers with deleting 1 are now in a different order then they were before. We started minus 1 up here go around to minus 2 to minus 3 to minus 4. [COUGH] All the way to minus 8. What's important to note here is that now we only have one representation of 0, namely all the bits are set to 0. And you'll notice that minus 1 is immediately adjacent to 0. So, it looks like things can flow on a number wheel by doing basic addition and subtraction, and get that to work. For example, if I start at 2 and take three steps back I do in fact get to minus 1. That wasn't the case with sign magnitude notation. The other nice thing about two's compliment notation is that its very easy to obtain the negative number from its positive of magnitude. All I have to do is take a bit wise complement of the number, of the positive number and add 1. And that gives me the negative version of that original number. Interesting interesting fact that makes it very easy to take the negatives of numbers. Okay, so let's take a look at 2's complement arithmetic in some more detail. What's nice about 2's complement is the same addition procedure now works for both unsigned and 2's complement integers. So we only have to build one kind of adder in our processors. Let's take a look at the example 4 plus 3. Here we have the positive number 4 the positive number 3. We do a straight addition and we get a result of 7. That works out well. On the righthand side we have minus 4 plus 3. 'Kay, you'll notice that when we add that up we get all 1s. That corresponds to minus 1. That's correct as well. Now let's take a look at the middle here. 4 minus 3 that's the example we did before that should have yielded 1. And now with 2's compliment numbers we have a 40100 but our minus 3 is 1101. And when we add this up we get the result, 0001. Of course we do have a carry out of 1 that we're going to drop. And because we have our 4 bits of precision here. And the result is 0001. Exactly the value we expected to see. the drop and carry makes this modulo edition. So we say that this is addition modulo 2 to the w, or modulo modulo 256, in this case, with w equal to 8. Or in the examples here with w equal to 4, it's modulo 16. Why does 2's complement notation work out so well? well, let's try to look at it a different way. Whenever we have a positive integer we'd like the negative number representation of that same integer. to always add up to 0 if we sum it with the positive version. So let's take a look at the numbers 00001. what we have to add to that in order to get all zeros, right. What we really want to be negative 1 is whatever bit pattern gives us that same result. And we know now that, that in fact is the pattern all 1s. Which when we add will cause a carry to ripple down this entire sequence of one's to yield all 0s with a carry out of 1. That we'll be dropping and ignoring, because we do modular 256 arithmetic. In the case of the number two, we want the number minus 2 here. What bit pattern would yield that? Well, we'd expect it to have a 0 here. So that 0 plus 0 would come out to 0. [COUGH]. Then a 1 in the second position, so that one plus 1 is also a 0. And then a sequence of 1s to ripple that carry through. So a minus 2 looks like this value, okay. And you'll notice that that's just the bit pattern of the number 2 complemented and then adding a 1. So if we complemented every one of these bits. We would get 111101, but then when we add 1, we would actually get this value here, which is our minus 2. And then for 3, it's the same situation. The pattern that, the pattern that would yield all the 0s looks like this. Which you'll notice again, is just a bit wise compliment of the original 3 plus 1 added in. Okay, so that's how 2s compliment works. If we look at these numbers now in terms of the possible big patterns that we can have in four bits. From 000 to 1111, we'll notice that for the first 7 numbers the positive values, signed and unsigned numbers are exactly the same. But now for unsigned, we continue on to 8, 9, 10 all the way up to 15. While for signed representations, the value that would have been 8 now corresponds to minus 8. And the value that would have been 15 corresponds to minus 1. Now, of course both signed and unsigned integers have limits. There's only so far we can go until we run out of patterns to use. So, for example, if we tried to add 6 plus 4, the result would be 10, and we could not represent that as a signed number. There's just not enough bits to do that. You notice that there is no pattern that corresponds to the number 10. If they were unsigned numbers we could, because we have a pattern of 10, for ten. in seeing we also use the notation 15u to signify an unsigned number. In this case 15u plus 2u. Yields 17 and that would not fit into any of our representations, signed or unsigned. Okay. We can also have a number that is too small for example minus 7, minus 3 unsigned would yield as signed numbers would yield minus 10. And you'll notice that there is no pattern for minus 10. We only get up to to minus 8. And then if they were unsigned we still have a problem because 0 unsigned minus 2 would be negative 2. Well we cannot represent negative numbers in unsigned formats. So we'd be in trouble there as well. So the CPU. when it's when it's given this kind these kinds of arithmetics to do will throw an exception. Meaning it will signal that it got a number that it can't represent. and it does that for signed values. But most CPUs do not do this for unsigned values. And, C and Java, both languages, will just cruse along and not bother checking that the arithmatic was correct or not. So you have to do an explicit check if you really want to know if the arithmatic worked out correctly. And we'll see that again later on. Alright, jsut a quick visualization of what is going on here. If we start off with a 2s complement number that can go from minus 2 to the w minus 1 to plus 2 to the w minus 1. When we move it to unsigned value a represented as an unsigned value. Of course those positive values stay the same but the negative numbers now look like big positive values. 'Kay. And similarly, going in the other direction. If we start with an unsigned number, the smaller numbers can just move straight across the 2s complement notation. But the large positive numbers, the ones that start with that leading 1. Now get interpreted as negative numbers, if we think of the representation as 2s complement. So, we have to remember which type of number we have in memory. Is it a 2s complement number or is it an unsigned integer? And that's part of how we get into types in these different languages data types in these different languages. Here were showing the addition of 2 numbers can yield a value that's very negative or a value that's very positive. the values again that are in teh midrange can just move straight alogn no problem to the 2s compliment representation. But the very large positive numbers get interpreted as negatives. The very large negative numbers end up getting interpreted as big positives. Okay, so that's where we would run into trouble in our arithmetic if we generate too large a number, or too negative a number. Okay, some values to remember when we're thinking about integers is for unsigned values. we have a special value called UMin, which is the smallest number we can represent that's 0. The pattern of all 0's and the maximum, UMax is the unsigned max, is all 1s obviously. And that would correspond to the 2 to the w minus 1. While in 2's compliment TMin is 2's compliment minimum is the biggest negative number we can have which would be the pattern of 1 all 0 followed by all 0s. And then TMax is 0 followed by all 1s. So the maximum numbers only half as big as it was before the unsigned values. And a negative 1 is represented by the sequence of all 1s. Ffff we would do in 32 bits. Okay. So for a word size of 16, we would see these value for UMax, TMax, and TMin. these would be the x representations of them and their binary representations.