Sutraction without subtraction

How to subtract numbers without using subtraction

Introduction

Today you will learn how to subtract numbers without using subtraction. First, open the console and try to type the following function:

const subtract = (x, y) => x + ~y + 1;

Try using it and check that it works. This formula is very similar to the way CPUs subtract two numbers.

Negative numbers

How do CPUs represent negative numbers? There are only 0s and 1s: signs, operations, and any other data need to adapt to this limitation.

Computer systems use something called the Two’s Complement for binary numbers.

Ten’s Complement in decimal base

To understand the Two’s Complement, we’ll first take a look at some examples of the Ten’s Complement for our familiar decimal system:

• 7 is the Ten’s Complement of 3 because 7 + 3 = 10

• 8 is the Ten’s Complement of 2 because  8 + 2 = 10

• 12 is the Ten’s Complement of 88 because 12 + 88 = 100

• 813 is the Ten’s Complement of 187 because 813 + 187 = 1000

The Ten’s complement is the number we need to add to get to the next power of ten. So, for example, ten for one-digit numbers, one hundred for two-digit numbers, etc.

Two’s Complement in binary base

The Two’s Complement for binary numbers is the same idea: The number we need to add to get to the next power of two.

• 0110 is the Two’s Complement of 1010 because 0110 + 1010 = 10000

• 010 is the Two’s Complement of 110 because 010 + 110 = 1000

• 01010 is the Two’s Complement of 10110 because 01010 + 10110 = 100000

This list feels weird. Our intuition is not that good for binary :(

Negative numbers using Two’s Complement

Computer systems chips work with a fixed number of bits, commonly 64 or 32. For the sake of simplicity, let’s take a CPU that works only with four bits.

That means the maximum number it can work with is “1111” (fifteen in decimal). That means there is no space to handle negative numbers because there are no more bits to store information.

CPUs use the Two’s Complement as negative numbers. So, for example, the Two’s Complement of “0010” (two) is “1110”; therefore the CPU understands “1110” as minus two, not as fourteen—the decimal value—.

Here is the list of all the numbers that our four-bit CPU can handle:

0111 →  7
0110 →  6
0101 →  5
0100 →  4
0011 →  3
0010 →  2
0001 →  1
0000 →  0
1111 →  -1
1110 →  -2
1101 →  -3
1100 →  -4
1011 →  -5
1010 →  -6
1001 →  -7
1000 →  -8

I have to say that I found this annoying when I learned about it. Why not just keep the last bit for negative or positive and the rest of the bits the same? For example, two is 0010, and -2 could be 1010, keeping the last three bits representing the number and the first bit for the sign. Keep reading, and you will learn that they have a good reason to use the Two’s Complement.

The CPU now covers from minus eight to seven instead of zero until fifteen. Thus, this system divides the highest number it covers by two, but it also covers the negative numbers.

The first bit on the left classifies the number as positive or negative. Therefore it is called the sign bit—0 for positive numbers and 1 for negative ones.

Why do we use the Two’s Complement

We are creating a system with a limited amount of numbers—four bits in our case—. When we reach the last one, we start again. Adding one to seven (1 + 0111) is “1000” or minus eight. Like in the hours of the day, that after reaching twelve (or twenty-four), we start again at one.

In this kind of system—called Modular Arithmetic—, another way to subtract is to add a big number that wraps around the highest.

For example, in our hours’ example, subtracting four hours to 7:00 is the same as adding eight hours.

• 7:00 minus four hours is 3:00.

• 7:00 plus eight hours is 3:00.

In this example, we could call eight the Complement of four. Hence we could consider eight to be minus four. Our Two’s Complement is similar to this high number.

Subtracting with no subtraction

The Two’s Complement is the negative number, which means that if we have a number y, the Two’s Complement is -y. So we can now get rid of the subtraction substituting -y with the Two’s Complement:

x - y === x + get2sComplement(y)

Now we need to learn how to calculate the Two’s Complement.

How to calculate the Two’s Complement?

Let’s use an example. Find the Two’s Complement of 0101—five in decimal—.

1. Five in binary: 0101

2. We negate all the bits: NOT(0101) → 1010

3. We add one: 1010 + 1 → 1011

Beautiful! Take a look at the list Two’s Complement above, try calculating a few numbers, and you’ll see that I am not lying :)

To summarize, the formula is:

get2sComplement -> NOT(y) + 1

Putting it all together

We started with x - y, which we learned can be written as x + get2sComplement(y). We also learned that get2sComplement -> NOT(y) + 1. So if we combine the equations, we have:

x - y == x + (NOT(y) + 1)

In JS x + NOT(y) + 1 can be written as x + ~y + 1 the formula that we learned at the beginning. ~ is doing a NOT on the number. However, notice that ~ only works with integers and only up to 32 bits.

And this is how to subtract without subtracting.

How cool is that?