Ones' complement

The ones complement, also (b-1) complement, is an arithmetic operation that is mostly used in the dual system. All digits or bits of a binary number (dual number) are inverted, i.e. 0 becomes 1 and vice versa. As a result, each digit of the binary number and its corresponding digit of the ones complement "add up to 1", which gives the operation its name. Thus, if an -digit binary number, then its one's complement is

a subtraction in which no carries occur. The operation is also called bitwise negation and the operator is notated as tilde ~ in various programming languages. The number is understood as a bit string.

One application of the one's complement is the simultaneous manipulation of individual bits in a bit string. For example, if you want to delete all bits in the bit string Number that are set in the bit string Mask, you can AND Number with the one's complement of Mask bit by bit, in C syntax Number &= ~Mask;

Another application is the one's complement representation, a method for the binary representation of negative integers. Although it is easy to describe - the complement of the representation of a negative number is the normal binary representation of its absolute value - the implementation of an arithmetic unit for numbers represented in this way is cumbersome. Compared to today's usual two's complement representation, it has advantages only for division, which is usually slow anyway, for multiplication with double-length results, and for the formation of simple checksums.

One's complement representation

Comparison of the representation of a nibble (4 bits) as unsigned value (0's), as magnitude and sign (BuV), in one's complement (1'S) and in two's complement (2'S)
Stored value		Decimal interpretation
Sync and corrected by dr.jackson for	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	4	4	4	4	4
0101	5	5	5	5	5
0110	6	6	6	6	6
0111	7	7	7	7	7
1000	8	8	−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	14	−6	−1	−2
1111	F	15	−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: 0 for plus, 1 for minus,
• they agree for positive numbers with the unsigned representation, in which small numbers are supplemented with zeros in front.

Differences exist if the most significant bit is set. In this case, in the one's complement representation, the absolute value is obtained by complementation. For example, 1010 turns out to be negative due to the leading 1 and the absolute value is ~1010, i.e. 0101 = 5. This definition results in the following further properties of the one's complement representation:

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

The examples here are given for a word width of n = 4 bit. For 8 and 16 bits, the maximum amounts are 127 and 32767, respectively, generally

Arithmetic operations and problems

The simplest arithmetic operation in one's complement representation is the arithmetic negation (unary --operator). Only the bitwise complement has to be formed. Thus the subtraction (binary --operator) can be directly traced back to the addition: 3 - 4 = 3 + (-4). To perform this addition, an adder constructed for unsigned numbers gives the correct result:

           1011 (-4) + 0011 (+3) Carryovers 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 after a simple binary number addition of the two one's complement representations, a wrong intermediate result appears at first:

 -4 + 6 = +2 leads to 1011 + 0110 carryovers 1110 ----- = 0001 (intermediate result)

The 0001 would stand for +1, not for +2. In order for a correct result to appear, the carry furthest to the left must be evaluated (1 in this case) and, if necessary, the result increased by 1. In other words, the carry must still be added to the intermediate result:

          0001 (intermediate result) + 1 (carry-over of the previous operation) ----- = 0010

In the first example above, the carry 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 expansion of the magnitude of the representable numbers is not exploited. The representable number space is reduced by 1; since the zero is present twice, a data word for the number space is dropped. However, the representation of every other number remains unique. In the example here with 4 bits, only 15 different numbers (from -7 to 7) are represented with the ²⁴ = 16 different bit combinations.

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

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