Two's complement is the most common method of representing signed (positive, negative, and zero) integers on computers,E.g. "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006 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 (0) or negative (1) numbers, and nonnegative numbers are given their unsigned representation (6 is 0110, zero is 0000); however, in two's complement, negative numbers are represented by taking the bit complement of their magnitude and then adding one (−6 is 1010). 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 (the range of a 4-bit number is −8 to +7). 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 (with the carry bit set).
All modern computers use two's complement, and thus standards such as C++20 and C23 require that representation.
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 (or flipping) 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 (the first 0) is the sign (just 110 in binary would be −2 in decimal). 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×23) + (0×22) + (1×21) + (0×20) = 1×−8 + 0 + 1×2 + 0 = −6. Bits:1010Decimal bit value: −8421Binary calculation:−(1×23)(0×22)(1×21)(0×20)Decimal calculation:−(1×8)01×20
Steps 2 and 3 together are a valid method to compute the additive inverse of any (positive or negative) integer where both input and output are in two's complement. An alternative to compute is to use subtraction . See below for subtraction of integers in two's complement.
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 (the only case where exactly 'two' would be produced in this term is , so for a 1-bit system, but these do not have capacity for both a sign and a zero). 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 (so and , where '2' indicates a binary representation), 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 (and the sign): 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. + Three-bit integers BitsUnsigned valueSigned value(Two's complement) 0000 0 0011 1 0102 2 0113 3 1004 −4 1015 −3 1106 −2 1117 −1 + Eight-bit integers BitsUnsigned valueSigned value (Two's complement) 0000 00000 0 0000 00011 1 0000 00102 2 0111 1110126 126 0111 1111127 127 1000 0000128 −128 1000 0001129 −127 1000 0010130 −126 1111 1110254 −2 1111 1111255 −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 (the number is nevertheless the reference point of the "Two's complement" in an -bit system). 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 (this term in binary is actually a simple number consisting of 'all 1s', and a subtraction from it can be done simply by inverting all bits in the number also known as the bitwise NOT operation) 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 (named that because summing such a number with the original gives the 'all 1s').
Compared to other systems for representing signed numbers (e.g., ones' complement), 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 (as long as the inputs are represented in the same number of bits as the output, and any overflow beyond those bits is discarded from the result). 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. (Later 18-bit DEC machines supported both ones'-complement addition with the ADD instruction and two's-complement arithmetic with the TAD instruction.) 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 (1955) and the Digital Equipment Corporation PDP-5 (1963) and PDP-6 (1964). (The PDP-5 and PDP-8 family computers continued using the assembler mnemonic TAD for two's complement addition, even though there was no ones'-complement ADD instruction on those computers.) 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. However, 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 (11111111). However, a two's complement 8-bit number can only represent non-negative integers from 0 to 127 (01111111), 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 (=8 bits), the decimal number 5 is represented by
The most significant bit (the leftmost bit in this case) 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. The most significant bit is 1, signifying that the value represented is negative.