Two's complement
The two's complement (also 2complement  generalized bcomplement (b base) , two complement , B (inary) complement , base complement , two's complement ) is a representation for negative integer numbers in the dual system , which does not have additional characters like + and  needed. This is important in digital technology (especially in computers ), since the two's complement allows the subtraction type of calculation to be traced back to the addition and as part of an adderperform. The two's complement requires a restricted, predefined format (bit length) for the representation of binary numbers , as the agreement requires a fixed meaning for the most significant data bit.
The two's complement can be seen as a way of interpreting formatted binary bit sequences which occurs for negative values of integer variables for which a value range divided into positive and negative is defined. These are the socalled "signed integer" in contrast to the "unsigned integer" in programming languages. For the latter, a two's complement does not occur.
motivation
Saved value  Decimal interpretation  

Am  Hex  0's  BuV  1'S  2'S 
0000  0  0  0  0  0 
0001  1  1  1  1  1 
0010  2  2  2  2  2 
0011  3  3  3  3  3 
0100  4th  4th  4th  4th  4th 
0101  5  5  5  5  5 
0110  6th  6th  6th  6th  6th 
0111  7th  7th  7th  7th  7th 
1000  8th  8th  −0  −7  −8 
1001  9  9  −1  −6  −7 
1010  A.  10  −2  −5  −6 
1011  B.  11  −3  −4  −5 
1100  C.  12  −4  −3  −4 
1101  D.  13  −5  −2  −3 
1110  E.  14th  −6  −1  −2 
1111  F.  15th  −7  −0  −1 
In the case of binary coding of negative numbers that are not in two's complement format, both the sign and the amount are represented by separate bits, so it is important to know which bit is used for what. This is usually achieved by having all numbers have a constant number of digits and, if necessary, padded with leading zeros and a separate bit that encodes the sign. Corresponding control logics are then required for processing, which evaluate the different bits and their meaning.
When coding in the two's complement representation, on the other hand, it is not necessary to explicitly differentiate between a marked sign bit and the bits that describe the amount. Negative numbers can be recognized by the fact that the most significant bit has the value 1
. At 0
is a positive number or the value 0. The advantage of this number format is that no additional control logic is required for processing in digital circuits.
Since in the two's complement representation the value 0 is assigned to the positive numbers, the value range for binary digits generally includes the range (unless otherwise defined):
Examples:
bei 8 Bit: −128_{(10)} bis +127_{(10)} bei 16 Bit: −32768_{(10)} bis +32767_{(10)} bei 32 Bit: −2147483648_{(10)} bis +2147483647_{(10)} bei 64 Bit: −9223372036854775808_{(10)} bis +9223372036854775807_{(10)}
Representation and conversion from the decimal system
The two's complement representation, unlike the one's complement representation , does not need to distinguish between cases, whether it is calculated with negative or positive numbers. The problem of one's complement representation of having two representations for the zero does not arise. In the two's complement representation, positive numbers are provided with a leading 0
(sign bit) and are otherwise not changed.
Negative numbers are coded from a positive number as follows: All binary digits are negated and the value 1 is added to the result . (For the mathematically exact procedure, see formal conversion .)
Exemplary conversion of the negative decimal number −4 into the two's complement representation using 8 binary digits:
 Ignore sign and convert into binary system: 4 _{(10)} = 00000100 _{(2)}
 Invert: Not [00000100] = 11111011
 Add one: 11111011 + 00000001 = 11111100
11111100_{(2)} = −4_{(10)}
Conversion by hand
Trick for faster conversion (a negative into a positive binary number or vice versa) by hand: Starting from the right, copy all zeros and the first one and invert all subsequent digits.
 Start at the right digit ( least significant bit ).

 If this digit is a 0 , write a 0 and go to point 3;
 If this digit is a 1 , write a 1 and go to point 4 .
 Go one sign to the left and repeat point 2 .
 Invert all remaining digits up to the most significant bit .
Alternative rule of thumb:
 Invert all digits
 Add 1
