Two’s complement is a way of representing signed (positive and negative) integers using bits.
The left most bit is reserved for dictating the sign of the number, 0 being positive, 1 being negative.
The magnitude of the integer is a bit weirder.
0001 is two’s complement binary for the decimal 1
1111 is two’s complement binary for the decimal -1
How in the name of all that is good and sensible did we get from 0001 to 1111 you might ask?
Repeat after me:
‘Flip the bits and add one’
0001 with all its bits flipped around is 1110, then we add 0001 to it and we get 1111.
Why on earth would you do something so wilfully perverse as this?
Because:
- A number system with two zeros is a pain in the arse.
- We should really simplify the lives of those long suffering hardware engineers, who have to take these representations of numbers, and make the computers do maths with them.
Two’s complement solves both of these problems.
To understand why, let’s try and reinvent signed 4 bit integers.
SIGN AND MAGNITUDE
Our first attempt will be as follows:
The left most bit is used to tell us the sign (1 for negative, 0 for positive), and the remaining three bits are used to represent the magnitude of the integer.
Looks simple enough. 1 is 0001, -1 is 1001.
Let’s kick our new system in the balls a bit.
What does 0000 represent? Easy, zero.
What about 1000? Easy, negative zero.
AHHHHhhhhhhh…. that’s a problem. I bet those hardware people aren’t going to like that. They’re always complaining about stuff like this.
I think we are wasting a slot in our binary integer, as we’ve got a redundant representation of zero, and our hardware will have to somehow account for this positive and negative zero when implementing any maths functionality. Sigh. OK.
After checking, the hardware engineers inform us that yes, this is a pain and no, they won’t have it (fussy fussy hardware engineers).
Also, it turns out that this representation is somewhat fiddly to do subtraction with.
0010 + 0001 in our naive signed binary is 2 + 1 in decimal. Which is 3 in decimal, or 0011 in binary.
0010 + 1001 in our naive signed binary is 2 - 1 in decimal. Which is 1 in decimal, and should be 0001 in binary.
However, if we add our binary representations in the simplest way we get 1001, or -1. Balls.
I assume there are ways around this, but those damned hardware people won’t do it because reasons. Grrr.
So to recap, ‘sign and magnitude system’; two representations of zero; painful to do basic maths with.
Fine we’ll throw that out.
ONE’S COMPLEMENT
Okieeee so what if we flip all the bits when we turn something negative? So 1 is 0001, -1 is 1000.
Now we can try our previous subtraction problem and just add them in the dumbest way possible and we’ll get the right answer I think? Let’s try it:
2-1 is represented as 0010 + 1110, which gives us 0000 with a one carried over.
Which is… still not right.
‘You should take the carry and stick it on the end’
What’s that Gwyneth?
‘Take. The carry. Stick it on the end’
Fine. At this point what do I have to lose.
0000 with the carry stuck on the end is 0001. Which is correct! Well done Gwyneth.
Still. I bet they won’t have that double zero stuff. Probably they’re going to kick up a fuss about this moving carries around as well.
TWO’S COMPLEMENT
Tabatha, what are you guys are chanting in the corner there? By the candles and the… wait is that blood?
‘Flip the bits and and one’
‘Flip the bits and and one’
‘Flip the bits and and one’
‘Flip the bits and and one’
‘Flip the bits and and one’
Not totally happy with this blood situation, but that’s not a bad idea Tabatha!
Let’s give it a go:
2 - 1 = 1
In two’s complement:
0010 + 1111 = 0001 with a one carried
The chanting has changed…
‘Discard the carry’
‘Discard the carry’
‘Discard the carry’
‘Discard the carry’
‘Discard the carry’
You know what I think you’re right, we don’t need it. We’ve got the right answer. Finally 2 - 1 = 1 without any messy carries!
Also, I think I’ve just spotted something even neater. This gets rid of our duplicate zero right?
Two’s complement of 0000:
flip the bits:
1111
add one:
0000 with a carry of 1
discard the carry:
0000
The circle is complete.
YES!!! How do you like that hardware people!?!