Understanding Number Complement Systems

Alright class, in this one we're going to talk about complement systems for numbers. Complement systems are really interesting. It's basically, you know, given a kind of a fixed numerical range, you just use, you cut it in half. and you treat one half of it as negative numbers and the other half as positive numbers, even though they're all kind of written as positive numbers. And it really greatly simplifies doing subtraction or, you know, adding with negative numbers, which is pretty, excuse me, pretty cool too. Okay, so let's jump in. Complement systems work like an odometer on a car, right? So if you think of, you know, a brand new car whose odometer is at zero miles, right? If you drive the car forward three miles, right, it goes up to three. But you could also imagine... If you got in that brand new car and you put it in reverse and you drove backwards three miles, it would go to negative three, right? Well, no, because odometers don't have a negative sign in front of them. It would roll back over to like 999, 998, 997, right? that is exactly what a complement system is, right? We're going to take our numerical range, however many digits we have, and that is one of the keys here is that you can't just, like, arbitrarily extend a number. You have to have this fixed range of digits in mind already. Like, okay, I'm going to do, you know, a complement system with 10-digit numbers, right, or 5 or 6 or whatever it is. And then within that, you can do math. So let's take a look at how this works. The key to complement systems is this formula right here. The base to the number of digits minus the number you want to represent as a negative number. So let me explain. The base of course is your numerical base. So in base 10 in decimal, that's 10 in binary, that's two. So the number of digits, number... Yeah, we'll just have to do it this way. Number of digits in the number n, the one that you're trying to represent as negative, and n equals the number to represent as a negative number. So let's just do an example. We'll do base 10 and we'll go with three digits. So let's do the number 370. Okay, so this is our n. And of course our base is 10 and the number of digits in n is 3. So now we need to calculate this number based to the number of digits. That's exponent if you were wondering. That's how you write that. in like a text file so that's going to be 10 to the third which is 1000 okay so then the way you actually find the complement is you subtract this number from or rather n from this number so that means we're gonna do a thousand minus 370. And that math's not terribly hard to work out. Right, we've got 0. We've got 3. And then we have, let's see, nine, right? I think I did that, right? No, that's not right. Why did I say nine? Seven, right? 7.30, yeah. Now I did it wrong again. Six, gracious, wow. I swear I can do basic arithmetic, guys. It's just a little early in the morning. I was up for quite many hours last night and slept for very few and then got up early again. Okay, yes, we'll check our work here. So 30 plus 70 is 100. 400 plus 600 is a thousand. Good stuff. Okay. So this is our representation of 370 as a negative number, AKA this is negative 370 in our complement system. And you're like, but it looks like 630. Yeah, but it's not. It's negative 370. And for this sort of thing, right, for numbers above, you know, certain level, it doesn't work anymore, right? So remember, our range is four or three digit numbers. So we have numbers from zero to 999, right? Those are the symbols, right, we have to work with. And we're assigning values to those symbols, right? Well, and it's easy for some of the positive numbers, right? Zero is zero, one is one, two is two, 100 is 100, 200 is 200. 300 is 300. But then at some point you cross this halfway point where your numbers start to represent negative numbers, right? So this is negative 370. But what if this was one bigger, right? So if this was 371, this would be one smaller, right? Okay, so as the number that you're trying to represent as a negative gets larger, this is going to tend downward. So you have to find that crossover point, right? How could we represent, you know, 499? well, that's gonna be 501, right? So that's negative 499. And then you're like, well, how do you represent negative 500? Well, it can't be this, right? Because that's already positive 500. So that's our crossover point, right? You know, we have to have this place where we say, okay, that's it, that's all we can do within this range, right? Because again, remember, we're limited to three digits in this case. So that's our crossover point is 500. So 500 just represents positive 500, and 501 represents negative 499, right? So you have this jump from positive to negative. Okay, so let's go back to our initial example, and let's show why this is kind of... kind of nifty. So now that we have our representation of negative 370, let's do some subtraction. with it so we're going to say okay let's take i don't know 4 450 seems like a good number 450 minus 370 that's the problem we want to work out minus 370 but instead of doing it like this we're going to use our complement representation so we're going to change this to 630 and what's neat about complementation is that when you want to do negative numbers you still only add right so like this is 450 plus negative 370 even though this doesn't look like negative 370 that's what it represents right and then we just add right so we add this that's going to be 0 5 & 3 is 8 6 & 4 is 10 and then the rule is you discard this digit if it comes to exist right so if you have you know a digit here you get rid of it So away it goes. And there's our answer, 80. And that's right, right? 450 minus 370 is in fact 80. Kind of neat, huh? Maybe not the fastest way to do subtraction, right? But, you know, it works. So let's see here. It's not the fastest for us, right? But it's not the fastest for us because first we have to find the complement. And finding the complement isn't the most involved process, right? You just take, you know, power of 10. So like if you have three digits, it's a thousand. If you have four digits, 10,000. Five digits, it's 100,000. from that thing and that gives you your compliment note too if we use a smaller number like let's say we did 360 here and actually here let me just copy this Oh, and actually, let's just put a reminder here. This is negative 370 in our complement system. Let's do this one more time. So let's change this from 450 to something that's smaller than 370. Let's change it to, I don't know, 360. So the answer we're looking for should be negative 10. Let's see if that works out. So 360 minus 370. We've got 0. We've got 9. nine, we've got nine. So does that work? Is that the right answer? I don't know. It's hard to tell. And it's hard to tell because this answer is also in complement notation, right? So this is our negative number, right? And that makes sense. The answer should be negative. So the real question is, is this negative? And I think it's clear that the answer is yes, if we run this process backwards, right, 1000 minus, you know, 990, that's going to be 10. Okay, so that is in fact, negative 10. Actually, sorry, excuse me. excuse me, the other way around, 1,000 minus 10 is 990. So that gives us our representation of negative 10. So it works either way, whether the positive number is bigger, whether the negative number is bigger. All you do is find the complement and then add. And here's why that's like a really key advantage over sign magnitude, especially with binaries. If you think about the fact that our addition operation... is implemented as a circuit, right? Well, we can do addition with these signed numbers using the same circuit we use for unsigned numbers, right? Because all you do is add. What we need is the special machinery to find the complement, but as we'll see, that's not actually terribly complicated in binary either. So let's move on to binary. Okay, so the complement system solves one issue, which is the algorithm for adding with negative numbers can be simplified, right? You just add. You find the complement, and then you just add, and you discard that last digit if there is one. Okay, so how about binary? Well, binary, it's the exact same thing, right? Let's say we wanted to do negative 8, and we're going to go with... Um... 6-bit numbers this time. So the number of digits, I think I said earlier that this has to be the number of digits in the number N. That's not correct. Let me go back and revise that. Not the number of digits in the number N, just the number of digits. you're working with. So like in computers, this is going to be the word size. I think I mentioned that briefly in another video, like a 32-bit computer has 32-bit chunks of memory that it likes to work with. So it uses 32-bit numbers. A 64-bit computer uses 64. bit old computers were 8-bit right so like the nes entertainment the nintendo entertainment system right the very first like nintendo console it was an 8-bit uh processor and that's why people talk about like 8-bit games or 8-bit you know chiptunes or whatever so we're gonna go with 6 bits just because you know it's a little bit fewer so our our number of digits is 6 in this case and our base is 2 okay so we want to find negative 8 in binary so first we start with positive 8. So in six digits that's going to be 0 0 1 0 0 0. Not too bad. Now we want to find the complement. So we're going to take 2 to the sixth power. So let's find out what that is. And actually I'm just going to consult the Python programming language here. to ask that to to the sixth power so python uses star star for exponentiation not the carrot but it doesn't matter and that's 64. okay so what we want is we want zero in the ones place a zero in the twos place fourth place eighths place 16th place 32's place and we want a one in the 64th place okay so we got a scooch over which makes sense right okay so now we're just gonna subtract That's all we have to do. We're going to subtract, and that will give us the answer. And I'm going to put my subtraction sign in. Okay, 0 minus 0, that's easy, it's 0. Likewise, likewise. Alright, now we have to do some borrowing. So remember, you know, this goes away. Slash through it. This becomes a 10, a 1, and a 0, right? It's 2. We borrow from that. It leaves a 1 there. This becomes a 1, 0. We borrow from that. That leaves a 1 there. This becomes a 1, 0. We subtract from that. And we get a 1. This seems incorrect. One second, let me double check something. Okay, I got ahead of myself. This is perfectly correct. I just was forgetting. I didn't forget a step to do it. I just kind of forgot that a step is going to take place in a second that's going to make this look right. So. That's it, right? That's it right there. This is our negative representation. So this is negative 8. Notice that the leftmost bit here is still a 1. So even though this technically isn't a sign bit anymore, it will always be 1 for negative numbers, just because that's how binary works. Because each one of each, every time you add a bit you double the range of numbers that you can represent right if with only one bit you can represent two numbers zero or one with two bits you can represent four zero one two or three right um etc because of that And the fact that we're dividing our numerical range in half and saying the upper half is negative and the lower half is positive, well, the lower half of all of the binary numbers you can represent with six digits is going to be, you know, 0, 0, 0, 0, 0, through... 0, 1, 1, 1, 1, 1, right? And at that point, when you add one more, you have to roll over to using this and then a bunch of zeros, right? And so basically because of that fact, anything that starts with a 1, you still know that's negative. So that's really nice too, actually, for two's complement. If the leftmost bit is a 1, you know it's negative, even though technically it's not a sine bit anymore. Okay, so there's our representation of negative 8. Now... Doing this subtraction is still annoying, the fact that we have to subtract to find the complement. However... With this two's complement system in binary, there is actually a trick you can do. And the trick is very simply this. If we flip the bits, right, so a bitwise not, if you will, we negate all the bits, 1, 1, 0, 1, 1, 1, right? So flip, that's what's happening here. And then we add 1. Oops, let me do this. We will get the appropriate compliment. So that's going to be 0, right? Carry the 1. 1 and 1 is 0. Carry the 1. 1 and 1 is 0. Carry the 1. 1 and 0 is 1. And then these stay the same. And look at that. That is our complement. So finding the two's complement in binary is very easy. Flip the bits, add one. Aha, so now this makes sense circuitry-wise, right? Circuitry-wise, all we have to have to do two's complement addition and deal with negative numbers that way is we have to have a circuit which is capable. of flipping the bits of a number, and then we already have our addition circuit, right? So we run a number through the flip the bits circuit, then we throw it into our addition circuit and add one to it, and now it is a negative number, right? It's in its negative form, and it is ready to be added to any other number in our adding circuit, and we will get the correct result, right? So two's complement fixes the algorithmic complexity problem. Does it fix the negative zero problem? Yes, and it does it in a really clever way. the way that humans do it, right? It's very simply this, right? We said, hey, here's the formula for finding the two's complement of a number, but it's actually not the complete formula. The complete formula is this. if n is 0, the complement is 0. Otherwise, use this formula. So basically the answer is there is no negative 0 because we said so, right? 0 is just 0, and then if you want to complement some other number, you have to use this formula, right? So the complement of 0 is 0. So, two's complement solves both of the issues from sine magnitude. It's less algorithmically complex, therefore requiring less complexity. like circuitry, and it is capable of avoiding the whole negative zero fiasco. However, there's still an important issue with representation of signed numbers, and that is what if you add up two numbers that are big enough that they flow into your leftmost bit, right? So you can think about, like I said, the largest number we could represent positively in our decimal system was 500, right? That was our largest positive number. Well, what if you try to add 500 and 500? Well, you're going to get zero, right? Since we said our process is, you know, add and then discard that, like, overflow digit. So 500 plus 500, that's going to give us 1,000. And then we throw this digit away, right? So, hey, look at that. 500 plus 500 is zero. This is called overflow. And it's a bad thing. And it's something that can cause security flaws that can lead to vulnerability. vulnerabilities and exploits. So we're not really going to talk about that a whole lot today, but I just wanted to tell you that it exists so that later I can call back to it and say, hey, remember when we talked about overflow? Here's one of those times where it's real important to think about. All right, that's it for this one. See you in the next one.

