Two's complement

The two's complement (also 2-complement - generalized b-complement (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 so-called "signed integer" in contrast to the "unsigned integer" in programming languages. For the latter, a two's complement does not occur.

motivation

Comparison of the representation of a nibble (4 bits) as an unsigned value (0's), as an amount and sign (BuV), in one's complement (1'S) and in two's complement (2'S)

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 0is 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): ${\displaystyle n}$

${\displaystyle -2^{n-1},\dotsc ,0,\dotsc ,2^{n-1}-1}$

Examples:

bei 8 Bit:                  −128(10)  bis                 +127(10)
bei 16 Bit:               −32768(10)  bis               +32767(10)
bei 32 Bit:          −2147483648(10)  bis          [phone](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:

1. Ignore sign and convert into binary system: 4 ₍₁₀₎ = 00000100 ₍₂₎
2. Invert: Not [00000100] = 11111011
3. 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.

1. Start at the right digit ( least significant bit ).
2. 1. If this digit is a 0 , write a 0 and go to point 3;
   2. If this digit is a 1 , write a 1 and go to point 4 .
3. Go one sign to the left and repeat point 2 .
4. Invert all remaining digits up to the most significant bit .

Alternative rule of thumb:

1. Invert all digits
2. 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 8-bit 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 8-bit 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 8-bit 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. ${\displaystyle \mathbb {Z} /256\mathbb {Z} }$

In the example, the representatives 253 and 249 can be selected for −3 and −7:

${\displaystyle -3{\mathrel {\widehat {=}}}253(256)}$

${\displaystyle -7{\mathrel {\widehat {=}}}249(256)}$

Multiplied it results:

${\displaystyle -3\cdot -7{\mathrel {\widehat {=}}}253\cdot 249{\mathrel {\widehat {=}}}62997{\mathrel {\widehat {=}}}21(256)}$

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)

${\displaystyle 255-3+1=1+255-3=256-3}$

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. ${\displaystyle \mathbb {Z} /256\mathbb {Z} }$

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 digit-by-digit subtraction, only the differences or are shown there . No carry-overs are necessary; each digit can be viewed in isolation. ${\displaystyle x_{z}=(x_{n-1},x_{n-2},\dotsc ,x_{1},x_{0})}$ ${\displaystyle n}$ ${\displaystyle 2^{n}-1}$ ${\displaystyle 2^{n}-1}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle 1-1=0}$ ${\displaystyle 1-0=1}$

In fact, this means that the subtraction corresponds to the bitwise complement of:, where is the bitwise complement of . ${\displaystyle (2^{n}-1)-x_{z}}$ ${\displaystyle x_{z}}$ ${\displaystyle (2^{n}-1)-x_{z}={\overline {x_{z}}}}$ ${\displaystyle {\overline {x_{z}}}}$ ${\displaystyle x_{z}}$

In the remainder of the class this means nothing other than:

${\displaystyle (2^{n}-1)-x_{z}{\mathrel {\widehat {=}}}{\overline {x_{z}}}(2^{n})}$

and thus

${\displaystyle -1-x_{z}{\mathrel {\widehat {=}}}{\overline {x_{z}}}(2^{n})}$

and after adding 1 on both sides:

${\displaystyle -x_{z}{\mathrel {\widehat {=}}}{\overline {x_{z}}}+1(2^{n})}$

In general, the sign of can be reversed by inverting bit by bit in the first step and adding 1 in the second step. ${\displaystyle x_{z}}$ ${\displaystyle x_{z}}$ ${\displaystyle {\overline {x_{z}}}}$

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 8-bit 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 n-digit range of numbers, in the case of 8-bit 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 8-bit 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 sign-extended 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 bit-pair 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):

1. Look at the first digit: if number = 1: negative number, number = 0: positive number.
2. Number is positive: Conversion from the binary system to the decimal system is already possible;
3. 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.)
4. The resulting, correspondingly positive number in the binary system is converted into the decimal system.
5. 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 : ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a_{n-1}a_{n-2}a_{n-3}\ldots a_{1}a_{0}}$

