Two's complement

Two's complement is the most common method of representing signed integers on computers, and more generally, fixed point binary values. As with the ones' complement and sign-magnitude systems, two's complement uses the most significant bit as the sign to indicate positive or negative numbers, and nonnegative numbers are given their unsigned representation ; however, in two's complement, negative numbers are represented by taking the bit complement of their magnitude and then adding one. The number of bits in the representation may be increased by padding all additional high bits of negative or positive numbers with 1's or 0's, respectively, or decreased by removing additional leading 1's or 0's.
Unlike the ones' complement scheme, the two's complement scheme has only one representation for zero, with room for one extra negative number. Furthermore, the same arithmetic implementations can be used on signed as well as unsigned integers
and differ only in the integer overflow situations, since the sum of representations of a positive number and its negative is 0.

Procedure

The following is the procedure for obtaining the two's complement representation of a given negative number in binary digits:

Step 1: starting with the absolute binary representation of the number, with the leading bit being a sign bit;
Step 2: inverting all bits – changing every 0 to 1, and every 1 to 0;
Step 3: adding 1 to the entire inverted number, ignoring any overflow. Accounting for overflow will produce the wrong value for the result.

For example, to calculate the decimal number −6 in binary from the number 6:

Step 1: +6 in decimal is 0110 in binary; the leftmost significant bit is the sign.
Step 2: flip all bits in 0110, giving 1001.
Step 3: add the place value 1 to the flipped number 1001, giving 1010.

To verify that 1010 indeed has a value of −6, add the place values together, but subtract the sign value from the final calculation. Because the most significant value is the sign value, it must be subtracted to produce the correct result: 1010 = − + + + = 1×−8 + 0 + 1×2 + 0 = −6.

Bits:	1	0	1	0
Decimal bit value:	−8	4	2	1
Binary calculation:	−
Decimal calculation:	−	0	1×2	0

Note that steps 2 and 3 together are a valid method to compute the additive inverse of any integer where both input and output are in two's complement format. An alternative to compute is to use subtraction. See below for subtraction of integers in two's complement format.

Theory

Two's complement is an example of a radix complement. The 'two' in the name refers to the number - "two to the power of N", which is the value in respect to which the complement is calculated in an -bit system. As such, the precise definition of the two's complement of an -bit number is the complement of that number with respect to.
The defining property of being a complement to a number with respect to is simply that the summation of this number with the original produce. For example, using binary with numbers up to three bits, a two's complement for the number 3 is 5, because summed to the original it gives. Where this correspondence is employed for representing negative numbers, it effectively means, using an analogy with decimal digits and a number-space only allowing eight non-negative numbers 0 through 7, dividing the number-space into two sets: the first four of the numbers 0 1 2 3 remain the same, while the remaining four encode negative numbers, maintaining their growing order, so making 4 encode −4, 5 encode −3, 6 encode −2 and 7 encode −1. A binary representation has an additional utility however, because the most significant bit also indicates the group : it is 0 for the first group of non-negatives, and 1 for the second group of negatives. The tables at right illustrate this property.

Bits	Unsigned value	Signed value
000	0	0
001	1	1
010	2	2
011	3	3
100	4	−4
101	5	−3
110	6	−2
111	7	−1

Calculation of the binary two's complement of a positive number essentially means subtracting the number from the. But as can be seen for the three-bit example and the four-bit , the number will not itself be representable in a system limited to bits, as it is just outside the bits space. Because of this, systems with maximally -bits must break the subtraction into two operations: first subtract from the maximum number in the -bit system, that is and then adding the one. Coincidentally, that intermediate number before adding the one is also used in computer science as another method of signed number representation and is called a ones' complement.
Compared to other systems for representing signed numbers, the two's complement has the advantage that the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers. This property makes the system simpler to implement, especially for higher-precision arithmetic. Additionally, unlike ones' complement systems, two's complement has no representation for negative zero, and thus does not suffer from its associated difficulties. Otherwise, both schemes have the desired property that the sign of integers can be reversed by taking the complement of its binary representation, but two's complement has an exception – the lowest negative, as can be seen in the tables.

History

