Two’s Complement

The computer stores a negative binary number in two’s complement format. This permits the machine to treat a negative number as an unsigned number with a positive value. The addition or subtraction of two registers is performed as the addition of two unsigned numbers.

The rule for forming the two’s complement of a number, is to “flip the bits and add 1”. This means first, to invert the bits (substitute a 0-bit for each 1-bit and vice versa), forming the one’s complement, and then, to add 1 to this result.

The following terms define positive values of unsigned bit configurations.

n= value of an arbitrary number_{ }C= value of the one’s complement of_{1}(n)nC= value of the two’s complement of_{2}(n)n2= value of a carry out of the high-order bit of a register^{R}Rbits in length

A number plus its one’s complement equals a register containing all 1 bits. Adding 1 to this result yields all zero bits inside the register and a carry out of the high-order bit.

n + C_{1}(n) + 1 = 2^{R}
C_{1}(n) = (2^{R} - 1) - n the value of all 1 bits minus n

By definition:

C_{2}(n) = C_{1}(n) + 1 = 2^{R} - n

Note that, as expected, two’s complement negates itself:

C_{2}(C_{2}(n)) = 2^{R} - (2^{R} - n) = n

Substituting the definition of the one’s complement into the definition of the two’s complement leads to an alternative rule for forming the two’s complement:

C_{2}(n) = C_{1}(n) + 1 = (2^{R} - 1) - n + 1 = (2^{R} - 1) - (n - 1) = C_{1}(n - 1)

The alternative rule is to “subtract 1 and then, flip the bits”. This comes in handy
when `n`, the number to complement, is given as a decimal figure.

To perform subtraction of a number `n`, the computer performs addition of
`C _{2}(n)`. The machine relies on the fact that a carry out of its
high-order bit causes a register to lose the value of the carry. An addition resulting in

**I. ** Subtracting two positive numbers `a` and `b`:

a - b = a + C_{2}(b)
= a + (2^{R} - b)
= 2^{R} + (a - b) for a > b, the value remaining in the register is a - b
= 2^{R} - (b - a) for a < b, the register contains C_{2}(b - a)

**II. ** Adding two negative numbers:` (-a) + (-b) = -(a + b)`

(-a) + (-b) = C_{2}(a) + C_{2}(b)
= (2^{R} - a) + (2^{R} - b)
= 2^{R} + [2^{R} - (a + b)]
= 2^{R} + C_{2}(a + b) the high-order carry is lost

**III. ** Subtracting two negative numbers:` (-a) - (-b) = b - a`

(-a) - (-b) = C_{2}(a) + C_{2}(C_{2}(b))
= C_{2}(a) + b the definition of b - a

The above notation may be used to prove some of the assertions made in the IBM Principles of Operation manual in the sections treating Binary-Integer Representation and Signed Binary Arithmetic.

In a signed binary number, bit 0, the high-order bit, is denoted the sign-bit, and the lower-order
bits are denoted the numeric bits. The number is deemed positive if the sign-bit contains
`B'0'`, and negative if it contains `B'1'`. The largest positive number
that a register may contain is `B'011...1'`. The largest negative number that a
register may contain is `B'100...0'` which is the two’s complement of the unsigned
number that is greater by one than the largest positive number. Therefore, the absolute value
of the smallest negative number is greater by one than that of the largest positive number.

C_{2}(B'100...0') = B'100...0' The bit pattern remains unchanged.

The value of a negative binary number may be reckoned directly from its bit pattern by the algebraic
addition of: the negative place value of the sign bit, which is the largest negative number, and the
positive value held in the numeric bits.

Value ofB'100...0' = 2Value taken for sign-bit^{R-1}= -2Value of numeric bits^{R-1}= CReckoned value of_{2}(n) - 2^{R-1}= 2^{R}- n - 2^{R-1}= 2^{R-1}(2 - 1) - n = 2^{R-1}- nC_{2}(n) = -2^{R-1}+ 2^{R-1}- n = -n

A fixed-point overflow occurs during signed binary addition or subtraction when the result
exceeds in absolute value the largest number of the same sign that the register can
hold. It is detected when the carry out of the highest-order numeric bit position
(into the sign-bit position) and the carry out of the sign-bit position disagree (do not
match). Therefore, it occurs for either a carry out of the sign-bit position with
no carry into it, or a carry into the sign-bit position with no carry out of it.
For addition of numbers of the same sign, these indicators signal a change in the sign of
the result, a clear error. It may be demonstrated that in all cases these
indicators are sufficient to prove that the magnitude of the result is too large to
represent in the correct sign by the register’s bits.

In the case of numbers of opposite sign (sign-bits of 0 and 1), an overflow can never occur because the result will have an absolute value smaller than the larger of the absolute values of the two numbers. A carry out of the sign-bit position can be triggered only by a carry out of the high-order numeric bit. Therefore, the carries always agree.

In the case of two positive numbers (sign-bits of 0 and 0), a carry out of the sign-bit position can never occur. A carry out of the high-order numeric bit indicates a result that is too large to be held in the register’s numeric bits. Thus, overflow occurs when the carries disagree.

In the case of two negative numbers (sign-bits of 1 and 1), a carry out of the sign-bit
position must always occur. The lack of a carry out of the high-order numeric bit
indicates that the sum of the positive numbers represented by the pair of numeric bits is
smaller than the positive place-value of the sign-bit.

Value of first negative number^{ } |
= 2^{R} - a, |
Value of numeric bits = 2^{R-1} - a |

Value of second negative number^{ } |
= 2^{R} - b, |
Value of numeric bits = 2^{R-1} - b |

(2^{R-1} - a) + (2^{R-1} - b) = 2^{R} - (a + b) < 2^{R-1}
-(a + b) < -2^{R-1}

The result is a negative number that is smaller than the smallest negative number that the register can hold.

When fixed-point overflow has occurred, the register contains a number that differs from
the correct result by `2 ^{R}`.

In the case of two positive numbers, the correct result is the positive value
`a + b` of the unsigned number composed of the sign and
numeric bits. The negative number that the register’s bits represent is such that:

C_{2}(n) = 2^{R} - n = a + b, -n = a + b - 2^{R}

In the case of two negative numbers, the correct result is the value
`-(a + b)`. As shown in example **II**, the positive
number contained in the register is `2 ^{R} - (a + b)`.

A program may detect overflow upon adding two unsigned numbers `a` and `b`,
even without access to the overflow indicator of assembly language. When overflow occurs,
the unsigned sum `c` contained in the register must be smaller than both `a`
and `b`.

When `a + b = 2 ^{R} + c`, then if

Copyright © 2003 The Stevens Computing Services Company, Inc. All rights reserved.