The ones' complement of a
binary number
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
is the value obtained by inverting all the bits in the
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is
possessive of the plural "ones", not of a singular "one"'') refers to the fact that such an inverted value, if added to the original, would always produce an 'all ones' number (the term "
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
" refers to such pairs of mutually
additive inverse
In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...
numbers, here in respect to a non-0 base number). This mathematical operation is primarily of interest in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, where it has varying effects depending on how a specific computer represents numbers.
A ones' complement system or ones' 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 −(2
N−1−1) to 2
N−1−1 while
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
can express −2
N−1 to 2
N−1−1. It is one of three common representations for
negative integers in binary computers, along with
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
and
sign-magnitude
In computing, signed number representations are required to encode negative number
In mathematics, a negative number represents an opposite. In the real number system, a negative number is a number that is less than zero. Negative numbers are ...
.
The ones' complement binary
numeral system
A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using Numerical digit, digits or other symbols in a consistent manner.
The same s ...
is characterized by the
bit complement
In computer programming, a bitwise operation operates on a bit string, a bit array or a Binary numeral system, binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-l ...
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, including the
UNIVAC 1101,
CDC 160
The CDC 160 series was a series of minicomputers built by Control Data Corporation. The CDC 160 and CDC 160-A were 12-bit minicomputers built from 1960 to 1965; the CDC 160G was a 13-bit minicomputer, with an extended version of the CDC 160-A i ...
,
CDC 6600
The CDC 6600 was the flagship of the 6000 series of mainframe computer systems manufactured by Control Data Corporation. Generally considered to be the first successful supercomputer, it outperformed the industry's prior recordholder, the IBM ...
, the
LINC
The LINC (Laboratory INstrument Computer) is a 12-bit, 2048-word transistorized computer. The LINC is considered by some the first minicomputer and a forerunner to the personal computer. Originally named the "Linc", suggesting the project's o ...
, the
PDP-1
The PDP-1 (''Programmed Data Processor-1'') is the first computer in Digital Equipment Corporation's PDP series and was first produced in 1959. It is famous for being the computer most important in the creation of hacker culture at Massachusetts ...
, and the
UNIVAC 1107
The UNIVAC 1100/2200 series is a series of compatible 36-bit computer systems, beginning with the UNIVAC 1107 in 1962, initially made by Sperry Rand. The series continues to be supported today by Unisys Corporation as the ClearPath Dorado Series. ...
, used ones' complement arithmetic. Successors of the CDC 6600 continued to use ones' complement arithmetic until the late 1980s, and the descendants of the UNIVAC 1107 (the
UNIVAC 1100/2200 series
The UNIVAC 1100/2200 series is a series of compatible 36-bit computer systems, beginning with the UNIVAC 1107 in 1962, initially made by Sperry Rand. The series continues to be supported today by Unisys Corporation as the ClearPath Dorado Series. ...
) still do, but the majority of modern computers use
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
.
Number representation
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 the sign 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 — Note that both +0 and −0 return TRUE when tested for zero
1 0001 1110 — and FALSE when tested for non-zero.
2 0010 1101
3 0011 1100
4 0100 1011
5 0101 1010
6 0110 1001
7 0111 1000
Basics
Adding two values is straightforward. Simply align the values on the least 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
In computing, signed number representations are required to encode negative numbers in binary number systems.
In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regist ...
". 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
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sin ...
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 —An
end-around borrow
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sin ...
is produced.
− 0000 0001 1 —Subtract the end-around borrow from the result.
0001 0110 22 —The correct result (19 − (−3) = 22).
Negative zero
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 An
end-around carry
In computing, signed number representations are required to encode negative numbers in binary number systems.
In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regist ...
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 An
end-around borrow
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sin ...
is produced.
− 0000 0001 1
0001 0110 22 The correct result (22 − (−0) = 22)
Negative zero is easily produced in a 1's 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.
Avoiding 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 likewise, 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 1 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 an
end-around borrow
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sin ...
. 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 both operands are −0.
See also
{{Portal, Computer programming
*
Signed number representations
In computing, signed number representations are required to encode negative numbers in binary number systems.
In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regis ...
*
Two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
*
IEEE floating point
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in ...
References
*
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
: ''
The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
'', Volume 2: Seminumerical Algorithms, chapter 4.1
Binary arithmetic
Numeral systems
Unary operations
th:การแทนจำนวนที่มีเครื่องหมาย#1’s Complement System