Alternatives
Separate interpretation of the sign bit
The two's complement representation can also be illustrated as follows: All bits have the same significance as with a positive representation. The MSB (most significant bit), however, receives the negative significance. By subtracting this bit, numbers can be converted very quickly. Example with 8bit binary numbers in two's complement representation:
Value  −128  64  32  16  8th  4th  2  1  Decimal 

Bit sequence  0  0  0  1  1  0  1  0  = 26 
Bit sequence  1  1  1  0  0  1  1  0  = −26 
00011010_{(2)} = 16 + 8 + 2 = 26 11100110_{(2)} = −128 + 64 + 32 + 4 + 2 = −26
The correctness of this procedure is explained in a subsequent section .
Subtraction from the value range limit
Another method is to simply add the number, if it is negative, to the number just beyond the range of values. For example, unsigned 8bit numbers cover the value range 0–255, the number immediately following is 256. A −1 just needs to be added to 256 and you get the value 255 (= 1111 1111b), as required. Similarly, a –128 leads to the value 128.
Interpretation in the remainder class ring
To understand the two's complement, it is helpful to keep in mind that common microprocessors calculate in residual class rings . In fact, it is not about treating positive and negative numbers differently, rather it is about an agreement as to which representatives are elected to describe a certain residual class.
The four basic arithmetic operations in the dual system are completely the same for positive and negative numbers.
In the context of the previous examples, one can consider the calculation (−7) · (−3) on a computer with 8 bit word length. With an 8bit word length, the number range that can be represented is 0 to 255, and even that is a selection of representatives, because it is actually about classes of the remainder class ring . And at this point you can choose the numbers from 0 to 255 as representatives, or, completely equivalent, the numbers −128 to 127. When calculating in two's complement, numbers are, strictly speaking, not “converted” at all, rather they become suitable for arithmetic Representatives of the remaining classes involved elected.
In the example, the representatives 253 and 249 can be selected for −3 and −7:
Multiplied it results:
When “converting” positive to negative numbers, which is actually just a skilful selection of representatives of the remaining classes involved, the special charm of the two's complement catches the eye: −1 is nothing other than the result of the calculation 0 minus 1 calculated in the basic arithmetic operations of the dual system. A carry bit is only added to the 8 bits of a register as used in this example.
Bit position:  C 7 6 5 4 3 2 1 0 
0:  0 0 0 0 0 0 0 0 0 
Subtract 1:  0 0 0 0 0 0 0 0 1 
Result:  1 1 1 1 1 1 1 1 1 
The result is the two's complement representation of −1 and the carry bit is also set correctly.
One can now interpret the conversion of numbers into two's complement in the remainder class ring. If z. For example, if the representation of −3 is sought, −3 is in the same congruence class as 253. So it is sufficient to add the value 256 to −3 to get a usable representative.
If you now add up the bit positions of bits 0 to 7, this is 255. If you take 3 as the “positive” decimal number and invert this bit by bit, the “supplementary value” is 255, ie 255  3. And if the result is incremented , this is (because of the commutative and associative law of addition)
The whole bit by bit:
Bit position:  C 7 6 5 4 3 2 1 0 
+3:  0 0 0 0 0 0 0 1 1 
~ =  1 1 1 1 1 1 1 0 0 
++  1 1 1 1 1 1 1 0 1 
At the end, the carry bit is set, which indicates a negative number, and the bit sequence 11111101, which corresponds to decimal 253.
Earlier in the text, the interpretation of the carry bit was suggested as −256. Incidentally, this can also be found at Tietze / Schenck. In fact, you can add 256 or subtract 256 to a number in the remainder class ring as often as you like. The congruence class is not left. This also applies to integer multiples of 256. If the carry bit is interpreted as −256, and 1 1 1 1 1 1 1 0 1 consequently as −256 + 253 = −3, one actually only has the formula 253 = −3 + 256 written differently.
Change of sign in the remainder class ring
The interpretation in the residual class ring of the two's complement also allows the following representation of a sign change.
If the binary representation is a digit number, this can easily be deducted from: is just the number one after the other . With a digitbydigit subtraction, only the differences or are shown there . No carryovers are necessary; each digit can be viewed in isolation.
In fact, this means that the subtraction corresponds to the bitwise complement of:, where is the bitwise complement of .
In the remainder of the class this means nothing other than:
and thus
and after adding 1 on both sides:
In general, the sign of can be reversed by inverting bit by bit in the first step and adding 1 in the second step.
This corresponds exactly to the “alternative rule of thumb” described in the section Conversion by hand . And it works in both directions, regardless of whether a decimal number is first to be converted into the binary system and then the sign is reversed, or whether the sign is first reversed for a negative number in order to then convert the positive number obtained into the decimal system.
Arithmetic operations
Addition and subtraction
Addition and subtraction do not require any case distinction. The subtraction is reduced to an addition.
Examples of 8bit long numbers without sign extension:
−4 + 3 = −1 entspricht: 11111100 + 00000011 = 11111111
+4 +(− 4) = 0 entspricht: 00000100 + 11111100 = 100000000
The first one, in this example the 9th digit, is discarded.
+4 − 3 = +1 entspricht: −4 − 3 = −7 entspricht: 00000100 11111100 + 11111101 + 11111101 = 100000001 = 111111001
Here, too, the correct result is generated by omitting the 9th digit, in these cases 1
.
As long as the valid ndigit range of numbers, in the case of 8bit numbers, the value range of the sum from −128 to +127, is not left, this procedure works without a sign extension. If, on the other hand, the value range of the sum is outside the interval, an overflow occurs , which in this context is often and incorrectly confused with the carry . The remedy is to extend the sign before the arithmetic operation.
Sign extension
If the two summands can take any values, a sign extension is necessary for correct addition in two's complement representation . First of all, the top digit of both summands is duplicated, thus increasing the number of digits by one. In these examples the 8th position, which is copied to the 9th position. Then the addition is carried out as above, but with 9 digits. The adder must always include one more digit.
If the highest value and the digit below differ from one another in the calculated sum, the result can no longer be represented in the value range of the summands  an overflow has occurred. Depending on the application, the result is one bit wider and more correct, or the result is an error termination.
Example: Adding the two positive numbers 50 and 80 results in 130 and thus exceeds the range of values. The number still fits in an 8bit variable, but the 8th bit is now set so that the number appears incorrectly negative. Some microprocessors such as the 6502 report such an event with their own status bit, here the overflow bit O , which the programmer queries for signed arithmetic operations and can react accordingly.
Example of a sign extension, the 9th position of the sign extension is written in brackets for clarity:
+4 + 127 = +131 führt zu −4 − 127 = −131 führt zu (0)00000100 (1)11111100 + (0)01111111 + (1)10000001   Ü* (0)11111000 Ü* (1)00000000   = (0)10000011 = (1)01111101
* Übertrag
In both cases the 8th and 9th digits differ from each other; a reduction to 8 bits would lead to an error. For clarification and comparison, the above two examples with sign extension:
+4 − 3 = +1 führt zu −4 − 3 = −7 führt zu (0)00000100 (1)11111100 + (1)11111101 + (1)11111101   Ü (1)11111000 Ü (1)11111000   = (0)00000001 = (1)11111001
in both cases the 8th and 9th digits of the total do not differ, so the two results can be correctly reduced to 8 digits again. In general, the number of digits in the two's complement representation, starting from the top, can be reduced without falsifying the value until the two highest digits differ in value from each other. This illustrates the fact that there is no fixed position for the coding of the sign in the two's complement representation of numbers.
multiplication
The multiplication is also possible in the two's complement representation in the context of multipliers and represents a basic function in digital signal processing in particular . There are various possibilities for the circuitry implementation of multipliers. With a parallel multiplier, the product is formed by extending the sign, shifting the digits and then adding. The individual factors must always be signextended to the product length. In addition to the parallel multipliers, there are also more efficient implementation variants of multiplication, which are based on the Booth algorithm or the bitpair method .
With two factors, each 4 bits long, the product is 8 bits long. Or in general: For two n bit or m bit wide factors, the product is n + m bits long and all factors must be extended to this length with the correct sign prior to the calculation using a parallel multiplier. This should be clarified with the operation −7 · −3 in two's complement representation, the factors of which can be represented with 4 bits each:
11111001 (entspricht dezimal der Zahl −7, mit Vorzeichenerweiterung) · 11111101 (entspricht dezimal der Zahl −3, mit Vorzeichenerweiterung)  + 11111001 (1001 · 1, um null Stellen nach links verschoben und mit Vorzeichenerweiterung) + 00000000 (1001 · 0, um eine Stelle nach links verschoben und mit Vorzeichenerweiterung) + 11100100 (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung) + 11001000 (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung) + 10010000 (1001 · 1, um vier Stellen nach links) + 00100000 (1001 · 1, um fünf Stellen nach links, obere Bits hinausgeschoben) + 01000000 (1001 · 1, um sechs Stellen nach links, obere Bits hinausgeschoben) + 10000000 (1001 · 1, um sieben Stellen nach links, obere Bits hinausgeschoben)  00010101 (entspricht dezimal +21)
Because of the sign extension, the number of summands can be reduced. The reason is that the upwardly signed bits of the individual factors in two's complement always have identical values. In this example, the sum of the last five lines always delivers the negated value of the fourth line, which in this case reduces the calculation to the summation of three lines and the subtraction of the last line and thus to half of the above effort:
1001 (entspricht dezimal der Zahl −7) · 1101 (entspricht dezimal der Zahl −3)  + 11111001 (1001 · 1, um null Stellen nach links verschoben und mit Vorzeichenerweiterung) + 00000000 (1001 · 0, um eine Stelle nach links verschoben und mit Vorzeichenerweiterung) + 11100100 (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung) − 11001000 (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung)  00010101 (entspricht dezimal +21)
The subtraction in the last line applies regardless of the signs of the two factors, even if the number of digits is different, and there is no need to distinguish between the signs of the factors or to correct the sign of the calculated product. In circuit implementations, this subtraction can be done either by full adders, which can be switched to subtraction mode, or by inverting the last line and adding +1, analogous to the formation of the two's complement.
To illustrate this optimized method, a multiplication with different signs (−7) 3 in two's complement representation:
1001 (entspricht dezimal der Zahl −7) · 0011 (entspricht dezimal der Zahl 3)  + 11111001 (1001 · 1) + 11110010 (1001 · 1) + 00000000 (1001 · 0) − 00000000 (1001 · 0)  11101011 (entspricht dezimal −21)
Conversion to the decimal system
If you want to recode a number from the two's complement representation to the decimal system , you have to proceed as follows (vice versa, corresponding to the conversion from the decimal system to the two's complement representation):
 Look at the first digit: if number = 1: negative number, number = 0: positive number.
 Number is positive: Conversion from the binary system to the decimal system is already possible;
 Number is negative: You subtract 1 and negate the individual digits. (This step can be simplified for humans: you first negate the individual digits and then add 1, which leads to the same result.)
 The resulting, correspondingly positive number in the binary system is converted into the decimal system.
 If negative, put a "  " in front of the number.
