Ones' complement

Last updated
Three-bit ones'-complement integers
BitsUnsigned valueOnes' complement
value
00000
00111
01022
01133
1004−3
1015−2
1106−1
1117−0
8-bit ones'-complement integers
BitsUnsigned
value
Ones'
complement
value
0000 00000 0 
0000 00011 1 
0000 00102 2 
0111 1110126 126 
0111 1111127 127 
1000 0000128 −127 
1000 0001129 −126 
1111 1101253 −2 
1111 1110254 −1 
1111 1111255 −0 

The ones' complement of a binary number is the value obtained by inverting (flipping) all the bits in the binary representation of the number. 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 mutually additive inverse numbers, here in respect to a non-0 base number). This mathematical operation is primarily of interest in computer science, where it has varying effects depending on how a specific computer represents numbers.

Contents

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 −(2N−1−1) to 2N−1−1 while two's complement can express −2N−1 to 2N−1−1. It is one of three common representations for negative integers in binary computers, along with two's complement and sign-magnitude.

The ones' complement binary numeral system is characterized by the bit 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, including the UNIVAC 1101, CDC 160, CDC 6600, the LINC, the PDP-1, and the UNIVAC 1107, 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) still do, but the majority of modern computers use two's complement.

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". 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    —An end-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

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 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 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.

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 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 an end-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.

See also

Related Research Articles

<span class="mw-page-title-main">Binary-coded decimal</span> System of digitally encoding numbers

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

<span class="mw-page-title-main">Arithmetic shift</span> Shift operator in computer programming

In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift. The two basic types are the arithmetic left shift and the arithmetic right shift. For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled in. Instead of being filled with all 0s, as in logical shift, when shifting to the right, the leftmost bit is replicated to fill in all the vacant positions.

Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ1 + φ0 = φ2. For instance, 11φ = 100φ.

A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method for represening numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A binary number may also refer to a rational number that has a finite representation in the binary numeral system, that is, the quotient of an integer by a power of two.

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands.

Two's complement is the most common method of representing signed integers on computers, and more generally, fixed point binary values. Two's complement uses the binary digit with the greatest value as the sign to indicate whether the binary number is positive or negative; when the most significant bit is 1 the number is signed as negative and when the most significant bit is 0 the number is signed as positive. As a result, non-negative numbers are represented as themselves: 6 is 0110, zero is 0000, and -6 is 1010. Note that while the number of binary bits is fixed throughout a computation it is otherwise arbitrary.

<span class="mw-page-title-main">Method of complements</span> Method of subtraction

In mathematics and computing, the method of complements is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm for addition throughout the whole range. For a given number of places half of the possible representations of numbers encode the positive numbers, the other half represents their respective additive inverses. The pairs of mutually additive inverse numbers are called complements. Thus subtraction of any number is implemented by adding its complement. Changing the sign of any number is encoded by generating its complement, which can be done by a very simple and efficient algorithm. This method was commonly used in mechanical calculators and is still used in modern computers. The generalized concept of the radix complement is also valuable in number theory, such as in Midy's theorem.

Excess-3, 3-excess or 10-excess-3 binary code, shifted binary or Stibitz code is a self-complementary binary-coded decimal (BCD) code and numeral system. It is a biased representation. Excess-3 code was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

PiHex was a distributed computing project organized by Colin Percival to calculate specific bits of π. 1,246 contributors used idle time slices on almost two thousand computers to make its calculations. The software used for the project made use of Bellard's formula, a faster version of the BBP formula.

In computing, signed number representations are required to encode negative numbers in binary number systems.

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.

In computer science, a scale factor is a number used as a multiplier to represent a number on a different scale, functioning similarly to an exponent in mathematics. A scale factor is used when a real-world set of numbers needs to be represented on a different scale in order to fit a specific number format. Although using a scale factor extends the range of representable values, it also decreases the precision, resulting in rounding error for certain calculations.

In computer processors, the overflow flag is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation, indicating that the signed two's-complement result would not fit in the number of bits used for the result. Some architectures may be configured to automatically generate an exception on an operation resulting in overflow.

A carry-save adder is a type of digital adder, used to efficiently compute the sum of three or more binary numbers. It differs from other digital adders in that it outputs two numbers, and the answer of the original summation can be achieved by adding these outputs together. A carry save adder is typically used in a binary multiplier, since a binary multiplier involves addition of more than two binary numbers after multiplication. A big adder implemented using this technique will usually be much faster than conventional addition of those numbers.

In computing, minifloats are floating-point values represented with very few bits. Predictably, they are not well suited for general-purpose numerical calculations. They are used for special purposes such as

In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency.

Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.

<span class="mw-page-title-main">Arithmetic logic unit</span> Combinational digital circuit

In computing, an arithmetic logic unit (ALU) is a combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numbers. It is a fundamental building block of many types of computing circuits, including the central processing unit (CPU) of computers, FPUs, and graphics processing units (GPUs).

In the C programming language, operations can be performed on a bit level using bitwise operators.

A half-carry flag is a condition flag bit in the status register of many CPU families, such as the Intel 8080, Zilog Z80, the x86, and the Atmel AVR series, among others. It indicates when a carry or borrow has been generated out of the least significant four bits of the accumulator register following the execution of an arithmetic instruction. It is primarily used in decimal (BCD) arithmetic instructions.

References

  1. Knuth, Donald E. "4.1. Positional Number Systems". The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). 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.