What is 2’s Complement?

Well the short answer is that 2’s complement arithmetic is mostly modular arithmetic where half of the numbers have been labelled with negative values. Almost no additional hardware is required for the computer to represent signed integers with 2’s complement. This answer inspires 3 questions:

• What is modular arithmetic?
• How do computers use it to represent integers?
• Why take this approach?

What is modular arithmetic?

Modular arithmetic is doing maths with with only a finite number of numbers. The most common example of this is clock arithmetic (except we’ll label 12 as 0 instead). Once we get past 11 we go back to zero. This is a handy example as it is one we’re all used to. If its 10am and we have to cook something for 4 hours we know that the food will be ready at 2pm. Or if we want to know the time in 29 hours we know that it will be the same as the time in 5 hours (because 29 hours is 5 hours more than a full day).

We do not need to choose 12 or 24 as the number of numbers on the clock. Indeed, for the examples here, 10 or 16 would be a better choice. From here on, I will assume that we are using 10. The number of numbers is described as the modular base, or base for short. Like this:

Modular arithmetic has some interesting properties:

Addition If a and b have the same location on the ‘clock’ then a + c will be in the same position as b + c. e.g., 17 and 7 have the same location therefore 17 + 6 will be in the same location as 7 + 6.

Multiplication If a and b have the same location on the ‘clock’ then a * c will be in the same position as b * c. e.g., 17 and 7 have the same location therefore 17 * 6 = 102 will be in the same location as 7 * 6 = 42.

For further discussion and proofs of these properties, please see my previous post.

In base 10, this can be worked out by looking at the units value. You can do your calculation and then ignore all but the least significant digit. Anything in the 10s column or above just counts as a full rotation around the clock, so will take you back to 0 (like counting in days). These properties of addition and multiplication are not particular to base 10; they work for whichever base you choose. For example, on a 12 hour clock 2 and 14 have the same location, 2 * 2 = 4 and 2 * 14 = 28 and 28 is two full rotations of the clock plus 4.

Why take this approach?

Efficency! Computers use modular arithmetic because limiting the size of your numbers allows you to complete arithmetic operations in a set amount of time. Adding 64 bit numbers takes the same amount of time regardless of the magnitude of those numbers. The problem with large numbers is what to do if the result is too large to store. The answer is that the most significant bits simply fall off the end and are ignored. This is true in both addition and multiplication. Similar to our base 10 example, this creates a clock but with a base of 2^64 instead. So the modular arithmetic is imposed as a consequence, rather than from specific choice. It is however a very useful system as we shall see.

Where do negative numbers come from?

So far we haven’t covered negative numbers at all, given that this is a post about 2’s complement arithmetic this seems strange. Looking at our base 10 clock we can add negative numbers by allowing ourselves to go backward round the clock so that -1 is in the same position as 9. Similarly 7 and -3 will be in the same location. If we choose to relable our clock keeping values as close to zero as possible we get a clock that looks like this instead:

As mentioned previously, if two numbers have the same location on the clock, then adding or multiplying them will result in the answer being in the same location. This result is not limited to positive numbers, if this seems surprising them try a few examples:

• 9 & -1 are in the same location, so 9 * 9 shoud end in the same location as -1 * -1, 81 will be in location 1, which is the same as -1 * -1
• 9 & -1 and 7 & -3 are in the same locations, 9 * 7 = 63 is equivalent to -1 * -3 = 3.

This is fantastic as your computer already knows how to add and multiply unsigned numbers. Much of the time, all that is required to do signed arithmetic is to relabel the values.

Subtraction and Negation

Subtraction is just like addtion except you ‘negate’ the second value. Even in unsigned arithmetic, this will result in the correct output as the harware doesn’t realy care if it’s doing signed or unsigned arithmetic e.g., 3 - 2 = 3 + -2 = 1 equivalently 3 - 2 = 3 + 8 = 11 = 1. One approach would be to multiply the second value by -1. A second approach is to have a dedicated negator. To see how this works we will look at a clock of 4 bit binary values:

Here 0 (0000) and -1 (1111) have exactly opposite bit patterns. If we then count down from -1 and up from 0, the results will continue to have exactly the opposite bit patterns e.g., -2 is opposite 1. Hence, to negate any number you decrement the value and ‘not’ the bits (try it). Decrementing a value can be done by adding -1 or with a dedicated decrementer.

Comparisons and Testing Negative

Comparing two values is mostly done using subtraction. To find out if a < b you do a - b and see if the result is ‘negative’. It is very easy to test if a result is negative… half of all the values are negative. This half are the “biggest” half of all the unsigned numbers; they all start with a one. This is why on our base 10 clock with negative values, we chose to use -5 instead of 5.

This doesn’t always work! In unsigned arithmetic, if you compare a really big number and a small number, subtraction will result is a number that is still big enough to have the top bit set so you will get the wrong outcome. Similarly, with signed arithmetic if you have a very large negative number and subtract a small positive number you may cross the negative-positive boundary (the one at -5 on our initial clock) and end up with a large positive number instead.

The solution is to check the top bits of the numbers we are comparing before doing the subtraction. When both the values have the same top bit, the subtraction approach will work well. Conversely, when they have different top bits, then we already know if one is bigger than the other. If we’re doing signed arithmetic and only one of the numbers has the top bit set, it is negative and smaller than the other number. Equivalently, in unsigned arithmetic, if only one of the values has the top bit set then it is the larger of the values. This is the only difference we have seen between signed and unsigned arithmetic from the computers point of view.

Finally a Bit of Fun

A common question that comes up is what happens if you negate the largest negative number. Looking back at our original clock which contained negative numbers, -5 is our biggest negative number. If we negate -5 we get 5, 5 is in the same position as -5 so as a signed result it is -5. The result is that negating the largest negative number results in still having the largest negative number.