Okay, so let's jump in. Complement systems work like an odometer on a car, right? So if you think of, you know, a brand new car whose odometer is at zero miles, right? If you drive the car forward three miles, right, it goes up to three.

But you could also imagine... If you got in that brand new car and you put it in reverse and you drove backwards three miles, it would go to negative three, right? Well, no, because odometers don't have a negative sign in front of them. It would roll back over to like 999, 998, 997, right? that is exactly what a complement system is, right?

We're going to take our numerical range, however many digits we have, and that is one of the keys here is that you can't just, like, arbitrarily extend a number. You have to have this fixed range of digits in mind already. Like, okay, I'm going to do, you know, a complement system with 10-digit numbers, right, or 5 or 6 or whatever it is.

And then within that, you can do math. So let's take a look at how this works. The key to complement systems is this formula right here.

The base to the number of digits minus the number you want to represent as a negative number. So let me explain. The base of course is your numerical base.

So in base 10 in decimal, that's 10 in binary, that's two. So the number of digits, number... Yeah, we'll just have to do it this way.

Number of digits in the number n, the one that you're trying to represent as negative, and n equals the number to represent as a negative number. So let's just do an example. We'll do base 10 and we'll go with three digits. So let's do the number 370. Okay, so this is our n. And of course our base is 10 and the number of digits in n is 3. So now we need to calculate this number based to the number of digits.

