two’s complement

In the last tutorial, we saw how modular arithmetic can turn a subtraction problem into addition.

Instead of calculating A - B, we can calculate A + C, where C is the complement of B.

finding the complement

Let’s go back to a 12-hour clock. Suppose the hour hand is currently at 12. If we want to set our clock to another time, we can either move it forwards (addition) or backwards (subtraction). Let’s look at how much we have to move it in each direction to get to any given time:

target	add	subtract
1	1	11
2	2	10
3	3	9
…
10	10	2
11	11	1
12	0	0

Notice how the add and subtract column always add up to 12, except the last row? Remember that in modular arithmetic, when we hit the modulus (12, here), we wrap back to 0. So actually the two columns always add up to 0.

This shows us how to find the complement — it’s the number that, when added to B, gets you to 12 (0).

So if we want to move our clock forward by 7 hours, we know the equivalent is moving it backwards by 12 - 7 = 5 hours.

binary

Let’s try this in a base-4 binary system, i.e. a number system that ranges from 0000 to 1111. The modulus is 10000 (16), so whenever we reach this value, we have to wrap back to 0000.

We’ll try 1100 - 0011 (11 - 3):

• Find the complement of 0011, which is 10000 - 0011 = 1101.
• Add this to the first number: 1100 + 1101 = 11001
• This is larger than the maximum value, so wrap it around: 11001 - 10000 = 1001 (8)

It works!

Steps 2 and 3 look easy to do in roons. Step 2 is just adding, for which we’ve already built an adder. Step 3 is just subtracting 10000, which just means removing the extra 1 at the start of the number (i.e. ignoring the carry).

But what about step 1? Finding the complement requires us to subtract two numbers. But… subtracting two numbers is what we’re trying to do in the first place, so we don’t seem to have made any progress.

modified complement

What if there were a simpler way to find the complement?

In our example above, we calculated the complement using modulus - B = complement:

• 10000 - 0011 = 1101

Looking at B and its complement, there’s no obvious relationship between those binary strings.

But what if instead of subtracting from the modulus, we subtracted from the maximum value (1 less than the modulus)?

• 1111 - 0011 = 1100

The maximum value is full of 1s. This means in every column, if B has a 1, then its complement must have a 0; and vice versa. This means that the complement is just the inverse of B — i.e. NOT(B)!

This modified complement is 1 less than our previous definition, so we need to remember to add 1 on the end. But now we have a complete and easy-to-implement formula for A - B:

• Perform NOT(B) to find the complement C
• Add A to C
• Add 1 to the result
• Discard any leftover carry, wrapping the result back into our range

implementation

next steps

Now we have an adder and a subtractor, we’re going to give our calculator the ability to switch between them.

continue