One's complement

The one's complement , also (B-1) -complement , is an arithmetic operation that is mostly used in the dual system . In doing so, all digits or bits of a binary number are inverted, i.e. it 0becomes off 1and vice versa. As a result, each digit of the binary number and its corresponding digit of the one's complement “ 1complement” each other, which gives the operation its name. The operation is also known as bitwise negation and the operator is noted as a tilde in various programming languages~ .

In principle, numbers in the register of a computer are represented as 0 and 1. The one's complement is one of several known ways of interpreting this stored value as a decimal number and processing it in arithmetic operations.

One application of one's complement is the simultaneous manipulation of individual bits in a data word . For example, if you want to Zustanddelete all bits in the word Maskethat are set in the word , you have to Zustanduse the one's complement of Maskebitwise and-combine , in C syntaxZustand &= ~Maske;

Another application is one's complement representation , a technique for binary representation of negative integers . It can be described easily - the complement of the representation of a negative number is the normal binary representation of its amount - but the implementation of an arithmetic unit for numbers represented in this way is cumbersome. It only has advantages over the two's complement representation that is common today in the case of division, which is usually slow anyway, in multiplication with twice the long result, and in the formation of simple checksums .

One's complement representation

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

Binary encodings of signed integers usually have the following properties:

a constant number n of digits is used ,
the most significant bit indicates the sign : 0for plus, 1for minus,
for positive numbers they agree with the unsigned representation, in which small numbers are supplemented with zeros in front.

There are differences when the most significant bit is set. In this case, the amount is obtained by forming the complement in the one's complement representation. For example, 1010the leading turns out to 1be negative and the amount is ~1010, therefore 0101= 5. This definition results in the following additional properties of the one's complement representation:

there are two representations for the number 0, +0 = 0000and −0 = 1111,
positive and negative numbers extend symmetrically up to the same amount, here 7 = 0111.

The examples are given here for a word length of n = 4 bits. For 8 and 16 bits, the maximum amounts are 127 and 32767, in general ${\ displaystyle 2 ^ {n-1} -1.}$

Arithmetic operations and problems

The simplest arithmetic operation in one's complement representation is the arithmetic negation (unary -operator). It is only necessary to form the bit-wise complement. This means that the subtraction (binary -operator) can be traced back directly to the addition: 3 - 4 = 3 + (−4). To carry out this addition, an adder constructed for unsigned numbers gives the correct result:

          1011 (−4)
       +  0011 (+3)
Übertrag 0011
         —————
       =  1110 (−1)

The disadvantage of the one's complement representation is the handling of the case when the zero is crossed during an operation. Example: When calculating −4 + 6 = +2, an incorrect intermediate result initially appears after a simple binary addition of the two one's complement representations:

 −4 + 6 = +2 führt zu
          1011
       +  0110
Übertrag 1110
         —————
       =  0001 (Zwischenergebnis)

The 0001stood for +1, not for +2. For a correct result to appear, the leftmost carry must be evaluated (here 1) and the result increased by 1 if necessary. In other words, the carryover has to be added to the intermediate result:

          0001 (Zwischenergebnis)
       +     1 (Übertrag der vorhergehenden Operation)
         —————
       =  0010

In the first example above, the carryover is 0, so the intermediate result there already corresponds to the final result.

Another disadvantage is the emergence of redundancy : There are two representations for the zero: 0000(+0) and 1111(−0), see signed zero . On the one hand, with a limited number of bits, the maximum extent of the amount of the numbers that can be represented is not used. The number range that can be represented is reduced by 1; since the zero is present twice, a data word for the number range is omitted. The representation of every other number remains clear. In the example here with 4 bits, only 15 different numbers (from −7 to 7) are represented with the 2 ⁴ = 16 different bit combinations.

Both problems described are avoided when coding numbers in the two's complement representation .

The adding of the carry improves the sensitivity of a simple checksum against multiple bit errors. For example, a checksum with modulo arithmetic ignoring carries would not indicate a transmission error with a probability of 50% if the most significant bit is often wrong, e.g. B. constant zero. The TCP uses a checksum in one's complement arithmetic, which does not have this deficiency and whose efficient calculation on hardware without one's complement arithmetic unit is described in RFC 1071 .

Generalization to B-adic systems

The inversion, which is only possible in the binary system, corresponds to the calculation rule with base B of the place value system. In the decimal system, the number has to be subtracted from 9. Some authors then speak of the nine's complement and generally of the (B-1) complement ${\ displaystyle {\ overline {a}} ~ = ~ (B-1) -a}$

Example for the decimal system (three digits):

-456₁₀ = ((9-4)(9-5)(9-6))_9K = (543)_9K

And an example calculation:

 112        112
-  3        996
-  4        995
-  5        994
————       ————
 100     (3)097 = 100 (Übertrag zum Ergebnis hinzuaddieren)

Web links

John Walker : Minus Zero. UNIVAC Memories - one's complement on UNIVAC 1100 computers (English)

Individual evidence

↑ Helmut Herold: Foundations of Computer Science . Pearson Studium, Munich 2007, ISBN 978-3-8273-7305-2 , p. 59
^ Herbert Schneider-Obermann: Basic knowledge of electrical, digital and information technology . 1st edition. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage, 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
↑ RFC 1071: Computing the Internet Checksum
↑ Neunerkomplement atrechnerlexikon.de; Retrieved April 6, 2015.

[1] Helmut Herold: Foundations of Computer Science . Pearson Studium, Munich 2007, ISBN 978-3-8273-7305-2 , p. 59

[2] Herbert Schneider-Obermann: Basic knowledge of electrical, digital and information technology . 1st edition. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage, 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

[3] RFC 1071: Computing the Internet Checksum

[4] Neunerkomplement atrechnerlexikon.de; Retrieved April 6, 2015.