Example:
11111101 1 subtrahieren = 11111100 invertiert = 00000011 00000011 im Dezimalsystem = 3 3 negativ = −3
11111101 (Zweierkomplementdarstellung) = −3 (Dezimalsystem)
Another procedure for converting a number in two's complement representation into the decimal system is as follows: Have the number in two's complement representation places, i.e. bits are given :
Formal conversion from the binary system
If it is a negative number, it is calculated in two's complement representation ( ) with digits as follows:
Accordingly, it also applies
where corresponds to the positive number and occurs in the calculation as a carryover in the th digit
Formal background to alternative changes
Separate interpretation of the sign bit
The following transformations show that this alternative conversion is correct. If the two's complement representation is a digit negative number and the suffix is, the value is calculated as follows:
Here is the interpretation function that determines the numerical value of a two's complement number. The second line results from the definition of a negative two's complement number and the third from the conversion into the positive representation of the two's complement number, where the complement should be of. The fourth line then follows from the fact that the complement formation can also be represented as a subtraction from a onestring of length ( ) . The last line corresponds exactly to the alternative conversion rule and therefore shows its correctness.
Subtraction from the value range limit
The correctness of this procedure is easy to see when one takes into account the order in which the numerical values are distributed in the space of the bit strings for a bit two's complement number:
I.e. By subtracting the number from the value range limit, when calculating in the binary system, one obtains the coding of in two's complement.
Two's complement representation for fixed point numbers
The two's complement representation can also be used for fixedpoint numbers , with which, for example, fractional numbers can be represented as binary. Fixedpoint numbers are used, among other things, in the field of digital signal processing . Fixedpoint numbers are generally formed by moving the decimal point, which is always to the right of the last digit in whole numbers. The decimal point is not saved in the binary representation, but implicitly its position is assumed to be fixed, from which the name of the fixed point representation is derived.
In principle, the calculation rules mentioned above are retained, only the values change. To form a binary two's complementary representation, all binary digits must be inverted and then the value of a quantization level 2 ^{k} must be added. K indicates the position of the last binary digit that can be represented. In the case of the above integers, this would be the position k = 0, which means that the value 2 ^{0} = 1 must be added after the inversion when forming the twocomplement for integers . For example, if the decimal point is shifted 2 places to the left and the binary word includes the two places to the right of the decimal point, k = −2, and thus 2 ^{−2} = 0.25 must be added to form the two's complement . (Note: With fixedpoint numbers, the decimal point can also be outside the range of values that can be represented.)
An example should clarify this: A binary number with a fivebit word length has three places before the decimal point and two places after the decimal point. This means that the value range −4 to +3.75 can be displayed in steps of 0.25. The number 2.25 corresponds to the binary number 010.01 _{2} . If the two's complement is now formed, all digits of the binary number are inverted and 2 ^{−2} = 0.25 is added, which results in 101.11 _{2} = −2.25.
Generalization to other place value systems
Whole numbers can also be represented in other place value systems without using a minus sign. The problem here is that the distinction between positive and negative numbers can be more or less arbitrarily agreed.
If you limit yourself to digit numbers for the base , then you can represent the natural numbers from 0 to . If one defines a number in this range as the largest positive number, then any larger number can be viewed as a two's complement representation of the negative number .
The arithmetic operation of the negation is carried out in the same way as for base 2: Each digit is replaced by , and 1 is added to the resulting number.
For the base and the number of digits we get this representation for −1:
 The digits of the 1 are 001.
 The negation of the digits results in 443.
 Adding 1 gives 444.
This represents −1 as 444. The addition 444 + 001 (to base 5 and number of digits 3) results in 000, since the last carry is omitted.
In this example, if we define the largest positive number as 222 (base 5, decimal this number has the value +62), then 223 = −222 is the smallest negative number (decimal −62). The range of numbers extends from decimal −62 to +62.
For base 10 and number of digits 2 one has 99 = −01 and 50 = −50, so here, as with base 2, one has another number besides 0, which corresponds to its two's complement representation. This phenomenon occurs with every even base.
If you generalize this notation further by allowing an infinite number of digits, you get the possibility to represent padic integers .
See also
literature
 Ulrich Tietze, Christoph Schenk: Semiconductor circuit technology . 12th edition. Springer, Berlin 2002, ISBN 3540428496 .
Web links
 A Java applet for practicing binary addition , there the register "conegative numbers" (requires Java)
 2's complement to decimal number, decimal number to 2's complement  JavaScript converter (any precision)
Individual evidence
 ^ Herbert SchneiderObermann: Basic knowledge of electrical, digital and information technology . 1st edition. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage GmbH, Wiesbaden 2006, ISBN 9783528039790 . , Table 2.1: "Negative numbers in the dual system" in Section 2.1.5 "Representation of negative numbers in the dual system"