That's exponent if you were wondering. That's how you write that. in like a text file so that's going to be 10 to the third which is 1000 okay so then the way you actually find the complement is you subtract this number from or rather n from this number so that means we're gonna do a thousand minus 370. And that math's not terribly hard to work out.

Right, we've got 0. We've got 3. And then we have, let's see, nine, right? I think I did that, right? No, that's not right.

Why did I say nine? Seven, right? 7.30, yeah. Now I did it wrong again.

Six, gracious, wow. I swear I can do basic arithmetic, guys. It's just a little early in the morning.

I was up for quite many hours last night and slept for very few and then got up early again. Okay, yes, we'll check our work here. So 30 plus 70 is 100. 400 plus 600 is a thousand. Good stuff. Okay.

So this is our representation of 370 as a negative number, AKA this is negative 370 in our complement system. And you're like, but it looks like 630. Yeah, but it's not. It's negative 370. And for this sort of thing, right, for numbers above, you know, certain level, it doesn't work anymore, right?

So remember, our range is four or three digit numbers. So we have numbers from zero to 999, right? Those are the symbols, right, we have to work with. And we're assigning values to those symbols, right? Well, and it's easy for some of the positive numbers, right?

Zero is zero, one is one, two is two, 100 is 100, 200 is 200. 300 is 300. But then at some point you cross this halfway point where your numbers start to represent negative numbers, right? So this is negative 370. But what if this was one bigger, right? So if this was 371, this would be one smaller, right? Okay, so as the number that you're trying to represent as a negative gets larger, this is going to tend downward. So you have to find that crossover point, right?

