Ones' complement

Last updated
8-bit ones'-complement integers
BitsUnsigned
value
Ones'
complement
value
0111 1111127 127 
0111 1110126 126 
0000 00102 2 
0000 00011 1 
0000 00000 0 
1111 1111255 −0 
1111 1110254 −1 
1111 1101253 −2 
1000 0001129 −126 
1000 0000128 −127 

The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0s for 1s and vice versa). The ones' complement of the number then behaves like the negative of the original number in some arithmetic operations. To within a constant (of −1), the ones' complement behaves like the negative of the original number with binary addition. However, unlike two's complement, these numbers have not seen widespread use because of issues such as the offset of −1, that negating zero results in a distinct negative zero bit pattern, less simplicity with arithmetic borrowing, etc.

Binary number system that represents numeric values using two symbols; 0 and 1

In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically "0" (zero) and "1" (one).

Two's complement is a mathematical operation on binary numbers, and is an example of a radix complement. It is used in computing as a method of signed number representation.

In elementary arithmetic, a carry is a digit that is transferred from one column of digits to another column of more significant digits. It is part of the standard algorithm to add numbers together by starting with the rightmost digits and working to the left. For example, when 6 and 7 are added to make 13, the "3" is written to the same column and the "1" is carried to the left. When used in subtraction the operation is called a borrow.

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.

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.

Numeral system Writing system for expressing numbers

A numeral system is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner.

Many early computers, including the CDC 6600, the LINC, the PDP-1, and the UNIVAC 1107, used ones' complement notation. Successors of the CDC 6600 continued to use ones' complement 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.

CDC 6600 computer

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 7030 Stretch, by a factor of three. With performance of up to three megaFLOPS, the CDC 6600 was the world's fastest computer from 1964 to 1969, when it relinquished that status to its successor, the CDC 7600.

LINC Minicomputer

The LINC 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 origins at MIT's Lincoln Laboratory, it was renamed LINC after the project moved from the Lincoln Laboratory. The LINC was designed by Wesley A. Clark and Charles Molnar.

PDP-1

The PDP-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 MIT, BBN and elsewhere. The PDP-1 is the original hardware for playing history's first game on a minicomputer, Steve Russell's Spacewar!

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

Related Research Articles

Binary-coded decimal class of binary encodings of decimal numbers where each decimal digit is represented by a fixed number of bits, usually four or eight. Special bit patterns are sometimes used for a sign or for other indications (e.g., error or overflow)

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

Arithmetic shift

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

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 = φ2. For instance, 11φ = 100φ.

In digital computer programming, a bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. It is a fast and simple action, directly supported by the processor, and is used to manipulate values for comparisons and calculations.

Method of complements

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 (hardware) 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 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 pi. 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.

IBM System/360 computers, and subsequent machines based on that architecture (mainframes), support a hexadecimal floating-point format (HFP).

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.

Sign extension is the operation, in computer arithmetic, of increasing the number of bits of a binary number while preserving the number's sign (positive/negative) and value. This is done by appending digits to the most significant side of the number, following a procedure dependent on the particular signed number representation used.

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 operation. Some architectures may be configured to automatically generate an exception on an operation resulting in overflow.

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, most often in computer graphics, where iterations are small and precision has aesthetic effects. Additionally, they are frequently encountered as a pedagogical tool in computer-science courses to demonstrate the properties and structures of floating-point arithmetic and IEEE 754 numbers.

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.

The serial binary adder or bit-serial adder is a digital circuit that performs binary addition bit by bit. The serial full adder has three single-bit inputs for the numbers to be added and the carry in. There are two single-bit outputs for the sum and carry out. The carry-in signal is the previously calculated carry-out signal. The addition is performed by adding each bit, lowest to highest, one per clock cycle.

Arithmetic logic unit digital circuits

An arithmetic logic unit (ALU) is a combinational digital electronic 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. An ALU 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). A single CPU, FPU or GPU may contain multiple ALUs.

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