Two’s Complement

For both addition and subtraction of two binary numbers, the operation is performed by an addition of two unsigned numbers. Before this addition is performed during the subtraction operation, the subtrahend is converted to two’s complement format which represents a negative number.

The one’s complement of a number is formed by inverting the bits (substituting a zero bit for each one bit and vice versa). The two’s complement is formed by adding 1 to the one’s complement. The informal statement of the rule for forming the two’s complement is to “flip the bits and add 1”.

In the representation of a binary number, by convention, the bits are ordered by descending place value from left to right. Therefore, the leftmost bit is assigned the highest place value and it is called the most significant bit or the high-order bit. Likewise, the rightmost bit is assigned the lowest place value and it is called the least significant bit or the low-order bit.

The following terms denote the positive values of unsigned binary numbers.

n	value of an arbitrary number
C₁(n)	value of the one’s complement of n
C₂(n)	value of the two’s complement of n
2^R	value of a carry out of the leftmost bit position of a register R bits in length

Addition of a number to its one’s complement yields a sum consisting of all one bits whose value is one less than the value of a carry out of the register’s leftmost bit position.

n + C₁(n) = 2^R – 1 C₁(n) = (2^R – 1) – n the value of all one 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

An alternative rule for forming the two’s complement of a number is to subtract 1 from the number and then invert the bits. This is derived from the original formula.

C₂(n) = 2^R – n = (2^R – 1) – (n – 1) = C₁(n – 1)

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

Another alternative rule for forming the two’s complement is to invert only the bits to the left of the rightmost one bit. Inverting all of the bits to form the one’s complement converts the group of bits consisting of the rightmost one bit and the following zero bits to a group consisting of a zero bit followed by all one bits. Adding 1 to the one’s complement causes a series of carries extending across the entire group, but no further, that restores the bits in the group to their original values.

To perform subtraction of a number n, the computer performs addition of C₂(n). The machine relies on the fact that a carry out of its leftmost bit position causes a register to lose the value of the carry. An addition resulting in 2^R + r leaves only the value of r inside the register.

I. Subtraction of two positive numbers a and b

a – b	=	a + C₂(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₂(b – a)

II. Addition of two negative numbers: (–a) + (–b) = –(a + b)

(–a) + (–b)	=	C₂(a) + C₂(b)
	=	(2^R – a) + (2^R – b)
	=	2^R + `[`2^R – (a + b)`]`
	=	2^R + C₂(a + b) the register contains C₂(a + b)

III. Subtraction of two negative numbers: (–a) – (–b) = b – a

(–a) – (–b)	=	C₂(a) + C₂(C₂(b))
	=	C₂(a) + b the definition of b – a

For a signed binary number, the leftmost bit is designated the sign bit, and the following bits are called the numeric bits. The number is positive when the sign bit is zero, and negative when the sign bit is one. A negative number is arranged in two’s complement format.

Note that a positive binary signed number has a value smaller than the place value of the sign bit, 2^R–1. This ensures that in the above Example II, the unsigned value in the register is C₂(a + b) because the term 2^R – (a + b) is a positive value.

The greatest positive number that a register can express is termed the maximum positive number, and the smallest negative number is termed the maximum negative number.

Here proofs are supplied for the below highlighted rules that are discussed in the series of IBM manuals entitled Principles of Operation in the sections treating Binary-Integer Representation and Signed Binary Arithmetic.

The absolute value of the maximum negative number is greater by one than that of the maximum positive number.

For a register R bits in length, the maximum positive number is:

2^R–1 – 1 = B'011...1'

The unsigned number whose absolute value is greater by one than this is:

2^R–1 – 1 + 1 = 2^R–1 = B'100...0'

The maximum negative number is the two’s complement of this unsigned number.

C₂(2^R–1) = 2^R – 2^R–1 = 2^R–1 = B'100...0' The value remains unchanged.

The value of a negative binary number may be calculated directly from its bit pattern. The sign bit is taken to represent the maximum negative number (or the negative of it’s place value). The numeric bits represent the value of a positive binary number. The two values are added together.

Value of sign bit = –2^R–1
Value of numeric bits = C₂(n) – 2^R–1 = 2^R – n – 2^R–1 = 2^R–1 – n

Calculated value of C₂(n) = –2^R–1 + 2^R–1 – n = –n

A fixed-point overflow occurs during signed binary addition or subtraction when the correct result would be a positive number greater than the maximum positive number, or a negative number smaller than the maximum negative number. It is indicated when the carry out of the sign-bit position and the carry out of the leftmost numeric bit position (into the sign-bit position) disagree.

Overflow occurs when there is 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, this condition produces a result of the opposite sign, a clear error. It is demonstrated below that in all cases the disagreement in carries is sufficient to prove that the correct result exceeds the maximum value for its sign.

In the case of numbers of opposite sign (sign bits of zero and one), an overflow can never occur because the result’s value must fall within the range of the two numbers. A carry out of the sign-bit position can be caused only by a carry out of the leftmost numeric bit position. Therefore, the carries always agree.

In the case of two positive numbers (sign bits of zero and zero), a carry out of the sign-bit position can never occur. A carry out of the leftmost numeric bit position indicates that the correct result is greater than the maximum positive number. Thus, overflow occurs when the carries disagree.

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

Value of C₂(a) numeric bits = 2^R–1 – a
Value of C₂(b) numeric bits = 2^R–1 – b
Value of correct result = –(a + b)

(2^R–1 – a) + (2^R–1 – b) = 2^R – (a + b) < 2^R–1 –(a + b) < –2^R–1

The correct result is smaller than the maximum negative number.

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 expressed as an unsigned number in the register. The sign bit is set to one, and therefore the register’s contents are interpreted as a negative signed number in two’s complement format.

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

In the case of two negative numbers, the correct result is the negative value –(a + b). The sign bit is set to zero, and therefore the register’s contents are interpreted as a positive signed number. As shown in Example II, the 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 c ≥ a, then b ≥ 2^R ; and if c ≥ b, then a ≥ 2^R.