More on Two Complement Representation
Hello and welcome. In this lecture we're going to look at some more details of
two's complement representation of signed integers.
Here is a quick recap of some topics related to this lecture,
that we have seen earlier. We've seen how integers are represented in a computer.
And, we've seen this for both unsigned integers and signed integers.
In this lecture, we're going to look at a bit more closely,
at two’s complement representation for signed integers.
We have already seen this earlier slightly sketchily.
We are going to look at it a bit more closely today,
And, we are also going to see how the magnitude of negative integers,
represented in two's complement representation can be computed.
So now for signed integers
we've already seen that we could treat the most significant bit as the signed bit and
if the most significant bit is 1, then we could treat the integer as a negative integer,
and if the MSB is 0, we could treat it as a positive integer.
This representation is also called the Sign-magnitude representation, for obvious reasons.
And, we have seen similar examples earlier,
where, here I am trying to represent integers using 3 bits,
and I have arranged the integers along a circle. As an unsigned integer this represent 0,
this represents 1, 2, 3, 4, 5, 6, 7. So, I have represented the binary representations of these
unsigned integers along the circle in this order 0 to 7,
and now I want to interpret these sequences of 0's and 1's
as two’s complement representation of integers.
So, here are the MSB 0 representations.
Here are the MSB 1 representations, and in the signed magnitude,
the MSB just gives you the sign the rest of it gives you the Magnitude.
So, we've seen that this corresponds to +0, +1, +2, +3, and then -0, -1, - 2, -3.
We have also seen that this basically corresponds to two increasing directions
one in this way and the other in this way.
These are two different increasing directions,
and it also gives rise to these wasteful representations,
where we have two representation of '0'. Now, before we go to two's complement representation,
We would like to ask that, 'Well, How else could we represent negative integers in binary?'
So using the MSB to represent the sign is really convenient,
because we could just look at one bit and tell whether the number is positive or negative.
And so, here is our circle again, and if we say that our MSB still represents the sign,
so we know that these are +0, +1, +2, +3. Now what about these.
Here the MSB is 1, and so these must represent negative integers.
But, what negative integer should be let each of these sequences of 0's and 1's represent?
So for example, what negative number should ' 1 0 0 ' represent?
What should ' 1 1 1 ' represent? and so on. In trying to answer this question,
what we might want to think of this circle as a wrapped-around number line.
So, if you think of this circle as a wrapped around number line,
then I can see that from here to here
the numbers are increasing +0, +1, +2, +3. These are going to be negative integers.
So, can I somehow think of this circle? Can I somehow unwrap this circle into a number line,
such that along the number line I get 0, 1, 2, 3 at these positions,
and these correspond to negative integers,
and still I can think of the unwrapped circle as a usual number line.
So, in order to break up a circle into a number line,
we have to figure out where to break this circle?
Now there are two logical points to break, where the MSB is changing.
So, this is one point where I am going from 1 to 0.
And, this is the other point where I am going from 0 to 1.
Now, if I broke the circle at this point, then I would get a number line,
which starts like this 0, 1, 2, 3 and then there are four numbers, which if I assume
there must to be representing the sign should be negative numbers.
So, my number line would now look like this,
Right. So, I have broken the circle here.
So I get 0, 1, 2, 3 and then I get these numbers with the blue MSB,
and if I want to treat this as a number line and
say that well, the numbers are increasing this way. What you will see is that, here
I must have something which is greater than +3. And, so really there is no space for negative integers.
So, I want to take this circle and unwrap it as a number line,
This is not a good place to break.
if we want these four binary sequences to represent negative integers.
So what is the other logical point. The other logical point is here.
So let see what happens if we break the circle there.
So now we going to break the circle there, and that
gives raise to this number line, where we start-off with the binary sequences, with the blue MSB, MSB of 1.
and then we get the binary sequences with red MSB. MSB of 0,
and these, we already know are +0 ,+1 ,+2 ,+3.
Because, we want to treat the MSB as the signed bit,
and when the number is positive,
we just want to treat the number as it's an unsigned integer.
So now the question is that given this number line.
Clearly, we can find out the direction in which, the numbers are increasing.
That is the increasing direction. So now, what negative numbers,
what negative integers should I place here, so that I get an increasing number line,
I get consecutive integers, and I am also able to represent negative integers.
Clearly, the choice is obvious. This will be -1, -2, -3, -4, and you can see that,
this is now consistent with the increasing direction.
I have represented consecutive integers,
and all of them are increasing in this direction. So, this is what motivates the two's Complement representation.
We are going to try to represent negative integers, such that this corresponds to -4,
this corresponds to -3 , this corresponds to -2 , this corresponds to -1.
Because, this allows us to break this circle at this convenient point,
and then treat this unwrapped circle as an increasing number line.
So this is the picture that we have seen earlier.
Along the circle, I am going to put -4, -3, -2, -1. So, this gives me one completely increasing sweep,
as I go around the circle, in this direction, and of course at the end,
when I come back from +3 to -4,
There is a wrap around. In terms of our previous picture,
the number line picture, this is really going back from end to this end. Right.
'0 1 1' to '1 0 0'. +3 to -4.
And, it easy to see, that we can now represent 8 numbers, using 8 combination of 3-bits.
So there is no wastage, and we have only one representation of 0.
Now, an interesting questions that comes here is that, when the numbers were positive,
we could just read-off the numbers as if they were unsigned integers,
and put '+' sign before to get signed integer.
Now, when the numbers are negative, we have this strange thing,
that '1 0 1' which is an unsigned integer would represent 5, and if we just look at magnitude,
which is the bits in black, it would represent 1.
But, we want this to represent the signed integer '-3'.
Similarly, If you look at this number '1 1 1', as an unsigned integer it could represent '7'.
If you just look at the magnitude which are bits in black, it would represent '3'.
But, we want to this represent as '-1'. So a question to ask is that,
Can we have a mapping of the binary representation to the magnitude of the negative integers?
So, we would like to go from this ' 1 1 ' to 1, I would like to go from this ' 1 0 ' to 2,
from this ' 0 1 ' to 3, and from ' 0 0 ' to 4. So, how do we come up with this mapping?
So, this is our desired mapping. When we are using 3 bits ' 1 1 ' should map to 1.
Remember, I am just interested in the magnitude now.
Because, the the MSB has already told me that it's a negative integer.
So, I want ' 1 1 ' to map to the magnitude 1.
' 1 0 ' to map to the magnitude 2. ' 0 1 ' to map to the magnitude 3.
' 0 0 ' to map to the magnitude 4,
And while ' 1 0 ' as an unsigned integer does represent 2.
But ' 0 1 ' is an unsigned integer, does not represent 3.
Similarly ' 1 1 ' is an unsigned integer, does not represent 1.
So, we need to come up with a more sophisticated mapping,
then just reading of this binary sequence as an unsigned integer.
Now the first observation we have is that if we look at this ' 1 1 ' over here,
which is actually coming from here, right! These are the negative integers
and here the magnitude represent by ' 1 1 '. ' 1 1 ' as an unsigned integer represents 3.
However, we wanted to represent 1 . So this 1,
what we wanted to represent, can we thought of as '4-3'.
Similarly ' 1 0 ' is an unsigned integer represents 2, and
we wanted to represent the magnitude 2. So, it can be thought of as '4-2'.
Similarly, ' 0 1 ' as an unsigned integer represents 1. We wanted to represent 3. So it can be
thought of as '4 – 1', which is 3. And, similarly ' 0 0 ' as an unsigned integer represent 0.
We wanted to represent 4, so it can be thought of as '4-0' which is 4.
So this basically tell us, that really if you want to get the magnitude of the unsigned,
if you want to get the magnitude of the negative integer from this binary representation in two's Complement,
we can just look at the bits that claims to represent magnitude, We can
find out what it represent is an unsigned integer and subtract that unsigned integer
from an appropriate power of 2. What was the appropriate of 2 here? It was 2's squared,
because this is the largest magnitude, that you can represent using three bits, in 2's complement.
Four is the largest magnitude that you can represent in 3 bits, using two's complement.
So, we want ' 4- 0 = 4 ' at this end, and that is why we are subtracting from 2's square, which is 4.
Yet, another way to think about this is to say that, you look at ' 1 1 ',
which represents the unsigned integer 3, flip all the bits, you get 0 and
then you add 1 to it, and that gives you the magnitude that you wanted to represent.
You look at ' 1 0 ', which represents the unsigned integer 2, but you wanted to represented 2,
so flip all the bits, you get the unsigned integer 1, then add 1 to it, you get 2, and so on.
' 0 1 ', which represents the unsigned integer 1, but you wanted to represent 3,
so flip all the bits, you get the unsigned integer 2, add 1 and you get 3. And so on
for ' 0 0 ' as well. ' 0 0 ', when you flip, you get ' 1 1 ', which represents unsigned integer 3,
you add 1, then you get 4. So if you look at these two ways of computing the
magnitude of the negative integers, you see that, one way of accomplishing this, basically
finding out the difference of the magnitude represented by the black sequence of bits,
from 2's squared, or from appropriate power of 2, if you have higher number of bits there,
is really to go like this. You can flip the bits, find out the decimal equivalent and then add 1 to it.
So this is what we can do, if we are asked a question, that can you find
out the magnitude of what this represents in 2's complement. So there are two ways.
In both ways, we will first look at the MSB, figure out its a negative integer,
and then what we could do is we could look at the rest of the representation, flip every bit,
find out what it represents in decimal, add 1, and then the absolute value is 9 in this case.
And, so the answer is -9. Alternatively, we could also solve the same problem, in the following way.
The MSB is 1, so it is a negative integer.
Now to get the absolute value of this, you would note the MSB, so you get decimal 7,
and then you say, I am going to subtract 7 from 2 raised to 4, in which case, I get 9.
Now, where did this 2 raised to 4 come from? This is the number of bits in the magnitude.
There are 4 bits in the magnitude, which is the total number of bits – 1. Because the total number
of bits also has 1 signed it. So this case also, the answer is -9. So, in summary,
we saw the rational behind the two's complement representation, and we saw two simple ways
of arriving at the magnitude of negative integers from two's complement representation.
Thank You.
two's complement representation of signed integers.
Here is a quick recap of some topics related to this lecture,
that we have seen earlier. We've seen how integers are represented in a computer.
And, we've seen this for both unsigned integers and signed integers.
In this lecture, we're going to look at a bit more closely,
at two’s complement representation for signed integers.
We have already seen this earlier slightly sketchily.
We are going to look at it a bit more closely today,
And, we are also going to see how the magnitude of negative integers,
represented in two's complement representation can be computed.
So now for signed integers
we've already seen that we could treat the most significant bit as the signed bit and
if the most significant bit is 1, then we could treat the integer as a negative integer,
and if the MSB is 0, we could treat it as a positive integer.
This representation is also called the Sign-magnitude representation, for obvious reasons.
And, we have seen similar examples earlier,
where, here I am trying to represent integers using 3 bits,
and I have arranged the integers along a circle. As an unsigned integer this represent 0,
this represents 1, 2, 3, 4, 5, 6, 7. So, I have represented the binary representations of these
unsigned integers along the circle in this order 0 to 7,
and now I want to interpret these sequences of 0's and 1's
as two’s complement representation of integers.
So, here are the MSB 0 representations.
Here are the MSB 1 representations, and in the signed magnitude,
the MSB just gives you the sign the rest of it gives you the Magnitude.
So, we've seen that this corresponds to +0, +1, +2, +3, and then -0, -1, - 2, -3.
We have also seen that this basically corresponds to two increasing directions
one in this way and the other in this way.
These are two different increasing directions,
and it also gives rise to these wasteful representations,
where we have two representation of '0'. Now, before we go to two's complement representation,
We would like to ask that, 'Well, How else could we represent negative integers in binary?'
So using the MSB to represent the sign is really convenient,
because we could just look at one bit and tell whether the number is positive or negative.
And so, here is our circle again, and if we say that our MSB still represents the sign,
so we know that these are +0, +1, +2, +3. Now what about these.
Here the MSB is 1, and so these must represent negative integers.
But, what negative integer should be let each of these sequences of 0's and 1's represent?
So for example, what negative number should ' 1 0 0 ' represent?
What should ' 1 1 1 ' represent? and so on. In trying to answer this question,
what we might want to think of this circle as a wrapped-around number line.
So, if you think of this circle as a wrapped around number line,
then I can see that from here to here
the numbers are increasing +0, +1, +2, +3. These are going to be negative integers.
So, can I somehow think of this circle? Can I somehow unwrap this circle into a number line,
such that along the number line I get 0, 1, 2, 3 at these positions,
and these correspond to negative integers,
and still I can think of the unwrapped circle as a usual number line.
So, in order to break up a circle into a number line,
we have to figure out where to break this circle?
Now there are two logical points to break, where the MSB is changing.
So, this is one point where I am going from 1 to 0.
And, this is the other point where I am going from 0 to 1.
Now, if I broke the circle at this point, then I would get a number line,
which starts like this 0, 1, 2, 3 and then there are four numbers, which if I assume
there must to be representing the sign should be negative numbers.
So, my number line would now look like this,
Right. So, I have broken the circle here.
So I get 0, 1, 2, 3 and then I get these numbers with the blue MSB,
and if I want to treat this as a number line and
say that well, the numbers are increasing this way. What you will see is that, here
I must have something which is greater than +3. And, so really there is no space for negative integers.
So, I want to take this circle and unwrap it as a number line,
This is not a good place to break.
if we want these four binary sequences to represent negative integers.
So what is the other logical point. The other logical point is here.
So let see what happens if we break the circle there.
So now we going to break the circle there, and that
gives raise to this number line, where we start-off with the binary sequences, with the blue MSB, MSB of 1.
and then we get the binary sequences with red MSB. MSB of 0,
and these, we already know are +0 ,+1 ,+2 ,+3.
Because, we want to treat the MSB as the signed bit,
and when the number is positive,
we just want to treat the number as it's an unsigned integer.
So now the question is that given this number line.
Clearly, we can find out the direction in which, the numbers are increasing.
That is the increasing direction. So now, what negative numbers,
what negative integers should I place here, so that I get an increasing number line,
I get consecutive integers, and I am also able to represent negative integers.
Clearly, the choice is obvious. This will be -1, -2, -3, -4, and you can see that,
this is now consistent with the increasing direction.
I have represented consecutive integers,
and all of them are increasing in this direction. So, this is what motivates the two's Complement representation.
We are going to try to represent negative integers, such that this corresponds to -4,
this corresponds to -3 , this corresponds to -2 , this corresponds to -1.
Because, this allows us to break this circle at this convenient point,
and then treat this unwrapped circle as an increasing number line.
So this is the picture that we have seen earlier.
Along the circle, I am going to put -4, -3, -2, -1. So, this gives me one completely increasing sweep,
as I go around the circle, in this direction, and of course at the end,
when I come back from +3 to -4,
There is a wrap around. In terms of our previous picture,
the number line picture, this is really going back from end to this end. Right.
'0 1 1' to '1 0 0'. +3 to -4.
And, it easy to see, that we can now represent 8 numbers, using 8 combination of 3-bits.
So there is no wastage, and we have only one representation of 0.
Now, an interesting questions that comes here is that, when the numbers were positive,
we could just read-off the numbers as if they were unsigned integers,
and put '+' sign before to get signed integer.
Now, when the numbers are negative, we have this strange thing,
that '1 0 1' which is an unsigned integer would represent 5, and if we just look at magnitude,
which is the bits in black, it would represent 1.
But, we want this to represent the signed integer '-3'.
Similarly, If you look at this number '1 1 1', as an unsigned integer it could represent '7'.
If you just look at the magnitude which are bits in black, it would represent '3'.
But, we want to this represent as '-1'. So a question to ask is that,
Can we have a mapping of the binary representation to the magnitude of the negative integers?
So, we would like to go from this ' 1 1 ' to 1, I would like to go from this ' 1 0 ' to 2,
from this ' 0 1 ' to 3, and from ' 0 0 ' to 4. So, how do we come up with this mapping?
So, this is our desired mapping. When we are using 3 bits ' 1 1 ' should map to 1.
Remember, I am just interested in the magnitude now.
Because, the the MSB has already told me that it's a negative integer.
So, I want ' 1 1 ' to map to the magnitude 1.
' 1 0 ' to map to the magnitude 2. ' 0 1 ' to map to the magnitude 3.
' 0 0 ' to map to the magnitude 4,
And while ' 1 0 ' as an unsigned integer does represent 2.
But ' 0 1 ' is an unsigned integer, does not represent 3.
Similarly ' 1 1 ' is an unsigned integer, does not represent 1.
So, we need to come up with a more sophisticated mapping,
then just reading of this binary sequence as an unsigned integer.
Now the first observation we have is that if we look at this ' 1 1 ' over here,
which is actually coming from here, right! These are the negative integers
and here the magnitude represent by ' 1 1 '. ' 1 1 ' as an unsigned integer represents 3.
However, we wanted to represent 1 . So this 1,
what we wanted to represent, can we thought of as '4-3'.
Similarly ' 1 0 ' is an unsigned integer represents 2, and
we wanted to represent the magnitude 2. So, it can be thought of as '4-2'.
Similarly, ' 0 1 ' as an unsigned integer represents 1. We wanted to represent 3. So it can be
thought of as '4 – 1', which is 3. And, similarly ' 0 0 ' as an unsigned integer represent 0.
We wanted to represent 4, so it can be thought of as '4-0' which is 4.
So this basically tell us, that really if you want to get the magnitude of the unsigned,
if you want to get the magnitude of the negative integer from this binary representation in two's Complement,
we can just look at the bits that claims to represent magnitude, We can
find out what it represent is an unsigned integer and subtract that unsigned integer
from an appropriate power of 2. What was the appropriate of 2 here? It was 2's squared,
because this is the largest magnitude, that you can represent using three bits, in 2's complement.
Four is the largest magnitude that you can represent in 3 bits, using two's complement.
So, we want ' 4- 0 = 4 ' at this end, and that is why we are subtracting from 2's square, which is 4.
Yet, another way to think about this is to say that, you look at ' 1 1 ',
which represents the unsigned integer 3, flip all the bits, you get 0 and
then you add 1 to it, and that gives you the magnitude that you wanted to represent.
You look at ' 1 0 ', which represents the unsigned integer 2, but you wanted to represented 2,
so flip all the bits, you get the unsigned integer 1, then add 1 to it, you get 2, and so on.
' 0 1 ', which represents the unsigned integer 1, but you wanted to represent 3,
so flip all the bits, you get the unsigned integer 2, add 1 and you get 3. And so on
for ' 0 0 ' as well. ' 0 0 ', when you flip, you get ' 1 1 ', which represents unsigned integer 3,
you add 1, then you get 4. So if you look at these two ways of computing the
magnitude of the negative integers, you see that, one way of accomplishing this, basically
finding out the difference of the magnitude represented by the black sequence of bits,
from 2's squared, or from appropriate power of 2, if you have higher number of bits there,
is really to go like this. You can flip the bits, find out the decimal equivalent and then add 1 to it.
So this is what we can do, if we are asked a question, that can you find
out the magnitude of what this represents in 2's complement. So there are two ways.
In both ways, we will first look at the MSB, figure out its a negative integer,
and then what we could do is we could look at the rest of the representation, flip every bit,
find out what it represents in decimal, add 1, and then the absolute value is 9 in this case.
And, so the answer is -9. Alternatively, we could also solve the same problem, in the following way.
The MSB is 1, so it is a negative integer.
Now to get the absolute value of this, you would note the MSB, so you get decimal 7,
and then you say, I am going to subtract 7 from 2 raised to 4, in which case, I get 9.
Now, where did this 2 raised to 4 come from? This is the number of bits in the magnitude.
There are 4 bits in the magnitude, which is the total number of bits – 1. Because the total number
of bits also has 1 signed it. So this case also, the answer is -9. So, in summary,
we saw the rational behind the two's complement representation, and we saw two simple ways
of arriving at the magnitude of negative integers from two's complement representation.
Thank You.
No hay comentarios.