 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(January 2014) (Learn how and when to remove this message) |
| Bits | Unsigned value | Ones' complement value |
|---|---|---|
| 000 | 0 | 0 |
| 001 | 1 | 1 |
| 010 | 2 | 2 |
| 011 | 3 | 3 |
| 100 | 4 | −3 |
| 101 | 5 | −2 |
| 110 | 6 | −1 |
| 111 | 7 | −0 |
| Bits | Unsigned value | Ones' complement value |
|---|---|---|
| 0000 0000 | 0 | 0 |
| 0000 0001 | 1 | 1 |
| 0000 0010 | 2 | 2 |
| 0111 1110 | 126 | 126 |
| 0111 1111 | 127 | 127 |
| 1000 0000 | 128 | −127 |
| 1000 0001 | 129 | −126 |
| 1111 1101 | 253 | −2 |
| 1111 1110 | 254 | −1 |
| 1111 1111 | 255 | −0 |
Theones' complement of abinary number is the value obtained by inverting (flipping) all the bits in the number (that is, changing each 1 to a 0 and each 0 to a 1). The name "ones' complement"[1] refers to the fact that such an inverted value, if added to the original, would always produce an "all ones" number (the term "complement" refers to such pairs of mutuallyadditive inverse numbers, here in respect to a non-0 base number). This mathematical operation is primarily of interest incomputer science, where it has varying effects depending on how a specific computer represents numbers.
Aones' complement system orones' complement arithmetic is a system in which negative numbers are represented by the inverse of the binary representations of their corresponding positive numbers. In such a system, a number is negated (converted from positive to negative or vice versa) by computing its ones' complement. An N-bit ones' complement numeral system can only represent integers in the range −(2N−1−1) to 2N−1−1 whiletwo's complement can express −2N−1 to 2N−1−1. It is one of three common representations fornegative integers in binary computers, along withtwo's complement andsign-magnitude.
Theones' complement binarynumeral system is characterized by thebit complement of any integer value being the arithmetic negative of the value. That is, inverting all of the bits of a number (the logical complement) produces the same result as subtracting the value from 0.
Many early computers, e.g., theUNIVAC 1101,CDC 160,CDC 1604,CDC 6600,LINC,DEC PDP-1,UNIVAC 1107, and their successors, used ones' complement arithmetic. Successors of the CDC 6600 continued to use ones' complement arithmetic until the late 1980s along with the descendants of the UNIVAC 1107 (theUNIVAC 1100/2200 series), but all modern computers usetwo's complement.
Positive numbers are the same simple, binary system used by two's complement and sign-magnitude. Negative values are the bit complement of the corresponding positive value. The largest positive value is characterized by the sign (high-order) bit being off (0) and all other bits being on (1). The lowest negative value is characterized by thesign bit being 1, and all other bits being 0. The table below shows all possible values in a four-bit system, from −7 to +7.
+ −0 0000 1111 — Both +0 and −0 return TRUE when tested for zero1 0001 1110 — and FALSE when tested for non-zero. 2 0010 11013 0011 11004 0100 10115 0101 10106 0110 10017 0111 1000
Adding two values is straightforward. Simply align the values on theleast significant bit and add, propagating any carry to the bit one position left. If the carry extends past the end of the word it is said to have "wrapped around", a condition called an "end-around carry". When this occurs, the bit must be added back in at the right-most bit. This phenomenon does not occur in two's complement arithmetic.
0001 0110 22+ 0000 0011 3=========== ==== 0001 1001 25
Subtraction is similar, except that borrows, rather than carries, are propagated to the left. If the borrow extends past the end of the word it is said to have "wrapped around", a condition called an "end-around borrow". When this occurs, the bit must be subtracted from the right-most bit. This phenomenon does not occur in two's complement arithmetic.
0000 0110 6− 0001 0011 19=========== ====1 1111 0011 −12 —An end-around borrow is produced, and the sign bit of the intermediate result is 1.− 0000 0001 1 —Subtract the end-around borrow from the result.=========== ==== 1111 0010 −13 —The correct result (6 − 19 = −13)
It is easy to demonstrate that the bit complement of a positive value is the negative magnitude of the positive value. The computation of 19 + 3 produces the same result as 19 − (−3).
Add 3 to 19.
0001 0011 19+ 0000 0011 3=========== ==== 0001 0110 22
Subtract −3 from 19.
0001 0011 19− 1111 1100 −3=========== ====1 0001 0111 23 —Anend-around borrow is produced.− 0000 0001 1 —Subtract the end-around borrow from the result.=========== ==== 0001 0110 22 —The correct result (19 − (−3) = 22).
Negative zero is the condition where all bits in a signed word are 1. This follows the ones' complement rules that a value is negative when the left-most bit is 1, and that a negative number is the bit complement of the number's magnitude. The value also behaves as zero when computing. Adding or subtracting negative zero to/from another value produces the original value.
Adding negative zero:
0001 0110 22+ 1111 1111 −0=========== ====1 0001 0101 21 Anend-around carry is produced.+ 0000 0001 1=========== ==== 0001 0110 22 The correct result (22 + (−0) = 22)
Subtracting negative zero:
0001 0110 22− 1111 1111 −0=========== ====1 0001 0111 23 Anend-around borrow is produced.− 0000 0001 1=========== ==== 0001 0110 22 The correct result (22 − (−0) = 22)
Negative zero is easily produced in a ones' complement adder. Simply add the positive and negative of the same magnitude.
0001 0110 22+ 1110 1001 −22=========== ==== 1111 1111 −0 Negative zero.
Although the math always produces the correct results, a side effect of negative zero is that software must test for negative zero.
The generation of negative zero becomes a non-issue if addition is achieved with a complementing subtractor. The first operand is passed to the subtract unmodified, the second operand is complemented, and the subtraction generates the correct result, avoiding negative zero. The previous example added 22 and −22 and produced −0.
0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22+ 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22=========== ==== but =========== ==== ; and =========== === but =========== === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0
"Corner cases" arise when one or both operands are zero and/or negative zero.
0001 0010 18 0001 0010 18− 0000 0000 0 − 1111 1111 −0=========== ==== =========== ==== 0001 0010 18 1 0001 0011 19 − 0000 0001 1 =========== ==== 0001 0010 18
Subtracting +0 is trivial (as shown above). If the second operand is negative zero it is inverted and the original value of the first operand is the result. Subtracting −0 is also trivial. The result can be only one of two cases. In case 1, operand 1 is −0 so the result is produced simply by subtracting 1 from 1 at every bit position. In case 2, the subtraction will generate a value that is 1 larger than operand 1 and anend-around borrow. Completing the borrow generates the same value as operand 1.
The next example shows what happens when both operands are plus or minus zero:
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0+ 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0=========== ==== =========== ==== =========== ==== =========== ==== 0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1 + 0000 0001 1 ================== 1111 1111 −0
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0− 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0=========== ==== =========== ==== =========== ==== =========== ====1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0− 0000 0001 1=========== ==== 0000 0000 0
This example shows that of the four possible conditions when adding only ±0, an adder will produce −0 in three of them. A complementing subtractor will produce −0 only when the first operand is −0 and the second is 0.
Detail-oriented readers and copy editors should notice the position of the apostrophe in terms like 'two's complement' and 'ones' complement': A two's complement number is complemented with respect to a single power of 2, while a ones' complement number is complemented with respect to a long sequence of 1s.
