Two’s Complement

The computer stores a negative binary number in two’s complement format.  This permits the machine to accomplish subtraction by performing an addition operation.  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.

Definition of binary values 

n     = value of an arbitrary bit configuration in a register
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 + C₁(n) + 1 = 2^R
C₁(n) = (2^R - 1) - n    the value of all 1 bits minus n

By definition:

C₂(n) = C₁(n) + 1 = 2^R - n

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

C₂(C₂(n)) = 2^R - (2^R - n) = n

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

C₂(n) = C₁(n) + 1 = (2^R - 1) - n + 1 = (2^R - 1) - (n - 1) = C₁(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.

The computer performs subtraction by adding a number in two’s complement format.  As shown below, the machine relies on the fact that when addition results in a carry out of the high-order bit, the register loses the value of the carry.

An addition resulting in 2^R + n leaves only the bits of n 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, this equals a positive value plus a high-order carry
      = 2R - (b - a)  for a < b, this equals 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(b)
            = C2(a) + C2(C2(b))
            = C2(a) + b  the expression for b - a in the first line of example I

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 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 the two’s complement of the next larger “positive” number B'100...0' which itself may not be expressed as such in a register of the same size.  Therefore, the absolute value of the smallest negative number is greater by one than that of the largest positive number.

C₂(B'100...0') = B'100...0' The bit pattern remains unchanged.

The value of a negative binary number may be reckoned directly from the bit pattern by taking the largest negative number for the value of the sign-bit, and performing the algebraic addition to this value of 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 range of numbers 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.
 

(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 2^R.  In the case of two positive numbers, the correct result is the positive value a + b represented by all bits including the sign-bit.  The register contains a negative number, C₂(n) such that:

C₂(n) = 2^R - n = a + b,  -n = a + b - 2^R

The error is quickly recognized by noting that under the direct method of reckoning the value of a negative number, the sign-bit is assigned the value -2^R-1 rather than 2^R-1.

In the case of two negative numbers, the correct result is the value -(a + b).  As shown above, the register contains a positive number equal to 2^R - (a + b).

A program may detect overflow upon adding two unsigned numbers a and b, by testing for the result c contained in the register being smaller than either a or b:

a + b = 2^R + c, c = a + (b - 2^R) = b + (a - 2^R)