Why are integers stored in Two's Complement?

Everyday Numbers

In computer systems, everything is stored as numbers, which are themselves encoded in binary notation. Binary notation is simply base 2 as compared to our everyday base 10 number system. For example, the number 125 can be understood to mean as encoding a 5 in the ones digit, 2 in the tens digit, and 1 in the hundreds digit. The "ones" digit is just 5*10^0 (10 to the power 0, here the ^ symbol represents exponentiation), the "tens" digit is 2*10^1 and the hundreds digit is 1*10^2. Note that their sum is 1*10^2 + 2*10^1 + 5*10^0 = 125.

The same is true for any base, including base 2. Whatever our number base is, we have available digits up to 1 less than our base. In base 10, we can use the digits 0 to 9. In base 2, we can use the digits 0 to 1, or simply, 0 and 1. Therefore, the base 2 number 1101 would be found by summing: 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 13.

Representing Negatives

So that describes the representation of positive, or unsigned, integers. But what about negative integers? Normally, the leftmost bit, the most significant bit, is turned on to indicate that a signed integer is negative. However that alone is insufficient for good binary arithmetic -- making it easy to add and subtract binary numbers.

Binary Arithmetic

This is where the Two's Complement method comes in. Take our previous binary number 00001101 = 13. Here we use a full 8 bits, or a byte, to have enough space to use the left-most signed bit. To find the Two's Complement of this number, we invert all the bits (flipping or toggling all the 1's to 0's and all the 0's to 1's) and add a binary 1 from the right, carrying the digits as necessary. Inverting 00001101 yields 11110010. Now adding 1 to that from the right yields: 11110010 + 1 = 11110011, which is the correct representation of -13. The first place Two's Complement shines is when we test binary addition. 13 + (-13) should equal 0. Let's see:

 00001101     /* 13 */
+11110011     /* Two's Complement of 13, ie -13 */
---------
 00000000     /* Their binary sum, works out to 0 */

If our summation would result in a leading 1 outside the width of our bit field, it is simply discarded. As in this example:

 00000001     /* 1 */
+11111111     /* Two's Complement of 1, ie -1 */
---------
100000000     /* discard excess carried left-most bit */
 00000000     /* Their binary sum, works out to 0 */

Only One Zero

This immediate ease of binary addition and subtraction is the key advantage of Two's Complement. Any other encoding would require more exceptions when adding or subtracting a negative number in terms of accounting for the left-most signed bit. Another benefit of Two's Complement is that there is only one version of 0. In a more naive encoding, the result is that there is a "unsigned zero" 00000000 and another "signed zero" as 10000000. Which requires even more exceptions in the code to deal with. But this problem does not arise with with Two's Complement binary field, where every positive element has a Two's Complement negative inverse, and together they add to the unique zero identity element. A proper algebraic group under addition and algebraic field under multiplication.

One's Complement

It is worthwhile to make a quick comparison with One's Complement, which is the same method except we do not add 1 after we flip all the bits. One problem with this method is that it also has two forms of 0. As in 1 + (-1) would be:

 00000001     /* 1 */
+11111110     /* One's Complement of 1, ie -1 */
---------
 11111111     /* the One's Complement of 0 */
 

Thus we can see that Two's Complement improves this problem of One's Complement by making sure the additive identity element, the 0, is uniquely encoded.

No Complement?

To more thoroughly illustrate the purpose of both having a signed bit and flipping the other bits, let's now see what happens if we do not take a complement at all, ie no flipping of the bits, but we do indicate negative by using the left-most bit (or any other):

 00000001     /* 1 */

+10000001     /* signed bit on, ie -1 */

---------
 10000010     /* 2 with signed bit on, ie, -2 */

So using "No Complement" while indicating a signed bit results in 1 + (-1) = -2. A very unfortunate result. Yet we need a way to indicate the negative, so a signed bit must be used. And to make binary arithmetic work out of the box, we need to complement. And to encode a unique additive identity element, only one 0, we need Two's Complement.

Thanks for reading! ;)