How could we represent, you know, 499? well, that's gonna be 501, right? So that's negative 499. And then you're like, well, how do you represent negative 500?

Well, it can't be this, right? Because that's already positive 500. So that's our crossover point, right? You know, we have to have this place where we say, okay, that's it, that's all we can do within this range, right? Because again, remember, we're limited to three digits in this case.

So that's our crossover point is 500. So 500 just represents positive 500, and 501 represents negative 499, right? So you have this jump from positive to negative. Okay, so let's go back to our initial example, and let's show why this is kind of... kind of nifty. So now that we have our representation of negative 370, let's do some subtraction.

with it so we're going to say okay let's take i don't know 4 450 seems like a good number 450 minus 370 that's the problem we want to work out minus 370 but instead of doing it like this we're going to use our complement representation so we're going to change this to 630 and what's neat about complementation is that when you want to do negative numbers you still only add right so like this is 450 plus negative 370 even though this doesn't look like negative 370 that's what it represents right and then we just add right so we add this that's going to be 0 5 & 3 is 8 6 & 4 is 10 and then the rule is you discard this digit if it comes to exist right so if you have you know a digit here you get rid of it So away it goes. And there's our answer, 80. And that's right, right? 450 minus 370 is in fact 80. Kind of neat, huh? Maybe not the fastest way to do subtraction, right?

