0:20

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.

3:59

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.

5:48

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.

7:13

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.

8:56

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.