Two's Complement

Section 10.3 Two's Complement

Consider the problem of representing an integer on a computer, especially integers which can be either positive or negative (i.e. signed integers). Ideally, we want a fixed number of bits is used.

🔗

One simple method is to use the left-most bit to represent the sign of the integer, and the other bits to represent the absolute value of the integer. However, this method makes addition and subtraction more complicated, and it makes it such that the representation of the number 0 is not unique.

🔗

Instead, a common method that is used is called two's complement.

🔗

Subsection 10.3.1 Two's Complement

🔗

Overall, two's complement uses a sequence of bits (binary digits) whose length is a power of 2, say 32. Since each digit can either be 0 or 1, this allows for representation of

2^{32}

decimal integers. This is used to represent all integers between

- 2^{31}

and

2^{31} - 1,

inclusive, which (again) is a total of

2^{32}

integers. This particular configuration allows for integers up to about 4 billion. Or, the next higher would be

2^{64} .

This is called 32-bit, and 64-bit, respectively.

🔗

For simplicity, we will explore the method and concepts using 8-bit representations (i.e. with 8 bits). However, the method easily generalizes to 32-bit or 64-bit.

🔗

Definition 10.3.1.

The two's complement of an integer $a$ between $- 128$ and $127$ (inclusive) is the integer,

{\begin{cases} a & a \geq 0 \\ 2^{8} - | a | & a < 0 \end{cases}

represented in binary.

🔗

To determine the two's complement of a negative integer

a,

first convert

| a |

to binary. Then, flip each bit, i.e. change each 0 to 1 and 1 to 0. Finally, add 1.

🔗

The flipping of each bit corresponds to subtracting

{| a |}_{2}

from

(2^{8} - 1)_{2} = 11111111_{2} .

Then, the adding of 1 gives the desired result,

(2^{8} - 1)_{2} - {| a |}_{2} + 1_{2} = (2^{8} - | a |)_{2}

🔗

Subsection 10.3.2 Addition and Subtraction with Two's Complement

🔗

Consider

a + b

a - b,

using two's complements. First, notice that examining addition is sufficient, because subtraction is just addition of the negative,

a - b = a + (- b) .

🔗

First, convert

a

and

b

to their two's complement representation. Then, add the integers using binary addition, but discard any carr bit that occurs in the

2^{8}

th digit position. Finally, convert the integer back to decimal form.

🔗

If the result of the sum is outside the range, this results in an overflow error. This occurs precisely when both integers are positive but the result is negative, or when both integers are negative but the result is positive.