But, you know, it works. So let's see here. It's not the fastest for us, right? But it's not the fastest for us because first we have to find the complement. And finding the complement isn't the most involved process, right?

You just take, you know, power of 10. So like if you have three digits, it's a thousand. If you have four digits, 10,000. Five digits, it's 100,000. from that thing and that gives you your compliment note too if we use a smaller number like let's say we did 360 here and actually here let me just copy this Oh, and actually, let's just put a reminder here.

This is negative 370 in our complement system. Let's do this one more time. So let's change this from 450 to something that's smaller than 370. Let's change it to, I don't know, 360. So the answer we're looking for should be negative 10. Let's see if that works out. So 360 minus 370. We've got 0. We've got 9. nine, we've got nine.

So does that work? Is that the right answer? I don't know.

It's hard to tell. And it's hard to tell because this answer is also in complement notation, right? So this is our negative number, right?

And that makes sense. The answer should be negative. So the real question is, is this negative?

And I think it's clear that the answer is yes, if we run this process backwards, right, 1000 minus, you know, 990, that's going to be 10. Okay, so that is in fact, negative 10. Actually, sorry, excuse me. excuse me, the other way around, 1,000 minus 10 is 990. So that gives us our representation of negative 10. So it works either way, whether the positive number is bigger, whether the negative number is bigger. All you do is find the complement and then add. And here's why that's like a really key advantage over sign magnitude, especially with binaries.

If you think about the fact that our addition operation... is implemented as a circuit, right? Well, we can do addition with these signed numbers using the same circuit we use for unsigned numbers, right?

Because all you do is add. What we need is the special machinery to find the complement, but as we'll see, that's not actually terribly complicated in binary either. So let's move on to binary. Okay, so the complement system solves one issue, which is the algorithm for adding with negative numbers can be simplified, right?

You just add. You find the complement, and then you just add, and you discard that last digit if there is one. Okay, so how about binary?

Well, binary, it's the exact same thing, right? Let's say we wanted to do negative 8, and we're going to go with... Um... 6-bit numbers this time.

So the number of digits, I think I said earlier that this has to be the number of digits in the number N. That's not correct. Let me go back and revise that.

Not the number of digits in the number N, just the number of digits. you're working with. So like in computers, this is going to be the word size.

I think I mentioned that briefly in another video, like a 32-bit computer has 32-bit chunks of memory that it likes to work with. So it uses 32-bit numbers. A 64-bit computer uses 64. bit old computers were 8-bit right so like the nes entertainment the nintendo entertainment system right the very first like nintendo console it was an 8-bit uh processor and that's why people talk about like 8-bit games or 8-bit you know chiptunes or whatever so we're gonna go with 6 bits just because you know it's a little bit fewer so our our number of digits is 6 in this case and our base is 2 okay so we want to find negative 8 in binary so first we start with positive 8. So in six digits that's going to be 0 0 1 0 0 0. Not too bad. Now we want to find the complement. So we're going to take 2 to the sixth power.

So let's find out what that is. And actually I'm just going to consult the Python programming language here. to ask that to to the sixth power so python uses star star for exponentiation not the carrot but it doesn't matter and that's 64. okay so what we want is we want zero in the ones place a zero in the twos place fourth place eighths place 16th place 32's place and we want a one in the 64th place okay so we got a scooch over which makes sense right okay so now we're just gonna subtract That's all we have to do. We're going to subtract, and that will give us the answer.

And I'm going to put my subtraction sign in. Okay, 0 minus 0, that's easy, it's 0. Likewise, likewise. Alright, now we have to do some borrowing. So remember, you know, this goes away.

Slash through it. This becomes a 10, a 1, and a 0, right? It's 2. We borrow from that. It leaves a 1 there.

