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
C1(n) = value of the one’s complement of n
C2(n) = value of the two’s complement of n
2R    = value of a carry out of the high-order bit of a register R bits 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 + C1(n) + 1 = 2R C1(n) = (2R - 1) - n    the value of all 1 bits minus n

By definition:

C2(n) = C1(n) + 1 = 2R - n

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

C2(C2(n)) = 2R - (2R - 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:

C2(n) = C1(n) + 1 = (2R - 1) - n + 1 = (2R - 1) - (n - 1) = C1(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 C2(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 2R + r leaves only the value of r remaining inside the register.

I. Subtracting two positive numbers a and b:

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

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

(-a) + (-b) = C2(a) + C2(b) = (2R - a) + (2R - b) = 2R + [2R - (a + b)] = 2R + C2(a + b) the high-order carry is lost

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

(-a) - (-b) = C2(a) + C2(C2(b)) = C2(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.

C2(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 of B'100...0' = 2R-1
Value taken for sign-bit = -2R-1
Value of numeric bits = C2(n) - 2R-1 = 2R - n - 2R-1 = 2R-1(2 - 1) - n = 2R-1 - n

Reckoned value of C2(n) = -2R-1 + 2R-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  = 2R - a,   Value of numeric bits = 2R-1 - a
Value of second negative number  = 2R - b,   Value of numeric bits = 2R-1 - b

(2R-1 - a) + (2R-1 - b) = 2R - (a + b) < 2R-1 -(a + b) < -2R-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 2R.

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:

C2(n) = 2R - n = a + b,  -n = a + b - 2R

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 2R - (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 = 2R + c, then if c ≥ a, then b ≥ 2R, and if c ≥ b, then a ≥ 2R.


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