Two’s complement and negative numbers

How are numbers represented in memory?

Like anything else stored in a computer’s memory, numbers are stored as 0 and 1. This is the infamous binary code, like in the matrix you are either a one or a zero…

So for example on a 64 bit machine a signed integer (that is an integer that can be positive or negative) is stored over 32 bits, a combination of 32 zeros and ones with the most left bit reserved for the sign. 0 for positive numbers and 1 for negative numbers.

How are positive numbers represented in memory

This is the actual representation of the positive number 1:

00000000000000000000000000000001

For simplicity sake let’s work with just 4 bits.

So this is 1 as a 4 bits number with the most left 0 as the sign bit:

0001

With 3 bits for the number and 1 for the sign you can have the following positive numbers:

Binary | Decimal
0000 ----> 0
0001 ----> 1
0010 ----> 2
0011 ----> 3
0100 ----> 4
0101 ----> 5
0110 ----> 6
0111 ----> 7

So a total of 8 positive numbers. As you can guess there are 8 negative counterparts that start with a 1, but we’ll talk about them a bit later…

Let’s take 5 to better understand how we get to that result. In binary each bit represent a power of 2 starting with power of 0 for the most right bit. Then as you move to the left you increment the value represented by a bit by the consecutive powers of 2. Therefore the second bit from the let is worth 2¹ which is 2, and the third 2² which is 4 as in the following schema:

So as you can see the 1 acts as an on switch. Column 0 (the most left) and column 2 are both switched on. Therefore you simply add the value each column represents if it’s on to get the decimal representation of the binary number. In our example 4 + 1 which is obviously 5.

But what about negative numbers?

It would be tempting to represent negative numbers this way:

1001 ----> -1

Which according to the previous rule would be -1. In other words the positive version of 1 with a 1 in front to signify the negative sign.

The problem with this approach is that it doesn’t allow for arithmetic calculations…

So let’s say that we want to add 6 and -1. We expect the result to be 5 or in its binary state, 0101. Let’s see what happen when we perform the actual calculation.

  0110
+ 1001
-------
  1111  

According to the rules we defined earlier we would get -7 which doesn’t make any sense. Therefore you need another approach.

Two’s complement

In order to solve the previous issue you need to build your negative numbers based on the desired outcome.

Let’s take the same example by trying to add 6 and -1 once again.

  0110 ---->  6
+ 1??? ----> -1
-------
  0101 ---->  5

Now let’s reverse all the bits of 1:

   0110 ---->  6
+  1110 ----> -1
-------
(1)0100 ---->  4

This approach gives you a result of 4 with an extra bit that is out of range... Close but no cigar…

You also note that if you take that extra bit and add it back in at the start of you result you do get the good result! As in:

  0100 ----> 4
+ 0001 ----> 1
-------
  0101 ---->  5

The other problem with this approach is that you get a negative value for 0 which becomes 1111. Wouldn’t it be nice to get rid of that negative zero by shifting every negative values by one. Therefore -1 becomes -0, -2 becomes -1 and so on an so forth.

In the end we have something like this:

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

Now the arithmetic works!

   0110 ---->  6
+  1111 ----> -1
-------
(1)0101 ---->  5

The extra bit can be discarded by the compiler to avoid an overflow.

In the end removing the negative zero by shifting all the negative values down allowed the arithmetic to work…