This becomes a 1, 0. We borrow from that. That leaves a 1 there. This becomes a 1, 0. We subtract from that. And we get a 1. This seems incorrect. One second, let me double check something.

Okay, I got ahead of myself. This is perfectly correct. I just was forgetting.

I didn't forget a step to do it. I just kind of forgot that a step is going to take place in a second that's going to make this look right. So.

That's it, right? That's it right there. This is our negative representation. So this is negative 8. Notice that the leftmost bit here is still a 1. So even though this technically isn't a sign bit anymore, it will always be 1 for negative numbers, just because that's how binary works. Because each one of each, every time you add a bit you double the range of numbers that you can represent right if with only one bit you can represent two numbers zero or one with two bits you can represent four zero one two or three right um etc because of that And the fact that we're dividing our numerical range in half and saying the upper half is negative and the lower half is positive, well, the lower half of all of the binary numbers you can represent with six digits is going to be, you know, 0, 0, 0, 0, 0, through...

0, 1, 1, 1, 1, 1, right? And at that point, when you add one more, you have to roll over to using this and then a bunch of zeros, right? And so basically because of that fact, anything that starts with a 1, you still know that's negative.

So that's really nice too, actually, for two's complement. If the leftmost bit is a 1, you know it's negative, even though technically it's not a sine bit anymore. Okay, so there's our representation of negative 8. Now... Doing this subtraction is still annoying, the fact that we have to subtract to find the complement. However...

With this two's complement system in binary, there is actually a trick you can do. And the trick is very simply this. If we flip the bits, right, so a bitwise not, if you will, we negate all the bits, 1, 1, 0, 1, 1, 1, right? So flip, that's what's happening here.

And then we add 1. Oops, let me do this. We will get the appropriate compliment. So that's going to be 0, right? Carry the 1. 1 and 1 is 0. Carry the 1. 1 and 1 is 0. Carry the 1. 1 and 0 is 1. And then these stay the same.

And look at that. That is our complement. So finding the two's complement in binary is very easy.

Flip the bits, add one. Aha, so now this makes sense circuitry-wise, right? Circuitry-wise, all we have to have to do two's complement addition and deal with negative numbers that way is we have to have a circuit which is capable. of flipping the bits of a number, and then we already have our addition circuit, right? So we run a number through the flip the bits circuit, then we throw it into our addition circuit and add one to it, and now it is a negative number, right?

It's in its negative form, and it is ready to be added to any other number in our adding circuit, and we will get the correct result, right? So two's complement fixes the algorithmic complexity problem. Does it fix the negative zero problem? Yes, and it does it in a really clever way.

the way that humans do it, right? It's very simply this, right? We said, hey, here's the formula for finding the two's complement of a number, but it's actually not the complete formula. The complete formula is this.

if n is 0, the complement is 0. Otherwise, use this formula. So basically the answer is there is no negative 0 because we said so, right? 0 is just 0, and then if you want to complement some other number, you have to use this formula, right?

So the complement of 0 is 0. So, two's complement solves both of the issues from sine magnitude. It's less algorithmically complex, therefore requiring less complexity. like circuitry, and it is capable of avoiding the whole negative zero fiasco. However, there's still an important issue with representation of signed numbers, and that is what if you add up two numbers that are big enough that they flow into your leftmost bit, right?

So you can think about, like I said, the largest number we could represent positively in our decimal system was 500, right? That was our largest positive number. Well, what if you try to add 500 and 500? Well, you're going to get zero, right?

Since we said our process is, you know, add and then discard that, like, overflow digit. So 500 plus 500, that's going to give us 1,000. And then we throw this digit away, right?

So, hey, look at that. 500 plus 500 is zero. This is called overflow. And it's a bad thing.

And it's something that can cause security flaws that can lead to vulnerability. vulnerabilities and exploits. So we're not really going to talk about that a whole lot today, but I just wanted to tell you that it exists so that later I can call back to it and say, hey, remember when we talked about overflow? Here's one of those times where it's real important to think about. All right, that's it for this one.

See you in the next one.

Transcript for:Understanding Number Complement Systems

Transcript for:
Understanding Number Complement Systems