The method of complements had long been used to perform subtraction in decimal adding machines and mechanical calculators. John von Neumann suggested use of two's complement binary representation in his 1945 First Draft of a Report on the EDVAC proposal for an electronic stored-program digital computer. The 1949 EDSAC, which was inspired by the First Draft, used two's complement representation of negative binary integers.
Many early computers, including the CDC 6600, the LINC, the PDP-1, and the UNIVAC 1107, use ones' complement notation; the descendants of the UNIVAC 1107, the UNIVAC 1100/2200 series, continued to do so. The IBM 700/7000 series scientific machines use sign/magnitude notation, except for the index registers which are two's complement. Early commercial computers storing negative values in two's complement form include the English Electric DEUCE and the Digital Equipment Corporation PDP-5 and PDP-6. The System/360, introduced in 1964 by IBM, then the dominant player in the computer industry, made two's complement the most widely used binary representation in the computer industry. The first minicomputer, the PDP-8 introduced in 1965, uses two's complement arithmetic, as do the 1969 Data General Nova, the 1970 PDP-11, and almost all subsequent minicomputers and microcomputers.

Converting from two's complement representation

A two's-complement number system encodes positive and negative numbers in a binary number representation. The weight of each bit is a power of two, except for the most significant bit, whose weight is the negative of the corresponding power of two.
The value of an -bit integer is given by the following formula:
The most significant bit determines the sign of the number and is sometimes called the sign bit. Unlike in sign-and-magnitude representation, the sign bit also has the weight shown above. Using bits, all integers from to can be represented.

Converting to two's complement representation

In two's complement notation, a non-negative number is represented by its ordinary binary representation; in this case, the most significant bit is 0. Though, the range of numbers represented is not the same as with unsigned binary numbers. For example, an 8-bit unsigned number can represent the values 0 to 255. However a two's complement 8-bit number can only represent non-negative integers from 0 to 127, because the rest of the bit combinations with the most significant bit as '1' represent the negative integers −1 to −128.
The two's complement operation is the additive inverse operation, so negative numbers are represented by the two's complement of the absolute value.

From the ones' complement

To get the two's complement of a negative binary number, all bits are inverted, or "flipped", by using the bitwise NOT operation; the value of 1 is then added to the resulting value, ignoring the overflow which occurs when taking the two's complement of 0.
For example, using 1 byte, the decimal number 5 is represented by
The most significant bit is 0, so the pattern represents a non-negative value. To convert to −5 in two's-complement notation, first, all bits are inverted, that is: 0 becomes 1 and 1 becomes 0:
At this point, the representation is the ones' complement of the decimal value −5. To obtain the two's complement, 1 is added to the result, giving:
The result is a signed binary number representing the decimal value −5 in two's-complement form. The most significant bit is 1, signifying that the value represented is negative.
Alternatively, instead of adding 1 after inverting a positive binary number, 1 can be subtracted from the number before it is inverted. The two methods can easily be shown to be equivalent. The inversion of equals, so the sum of the inversion and 1 equals, which equals the two's complement of as expected. The inversion of equals, identical to the previous equation. Essentially, the subtraction inherent in the inversion operation changes the −1 added to before the inversion into +1 added after the inversion. This alternate subtract-and-invert algorithm to form a two's complement can sometimes be advantageous in computer programming or hardware design, for example where the subtraction of 1 can be obtained for free by incorporating it into an earlier operation.
The two's complement of a negative number is the corresponding positive value, except in the special case of the most negative number. For example, inverting the bits of −5 gives:
And adding one gives the final value:
The two's complement of the most negative number representable is itself. Hence, there is an 'extra' negative number for which two's complement does not give the negation, see below.
The case for the most negative number is one of only two special cases. The other special case is for zero, the two's complement of which is zero: inverting gives all ones, and adding one changes the ones back to zeros. Mathematically, in the two's complement system of signed integers, this is obviously correct: the negative of 0 is in fact 0. This zero case also makes sense by the definition of two's complements: by that definition, the two's complement of zero would be, but in bits, all values are taken modulo, and. In other words, the two's complement of 0 in bits is a single 1 bit followed by zeros, but the 1 gets truncated, leaving 0.
In summary, the two's complement of any number, either positive, negative, or zero, can be computed in the same ways. In two's complement signed integer representation, the two's complement of any integer is equal to -1 times that integer, except for the most negative integer representable in the given number of bits, i.e. the integer, the two's complement of which is itself.