Signed binary numbers: Two's complement

[qingquan-li]

1. Two's complement

Unsigned numbers involve only non-negative numbers, like 0 and 3. Signed numbers involve both positive and negative numbers, like 3 and -3.

In binary, a signed-magnitude representation uses the left bit for the sign: 0 means positive, 1 means negative. Ex: For 4-bit numbers, 0011 is 3, and 1011 is -3. Signed-magnitude representation is rarely used, because calculations involving negative numbers, such as 5 - 3, would require special circuits beyond an adder.

A more clever negative number representation exists that can use an adder for both positive and negative numbers. A complement of an N-digit number is another number that yields a sum of 100...00 (with N 0's), and can be used to represent the negative of that number.

Base 10:

  5
- 3
----
  2

Replace by:

  5
+ 7
----
 12  ignore cary

7 + 3 = 10; 7 is the complement of 3. Thus 5 + 7 is 10 too much, so the carry can be ignored.

Base 2:

  0101 (5)
- 0011 (3)
------------
  0010 (2)

Replace by:

  0101 (5)
+ 1101 (-3)
------------
 10010 (2)  ignore cary

Complement: invert bits, add 1

0011 (3) has complement:  (0011)' + 1
                           1100   + 1
               So -3 is:   1101

The above is called the two's complement representation, which inverts every bit and adds 1.

Example:

1. In base ten, the complement of 33 (two digits) is: 67
2. In base two, the complement of 0010 (four bits) is: 1101 + 1 = 1110
3. What is -2 in four-bit two's complement representation: 2₁₀ = 0010₂ , -2₁₀ = 1101₂ +1₂ = 1110₂
4. Assuming two's complement representation, what base ten number does 1001 represent? Left bit is 1, so negative. Complement to find positive. 0110 + 1 = 0111. Magnitude is 7. Negate to yield -7. Method2: 1001 - 1 = 1000, invert bits to 01111, 01111₂ = 7₁₀, then -7.

---

2. Subtracting by adding

Two's complement representation has the benefit of allowing an adder to be used even when dealing with negative numbers.z Ex: 5 + -3 is just 0101(5) + 1101(-3) = 10010, or 0010(2) after ignoring the carry. No extensive special circuitry for negative numbers is needed.

Example:

1. 6 + 2 is 0110 + ? 0010 (2 is 0010 in binary. The leftmost 0 means positive.)
2. 6 + -2 is 0110 + ? 1101+1=1110 (2 is 0010. The negative is the complement, so 1101 + 1 or 1110.)

---

3. Overflow

The largest positive four-bit two's complement number is 0111, or 7. The smallest negative is 1000, or -8 (0111 + 1 = 1000, so magnitude is 8). Adding two positives, or adding two negatives, may yield a value that can't be represented in the given number of bits, a situation known as overflow. Ex: 0101 (5) + 0011 (3) incorrectly yields 1000, which is -8 in two's complement.

Adding two positives may overflow:

0010 + 0011 = 0101  (ok)
  2  +  3   =  5

0111 + 0001 = 1000  (overflow)
  7  +  1  !=  -8

(The leftmost 0 means positive, so 0111₂ = 7₁₀ , 0001₂ = 1₁₀ . 1000 is -8 in four-bit two's complement representation)

Adding two negatives may overflow:

1111 + 1111 = (1)1110  (ok)
 -1  +  -1  =     -2

(1110 is -2 in four-bit two's complement representation)

1000 + 1111 = (1)0111  (overflow)
 -8  +  -1 !=     7

(The leftmost 0 means positive, so 0111₂ = 7₁₀ )

Adding positive and negative cannot overflow:

1000 + 0111 = 1111  (ok)
 -8  +  7   =  -1

0010 + 1000 = 1010  (ok)
  2  +  -8  =  -6

As seen above, overflow occurs if the numbers being added have the same sign bit but the sum's sign bit differs. In other words, overflow occurs if two positives sum to a negative (clearly wrong), or two negatives sum to a positive (clearly wrong).

Adding a positive number and negative number (or vice-versa) cannot result in overflow. The sum always has a smaller magnitude than one or both of the numbers, so clearly can fit in the same number of bits. Ex: 7 + -2 = 5, and 5's magnitude is smaller than 7.