${\displaystyle x_{\text{dezimal}}=-2^{n-1}\cdot a_{n-1}+2^{n-2}\cdot a_{n-2}+2^{n-3}\cdot a_{n-3}+\dotsb +2^{1}\cdot a_{1}+2^{0}\cdot a_{0}}$

Formal conversion from the binary system

If it is a negative number, it is calculated in two's complement representation ( ) with digits as follows: ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{z}}$ ${\displaystyle n}$

${\displaystyle x_{z}=2^{n}-|x|}$

Accordingly, it also applies

${\displaystyle x_{z}+|x|=2^{n}}$

where corresponds to the positive number and occurs in the calculation as a carryover in the -th digit ${\displaystyle |x|}$ ${\displaystyle 2^{n}}$ ${\displaystyle (n+1)}$

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: ${\displaystyle x_{z}=(x_{n-1},x_{n-2},\dotsc ,x_{1},x_{0})}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle v=(x_{n-2},\dotsc ,x_{1},x_{0})}$ ${\displaystyle x_{z}}$ ${\displaystyle x}$

${\displaystyle {\begin{aligned}x&=f_{ZK}\left(x_{z}\right)\\&=1\cdot 2^{n-1}+f_{ZK}\left(v\right)\\&=-(f_{ZK}({\overline {v}})+1)\\&=-((2^{n-1}-1)-f_{ZK}(v)+1)\\&=f_{ZK}(v)-2^{n-1}\end{aligned}}}$

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 one-string of length ( ) . The last line corresponds exactly to the alternative conversion rule and therefore shows its correctness. ${\displaystyle f_{ZK}}$ ${\displaystyle {\overline {v}}}$ ${\displaystyle v}$ ${\displaystyle n-1}$ ${\displaystyle 2^{n-1}-1}$ ${\displaystyle v}$

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: ${\displaystyle n}$

${\displaystyle {\begin{aligned}100\ldots 000&\rightarrow -2^{n-1}\\100\ldots 001&\rightarrow -2^{n-1}+1\\&\ \ \vdots \\111\ldots 100&\rightarrow -4\\111\ldots 101&\rightarrow -3\\111\ldots 110&\rightarrow -2\\111\ldots 111&\rightarrow -1\end{aligned}}}$

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. ${\displaystyle x\geq 1}$ ${\displaystyle 2^{n}}$ ${\displaystyle -x}$

Two's complement representation for fixed point numbers

The two's complement representation can also be used for fixed-point numbers , with which, for example, fractional numbers can be represented as binary. Fixed-point numbers are used, among other things, in the field of digital signal processing . Fixed-point 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. ${\displaystyle x={\tfrac {1}{4}}}$

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 ⁰ = 1 must be added after the inversion when forming the two-complement 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 ⁻² = 0.25 must be added to form the two's complement . (Note: With fixed-point 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 five-bit 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 ₂ . If the two's complement is now formed, all digits of the binary number are inverted and 2 ⁻² = 0.25 is added, which results in 101.11 ₂ = −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 . ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle b^{n}-1}$ ${\displaystyle x}$ ${\displaystyle x-b^{n}}$

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. ${\displaystyle z}$ ${\displaystyle (b-1)-z}$

For the base and the number of digits we get this representation for −1: ${\displaystyle b=5}$ ${\displaystyle n=3}$

• 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 p-adic integers .

See also

• One's complement

literature

• Ulrich Tietze, Christoph Schenk: Semiconductor circuit technology . 12th edition. Springer, Berlin 2002, ISBN 3-540-42849-6 .

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

1. ^ Herbert Schneider-Obermann: Basic knowledge of electrical, digital and information technology . 1st edition. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage GmbH, Wiesbaden 2006, ISBN 978-3-528-03979-0 . , Table 2.1: "Negative numbers in the dual system" in Section 2.1.5 "Representation of negative numbers in the dual system"