Understanding Two's Complement

Understanding Two's Complement

·

3 min read

Two's complement is a mathematical operation, usually used to express signed integers. Let's start from scratch step by step to see how it implemented and why it is need.

We know that all things in computer are bits. If we want to use bits to express unsigned interger, we can just use the binary format to interpret bits into integers. For example, if we have 4 bits, then it may looks like below table.

0 0 0 0  => 0
0 0 0 1  => 1
0 0 1 0  => 2
0 0 1 1  => 3
0 1 0 0  => 4
0 1 0 1  => 5
0 1 1 0  => 6
0 1 1 1  => 7
...

But how about negative values? We can use the first bit as a sign, with 0 as positive, 1 as negative. So table may looks like below.

1 1 1 1  => -7
1 1 1 0  => -6
1 1 0 1  => -5
1 1 0 0  => -4
1 0 1 1  => -3
1 0 1 0  => -2
1 0 0 1  => -1
1 0 0 0  => -0
0 0 0 0  => 0
0 0 0 1  => 1
0 0 1 0  => 2
0 0 1 1  => 3
0 1 0 0  => 4
0 1 0 1  => 5
0 1 1 0  => 6
0 1 1 1  => 7

OK, it looks good. Let's do some math. How about -3 + 3?

 1011  <= -3
 0011  <= 3
-----
 1110  <= -6

This math give us the answer -6, which is definitely wrong.

So a simple sign bit is not enough, we need to make some improvement.

Let's try to inverse value bits for negative values. Then the table becomes below.

1 0 0 0  => -7
1 0 0 1  => -6
1 0 1 0  => -5
1 0 1 1  => -4
1 1 0 0  => -3
1 1 0 1  => -2
1 1 1 0  => -1
1 1 1 1  => -0
0 0 0 0  => 0
0 0 0 1  => 1
0 0 1 0  => 2
0 0 1 1  => 3
0 1 0 0  => 4
0 1 0 1  => 5
0 1 1 0  => 6
0 1 1 1  => 7

With this new table, let's do this math again.

 1100  <= -3
 0011  <= 3
-----
 1111  <= -0

The answer is -0, this is close.

Now let's do the last step of two's complement, add all negative values with value 1. Then the table should becomes below.

1 0 0 0  => -8
1 0 0 1  => -7
1 0 1 0  => -6
1 0 1 1  => -5
1 1 0 0  => -4
1 1 0 1  => -3
1 1 1 0  => -2
1 1 1 1  => -1
0 0 0 0  => 0
0 0 0 1  => 1
0 0 1 0  => 2
0 0 1 1  => 3
0 1 0 0  => 4
0 1 0 1  => 5
0 1 1 0  => 6
0 1 1 1  => 7

Note that adding only applys to the bits part, the value it represents is not changed. And 1111 plus 1 becomes 1000, and we use it to represent -8.

Now let's do the math again.

 1101  <= -3
 0011  <= 3
-----
10000  <= 0

Overflow bits should be discarded. Then we finally get the right answer.

That's all the process of two's complement. We can also see this process in terminal(JavaScript).

> ~3
-4

> ~3 + 1
-3