The complement to positive numbers.
Up until now things have been reasonably straight forward. Now it starts to get interesting. There are a few ways to represent negative numbers in binary. In normal decimal numbers we may simply place a negative sign ( - ) in front of the number to indicate that it is negative. In binray we don't have this luxury as we are limited to only 1's and 0's.
We'll first investigate two early implementations of representing negative numbers, along with their shortcomings, before going into detail with 2's Complement which is the method used most commonly.
Sign magnitude (sometimes also referred to as sign modulus) is the easiest of the methods we may use. It is not used very often though as it is also the least practical (which you'll soon see). Understanding sign magnitude will help you better understand and appreciate the other methods however so I would recommend you don't skip this section.
With sign magnitude we designate one of the bits (usually the far left, also known as the most significant bit) to indicate whether a number is positive or negative. Usually a '0' indicates the number is positive and a '1' indicates the number is negative. Using this method we get the following:
The above example illustrates an important point when dealing with negative numbers in binary. Because we have to designate a specific bit to be the sign indicator, we have to specify how many bits the numbers will be represented using, and pad out accordingly. In the example above we have numbers being represented using 8 bits. You could just as easily have used 16, 32, 64 bits etc.
Representing negative numbers in binary has some interesting side effects.
The largest number we may represent (With a given number of bits is effectively halved. This is because there are still the same number of combinations of 1's and 0's but now half of them are given to representing negative numbers. In fact, with sign magnitude we actually have just under half because zero may be represented as either 1000000 or 00000000. With unsigned (or no negative numbers) with 8 bits we have:
Whereas with sign magnitude we have:
We mentioned above that the left most bit is usually the one designated to be the one that indicates the sign of the number and that because of this we need to specify how many bits will be used and that every number must be padded out to that number of bits. One might ask why that has to be the case. For instance, why not:
Use only the required number of bits and make the last bit only the sign bit. eg:
Or put the sign bit as the right most bit. eg:
There is actually no reason we couldn't do this however it has 2 undesirable effects. For humans reading it it becomes much easier to make mistakes. For computers having to interpret it the processing required increases. (This may seem trivial due to how powerful computers are today but a large amount of that power comes from designing them to be very efficient.)
And finally, what about arithmetic? Unfortunately with this method of representing positive and negative numbers it is not practical to perform arithmetic operations on them. This is why in the real world sign magnitude is very rarely used. It is important to understand sign magnitude (and its shortfalls) however to fully appreciate why 2's Complement (explained further below) is the preferred method.
1's Complement is the next step on from sign magnitude. Similar to sign magnitude the most siginificant bit indicates the sign of the number. For negative numbers, however, we invert the bits from what they would normally be. Let's look at an example (again with 8 bits):
For sign magnitude:
With 1's Complement we have:
1's complement still results in 2 values that represent 0, 00000000 ( 0 ) and 11111111 ( -0 ) but it has an advantage in that now we may do basic arithmetic in a very similar fashion to that for unsigned (positive only) binary numbers. (See our page on Binary arithmetic if you need a refresher.)
2's Complement can seem a little daunting at first but once you understand the mechanism it's fairly straight forward.
What we do is state that the left most bit is actually the negative of the value which it would normally represent. We still represent the same number of values but we shift down the number line a bit. Let's say we are working with 4 bit numbers.
Similar to the previous methods, we need to set the number of bits we are going to use up front. If our number turns out to not need that number of bits then we need to pad out with 0's.
With normal unsigned binary we may represent 16 values (0 through to 15). The 4 bits (from left to right) represent 8, 4, 2 and 1.
Making the left most bit represent -8 instead of 8 we shift 8 places down the numberline and get the following range of values (7 - -8). The 4 bits now represent -8, 4, 2 and 1.
Let's look at a simple example. In the demonstration below you may put in various 4 bit or 8 bit signed binary numbers and see how they translate into decimal values.
Running Total in Decimal :
Converting from binary 2's Complement to decimal is very similar to converting normal binary (as we saw in the demonstration above). The only change is that we have to remember to minus the value of the left most bit.
Converting from decimal to 2's Complement involves a few more steps but it's not too dificult.
If the number is positive then we may convert the same way we would for unsigned binary. We must, however, pad out with 0's to the required number of bits. eg. if we are working with 8 bits and we need to represent 6 then:
If the number is negative then we first convert as if it was a positive number (remembering to pad with 0's), then we invert the bits (ie. switch all the 0's to 1's and vice versa) and finally add 1. Let's look at an example (with 8 bits):
If you just want to memorise the steps that's cool but many of you probably want to understand how this conversion to 2's Complement works.
Steps 1, 2 and 3 are pretty straight forward. Let's look in more detail at steps 4 and 5.
In step 4 what we do is a bit interesting. If we ignore the left most bit, by inverting the other digits we have created a positive number which may be added to our original number to form the maximum possible value with that many bits. So for example if we have:
If we then said 5 minus 7 we would get -2 which is our intended value. We will however always be minusing a number 1 larger than the maximum number (in binary, the next digit to the left will always represent 1 more than the maximum value of all the previous bits).
Remember that the left most bit is a negative of its normal value so here we would have a 4th bit which is normally 8 but is now -8 (negative 1 larger than the maximum, 7, of the first 3 bits). By inverting the bits we set this to 1 which means it would become 5 minus 8 which is -3. Then we add 1 to adjust for this bringing it back to -2.
With vanilla (or unsigned) binary this is not a problem, if we need a larger number we may simply add more bits accordingly. With signed binary however, we need to be weary that the number of bits in use is specified up front and we need to stick to that. If we need to represent a larger value then we need to increase the number of bits used overall, eg, move from 8 bits to 16 bits remembering that all the numbers we are working with will need to be adjusted, or just accept that it cannot be done.
Let's have a look at how we may perform addition and subtraction using 2's complement numbers. Essentially, we do exactly the same as we would for normal unsigned binary numbers. When we get to the final step there is a slight variation however.
There are a few scenarios we need to look out for:
It is only possible to get an overflow if the two numbers to be added together are of the same sign (ie, both positive or both negative).
By overflow we mean that the result was a number larger, or smaller, than what is capable of being represented using the given number of bits.
In the simulator below we are using 8 bit 2's complement numbers. Remember the largest number we may represent is 127 and the smallest number is -128 when considering how we handle the left most bit.
Firstly, lets look at overflows. In 2's complement numbers we can tell the sign of a number by looking at the left most bit. If it is a 0 then the number is positive and if it is a 1 then the number is negative. If we add two positive numbers then we expect the result to be positive. If our result has a 1 as the left most bit then our result is a negative number (which may not be so) and so an overflow has occurred.
Similarly, if we are adding two negative numbers then the result must also be negative. If our result has the left most bit being a 0 then the result is positive (which may not be so) and as such an overflow has occurred. Note that for this to occur there must be a discarded carry as the last operation and this is a clue that this has occurred.
If we are adding two negative numbers and there is a carry for the left most bit, this does not automatically mean there is an overflow. If the left most bit after discarding the carry is a 1 then the result is valid. (we discard the carry)
To understand how in some circumstances we may discard the carry yet still end up with a valid result we need to look at how our numberline behaves. With normal numbers, every time we add 1 to our number, we move 1 space along on our number line. With 2's complement numbers this same behaviour occurs however when we hit our maximum point for the number of bits we have we wrap around to the other end of the numberline.
With 8 bits if we have the following number:
This represents 127 which is the largest number on our 2's complement number line (for 8 bits).
If we add 1 to this number (and forget that it is a 2's complement number for a second) we end up with:
Which with normal unsigned binary numbers would represent 128 (1 space along from 127 on the number line) but in 2's complement this represents -128, which is the opposite end of the number line. Imagine we have curved the number line into a circle and joined the two ends.
After this jump, the normal behaviour of adding 1 shifting one space along on the number line continues. eg:
Represents -127 which is one space along from -128.
Discarding the final carry allows us to accommodate this jump on the numberline.
So the best way to learn this stuff is to practice it and now we'll get you to do just that.
Assume 8 bit binary numbers for the below activities.