22 September 2011

Okay, Dave Collins at Twirly Bird Tips has pretty much short changed me on this topic. He has done an excellent introduction to two’s complement that frankly I can’t improve on. It’s in two parts and you can find the first one here:

http://www.youtube.com/watch?v=9W67I2zzAfo

However what I can do is reinforce some key points that Dave brought up in his video.

Calculating two’s complement

This is really easy and Dave covers it so I won’t get into any detail but for the number one, the steps are basically:

  1. Flip the bits -  001  becomes 110

  2. Add one - 110 becomes 111

And well, that’s it really. If the number is greater than three bits i.e. if you have zero 000 _becomes _111 and when you add one more you get 1000, you simply drop the carry i.e. the left most number, which brings you back to (in this case) 000.

It really is that easy :)

If you forget everything else remember this!

In any binary system, the value stored can mean ANYTHING that we agree it to mean. This is a really important concept and it’s probably the most common cause of mistakes. For example the binary number 111 is usually considered to mean 7. But it only means 7 because we have agreed that this is the case. It could instead stand for a chicken and mushroom pie as long as both agree to it in advance.

In an unsigned system where all the numbers are integers, it makes sense to simply count up and whatever value we get is what the value is. When we need negative numbers though we have a problem. You can’t have a negative number of bits just like there is no physical representation for a negative number of chicken and mushroom pies.

So if we can’t literally show negative values, we need a way to show negative values using positive numbers. A three bit system can store eight values. In an unsigned system, it would store values zero to seven (0 - 7). We want to store negative numbers but we only have the same three bits to work with. Clearly this means that some of those positive bits must now represent negative numbers.

Using two’s complement for example 111  _is -1. In an unsigned system, _111 is usually taken to be 7. So which one is right? The answer is, they are both right. It just depends what system we are using.

The short version: As long as we agree on a system and we both use that system to read and store our values, we will be able to understand each other. The value that’s actually stored is just a representation and it means whatever the chosen system says it should mean.

Two’s complement lets you subtract by adding

This is a really great feature. I won’t go into it in any depth simply because Dave has worked examples and I can’t really add anything of value to it. However the benefit is we just need an adder in order to add and subtract which makes things a lot less complicated as far as hardware and CPU design go. It’s also easy to work with and you don’t have to worry about a separate subtraction system.

Overflows are really easy to detect

You can easily detect an over flow by determining when the sign changes. If you add two positive numbers together and end up with a negative answer, then you’ve overflowed and the number you have stored is not the correct answer. This works the other way too - if you add two negative numbers and end up with a positive answer, you’ve also had an overflow. Again, Dave has worked examples for this.

Double checking you have the right complement

One thing Dave didn’t mention (or if he did my apologies because I missed it) is that there is a really easy way to double check if you’ve calculated the compliment correctly. If you take the binary representation for say 1 (001) and the representation for -1 (111) and add them together, you will get 1000. We only have a three bit system so we drop the carry bit and end up with 000.

As long as you have the right value for the negative and positive numbers, adding them together will always yield zero. For a three bit system, it’s really easy to see if you’ve made a mistake but if you’re dealing with a 32 bit or 64 bit system it might become a bit more challenging…

That’s it :)

That’s it really. Two’s complement is probably the most common way to represent signed values in computers today. It’s relatively simple to understand and easy to implement in hardware. It also lets you subtract by adding which is pretty neat.

If I’ve missed anything out, please leave a comment. If I’ve made a mistake please please please leave a comment! Thanks again to Dave for that video - he saved me a lot of typing and solidified my understanding of two’s complement. As always any mistakes here are mine and mine alone :)



blog comments powered by Disqus