FACTOID # 15: A mere 0.8% of West Virginians were born in a foreign country.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Two's complement

The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2N for an N-bit two's complement). The binary or base-two numeral system is a system for representing numbers in which a radix of two is used; that is, each digit in a binary numeral may have either of two different values. ...


A two's-complement system or two's-complement arithmetic is a system in which negative numbers are represented by the two's complement of the absolute value;[1] this system is the most common method of representing signed integers on computers.[2] In such a system, a number is negated (converted from positive to negative or vice versa) by computing its two's complement. An N-bit two's-complement numeral system can represent every integer in the range −2N-1 to +2N-1-1. In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a − sign. ... This article is about the machine. ...


The two's-complement system is ubiquitous today because it doesn't require that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract, making it both simpler to implement and capable of easily handling higher precision arithmetic. Also, 0 has only a single representation, obviating the subtleties associated with negative zero, which exists in ones'-complement systems. This article is being considered for deletion in accordance with Wikipedias deletion policy. ... In mathematics, signed numbers in some arbitrary base is done in the usual way, by prefixing it with a - sign. ...


The method of complements can also be applied in base-10 arithmetic, using ten's complements by analogy with two's complements. In mathematics and computing, the method of complements is a technique used to subtract one number from another using only addition of positive numbers. ...

sign bit
0 1 1 1 1 1 1 1 = 127
0 0 0 0 0 0 1 0 = 2
0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 = 0
1 1 1 1 1 1 1 1 = −1
1 1 1 1 1 1 1 0 = −2
1 0 0 0 0 0 0 1 = −127
1 0 0 0 0 0 0 0 = −128
8-bit two's-complement integers

Contents

Explanation

Two's complement Decimal
0111 7
0110 6
0101 5
0100 4
0011 3
0010 2
0001 1
0000 0
1111 −1
1110 −2
1101 −3
1100 −4
1011 −5
1010 −6
1001 −7
1000 −8
Two's complement using a 4-bit integer

A system of two's-complement arithmetic represents negative integers by counting backwards and wrapping around.


The boundary between positive and negative numbers may theoretically be anywhere (as long as you check for it). For convenience, all numbers whose left-most bit is 1 are considered negative. The largest number representable this way with 4 bits is 0111 (7) and the smallest number is 1000 (-8).


To understand its usefulness for computers, consider the following. Adding 0011 (3) to 1111 (-1) results in the seemingly-incorrect 10010. However, ignoring the 5th bit (from the right), as we did when we counted backwards, gives us the actual answer, 0010 (2). Ignoring the 5th bit will work in all cases (although you have to do the aforementioned overflow checks when, eg, 0100 is added to 0100). Thus, a circuit designed for addition can handle negative operands without also including a circuit capable of subtraction (and a circuit which switches between the two based on the sign). Moreover, by this method an addition circuit can even perform subtractions if you convert the necessary operand into the "counting-backwards" form. The procedure for doing so is called taking the two's complement (which, admittedly, requires either an extra cycle or its own adder circuit). Lastly, a very important reason for utilizing two's-complement representation is that it would be considerably more complex to create a subtraction circuit that takes 0001 − 0010 and returns 1001 (ie −001) than it is to make one that returns 1111. (Doing the former means you have to check the sign, then check if there will be a sign reversal, then possibly rearrange the numbers, and finally subtract. Doing the latter means you simply subtract, pretending there's an extra leftmost bit hiding somewhere.)


In an n-bit binary number, the most significant bit is usually the 2n−1's place. But in the two's-complement representation, its place value is negated; it becomes the −2n−1s place and is called the sign bit. The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... The binary representation of decimal 149, with the MSB highlighted. ... In computer science the sign bit is the bit in a computer numbering format which indicates the sign of the number. ...


If the sign bit is 0, the value is positive; if it is 1, the value is negative. To negate a two's-complement number, invert all the bits (bitwise NOT) then add 1 to the result. In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...


If all bits are 1, the value is −1. If the sign bit is 1 but the rest of the bits are 0, the value is the most negative number, −2n−1 for an n-bit number. The absolute value of the most negative number cannot be represented with the same number of bits, because it is exactly 1 greater than the most positive number that two's complement can represent in the given number of bits.


A two's-complement 8-bit binary numeral can represent every integer in the range −128 to +127. If the sign bit is 0, then the largest value that can be stored in the remaining seven bits is 27 − 1, or 127.


Using two's complement to represent negative numbers allows only one representation of zero, and to have effective addition and subtraction while still having the most significant bit as the sign bit.


Calculating two's complement

In finding the two's complement of a binary number, the bits are inverted, or "flipped", by using the bitwise NOT operation; the value of 1 is then added to the resulting value. Bit overflow is ignored, which is the normal case with zero. This article is about the unit of information. ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...


For example, beginning with the signed 8-bit binary representation of the decimal value 5, using subscripts to indicate the base of a representation needed to interpret its value:

000001012 = 510

The most significant bit is 0, so the pattern represents a non-negative (positive) value. To convert to −5 in two's-complement notation, the bits are inverted; 0 becomes 1, and 1 becomes 0:

11111010

At this point, the numeral is the ones' complement of the decimal value 5. To obtain the two's complement, 1 is added to the result, giving: In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a − sign. ...

111110112 = − 510

The result is a signed binary number representing the decimal value −5 in two's-complement form. The most significant bit is 1, so the value represented is negative.


The two's complement of a negative number is the corresponding positive value. For example, inverting the bits of −5 (above) gives:

00000100

And adding one gives the final value:

000001012 = 510

The value of a two's-complement binary number can be calculated by adding up the power-of-two weights of the "one" bits, but with a negative weight for the most significant (sign) bit; for example:

111110112 = − 128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = ( − 27 + 26 + ...) = − 5

Note that the two's complement of zero is zero: inverting gives all ones, and adding one changes the ones back to zeros (the overflow is ignored). Also the two's complement of the most negative number representable (e.g. a one as the sign bit and all other bits zero) is itself. Hence, there appears to be an 'extra' negative number.


A more formal definition of a two's-complement negative number (denoted by N* in this example) is derived from the equation N * = 2nN, where N is the corresponding positive number and n is the number of bits in the representation.


For example, to find the 4 bit representation of -5:

N = 510 therefore N = 01012
n = 4

Hence:

N * = 2nN = 24 − 510 = 100002 − 01012 = 10112

The calculation can be done entirely in base 10, converting to base 2 at the end:

N * = 2nN = 24 − 5 = 1110 = 10112

Faster conversion

A shortcut to convert a binary number into its two's complement is to start at the least significant bit (LSB), and copy all the zeros (working from LSB to most significant bit) until the first 1 is reached; then copy that 1, and flip all the remaining bits. This shortcut allows a person to convert a number to its two's complement without first forming its ones' complement. For example: the two's complement of "0011 1100" is "1100 0100", where the underlined digits are unchanged by the copying operation.


In computer circuitry, this method is no faster than the "complement and add one" method; both methods require working sequentially from right to left, propagating logic changes. The method of complementing and adding one can be sped up by a standard carry look-ahead adder circuit; the alternative method can be sped up by a similar logic transformation. A Carry Look-Ahead Adder is one type of adder used in digital logic. ...


Sign extension

Decimal 4-bit two's complement 8-bit two's complement
5 0101 0000 0101
-3 1101 1111 1101
sign-bit repetition in 4 and 8-bit integers

When turning a two's-complement number with a certain number of bits into one with more bits (e.g., when copying from a 1 byte variable to a two byte variable), the sign bit must be repeated in all the extra bits and lower bits.


Some processors have instructions to do this in a single instruction. On other processors a conditional must be used followed with code to set the relevant bits or bytes.


Similarly, when a two's-complement number is shifted to the right, the sign bit must be maintained. However when shifted to the left, a 0 is shifted in. These rules preserve the common semantics that left shifts multiply the number by two and right shifts divide the number by two.


Both shifting and doubling the precision are important for some multiplication algorithms. Note that unlike addition and subtraction, precision extension and right shifting are done differently for signed vs unsigned numbers.


The most negative number

With only one exception, when we start with any number in two's-complement representation, if we flip all the bits and add 1, we get the two's-complement representation of the negative of that number. Negative 12 becomes positive 12, positive 5 becomes negative 5, zero becomes zero, etc.

−128 1000 0000
invert bits 0111 1111
add one 1000 0000
The two's complement of -128 results in the same 8-bit binary number.

The two's complement of the minimum number in the range will not have the desired effect of negating the number. For example, the two's complement of −128 in an 8-bit system results in the same binary number. This is because a positive value of 128 cannot be represented with an 8-bit signed binary numeral. Note that this is detected as an overflow condition since there was a carry into but not out of the sign bit. This can lead to unexpected bugs in that a naive implementation of absolute value could return a negative number. In mathematics, the absolute value (or modulus[1]) of a real number is its numerical value without regard to its sign. ...


Although the number is an exception, it is a valid number in regular two's complement systems. All arithmetic operations work with it both as an operand and (unless there was an overflow) a result.


Why it works

The 2n possible values of n bits actually form a ring of equivalence classes, namely the integers modulo 2n, Z/(2n)Z. Each class represents a set {j + k2n | k is an integer} for some integer j, 0 ≤ j ≤ 2n − 1. There are 2n such sets, and addition and multiplication are well-defined on them. In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, the term well-defined is used to specify that a certain concept (a function, a property, a relation, etc. ...


If the classes are taken to represent the numbers 0 to 2n − 1, and overflow ignored, then these are the unsigned integers. But each of these numbers is equivalent to itself minus 2n. So the classes could be understood to represent −2n−1 to 2n−1 − 1, by subtracting 2n from half of them (specifically [2n−1, 2n−1−1]).


For example, with eight bits, the unsigned bytes are 0 to 255. Subtracting 256 from the top half (128 to 255) yields the signed bytes −128 to 127.


The relationship to two's complement is realised by noting that 256 = 255 + 1, and (255 − x) is the ones' complement of x. In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a − sign. ...

Decimal Two's complement
127 0111 1111
64 0100 0000
1 0000 0001
0 0000 0000
-1 1111 1111
-64 1100 0000
-127 1000 0001
-128 1000 0000
Some special numbers to note

Example


 −95 modulo 256 is equivalent to 161 since

−95 + 256
= −95 + 255 + 1
= 255 − 95 + 1
= 160 + 1
= 161
 1111 1111 255 − 0101 1111 − 95 =========== ===== 1010 0000 (ones' complement) 160 + 1 + 1 =========== ===== 1010 0001 (two's complement) 161 

Arithmetic operations

Addition

Adding two's-complement numbers requires no special processing if the operands have opposite signs: the sign of the result is determined automatically. For example, adding 15 and -5:

 11111 111 (carry) 0000 1111 (15) + 1111 1011 (-5) ================== 0000 1010 (10) 

This process depends upon restricting to 8 bits of precision; a carry to the (nonexistent) 9th most significant bit is ignored, resulting in the arithmetically correct result of 10.


The last two bits of the carry row (reading right-to-left) contain vital information: whether the calculation resulted in an arithmetic overflow, a number too large for the binary system to represent (in this case greater than 8 bits). An overflow condition exists when a carry (an extra 1) is generated into but not out of the far left sign bit, or out of but not into the sign bit. As mentioned above, the sign bit is the leftmost bit of the result. The term carry may refer to: A violation whilst dribbling in the game of basketball. ... The term arithmetic overflow or simply overflow has the following meanings. ...


In other terms, if the last two carry bits (the ones on the far left of the top row in these examples) are both 1's or both 0's, the result is valid; if the last two carry bits are "1 0" or "0 1", a sign overflow has occurred. Conveniently, an XOR operation on these two bits can quickly determine if an overflow condition exists. As an example, consider the 4-bit addition of 7 and 3: Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...

 0111 (carry) 0111 (7) + 0011 (3) ============= 1010 (−6) invalid! 

In this case, the far left two (MSB) carry bits are "01", which means there was a two's-complement addition overflow. That is, ten is outside the permitted range of −8 to 7.


In general, any two n-bit numbers may be added without overflow, by first sign-extending both of them to n+1 bits, and then adding as above. The n+1 bit result is large enough to represent any possible sum (e.g. 5 bits can represent values in the range −16 to 15) so overflow will never occur. It is then possible, if desired, to 'truncate' the result back to n bits; the value is preserved if and only if the discarded bit is a proper sign extension of the retained result bits. This provides another method of detecting overflow — which is equivalent to the method of comparing the carry bits — but which may be easier to implement in some situations, since it does not require access to the internals of the addition.


Subtraction

Computers usually use the method of complements to implement subtraction. But although using complements for subtraction is related to using complements for representing signed numbers, they are independent; direct subtraction works with two's-complement numbers as well. Like addition, the advantage of using two's complement is the elimination of examining the signs of the operands to determine if addition or subtraction is needed. For example, subtracting -5 from 15 is really adding 5 to 15, but this is hidden by the two's-complement representation: In mathematics and computing, the method of complements is a technique used to subtract one number from another using only addition of positive numbers. ...

 11110 000 (borrow) 0000 1111 (15) − 1111 1011 (−5) =========== 0001 0100 (20) 

Overflow is detected the same way as for addition, by examining the two leftmost (most significant) bits of the borrows; overflow has occurred if they are different.


Another example is a subtraction operation where the result is negative: 15 − 35 = −20:

 11100 000 (borrow) 0000 1111 (15) − 0010 0011 (35) =========== 1110 1100 (−20) 

As for addition, overflow in subtraction may be avoided (or detected after the operation) by first sign-extending both inputs by an extra bit.


Multiplication

The product of two n-bit numbers can potentially have 2n bits. If the precision of the two two's-complement operands is doubled before the multiplication, direct multiplication (discarding any excess bits beyond that precision) will provide the correct result. For example, take 5 × −6 = −30. First, the precision is extended from 4 bits to 8. Then the numbers are multiplied, discarding the bits beyond 8 (shown by 'x'):

 00000101 (5) × 11111010 (−6) ========= 0 101 0 101 101 101 x01 xx1 ========= xx11100010 (−30) 

This is very inefficient; by doubling the precision ahead of time, all additions must be double-precision and at least twice as many partial products are needed than for the more efficient algorithms actually implemented in computers. Some multiplication algorithms are designed for two's complement, notably Booth's multiplication algorithm. Methods for multiplying sign-magnitude numbers don't work with two's-complement numbers without adaptation. There isn't usually a problem when the multiplicand (the one being repeatedly added to form the product) is negative; the issue is setting the initial bits of the product correctly when the multiplier is negative. Two methods for adapting algorithms to handle two's-complement numbers are common: Booths multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in twos complement notation. ...

  • First check to see if the multiplier is negative. If so, negate (i.e., take the two's complement of) both operands before multiplying. The multiplier will then be positive so the algorithm will work. And since both operands are negated, the result will still have the correct sign.
  • Subtract the partial product resulting from the sign bit instead of adding it like the other partial products.

As an example of the second method, take the common add-and-shift algorithm for multiplication. Instead of shifting partial products to the left as is done with pencil and paper, the accumulated product is shifted right, into a second register that will eventually hold the least significant half of the product. Since the least significant bits are not changed once they are calculated, the additions can be single precision, accumulating in the register that will eventually hold the most significant half of the product. In the following example, again multiplying 5 by −6, the two registers are separated by "|": The binary representation of decimal 149, with the lsb highlighted. ...

 0101 (5) ×1010 (−6) ====|==== 0000|0000 (first partial product (rightmost bit is 0)) 0000|0000 (shift right) 0101|0000 (add second partial product (next bit is 1)) 0010|1000 (shift right) 0010|1000 (add third partial product: 0 so no change) 0001|0100 (shift right) 1100|0100 (subtract last partial product since it's from sign bit) 1110|0010 (shift right, preserving sign bit, giving the final answer, −30) 

Two's complement and universal algebra

In the classic "HAKMEM" published by the MIT AI Lab in 1972, Bill Gosper noted that whether or not a machine's internal representation was two's-complement could be determined by summing the successive powers of two. In a flight of fancy, he noted that the result of doing this algebraically indicated that "algebra is run on a machine (the universe) which is twos-complement." [3] HAKMEM, alternatively known as AI Memo 239, is a 1972 memo (technical report) of the MIT AI Lab that describes a wide variety of hacks, primarily useful and clever algorithms for mathematical computation. ... ... R. William Gosper, Jr. ...


Gosper's end conclusion is not necessarily meant to be taken seriously, and it is akin to a mathematical joke. The critical step is "...110 = ...111 − 1", i.e., "2X = X − 1". This presupposes a method by which an infinite string of 1's is considered a number, which requires an extension of the finite place-value concepts in elementary arithmetic. It is meaningful either as part of a two's-complement notation for all integers, as a typical 2-adic number, or even as one of the generalized sums defined for the divergent series of real numbers 1 + 2 + 4 + 8 + · · ·.[4] This equation uses mathematical symbols to write Sex is fun. A mathematical joke is a form of humor which relies on aspects of mathematics or a stereotype of mathematicians to derive humor. ... In mathematics, the p-adic number systems were first described by Kurt Hensel in 1897. ... In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a limit. ... In mathematics, 1 + 2 + 4 + 8 + · · · is the infinite series whose terms are the successive powers of two. ...


Potential ambiguities in usage

One should be cautious when using the term two's complement, as it can mean either a number format or a mathematical operator. For example 0111 represents 7 in two's-complement notation, but 1001 is the two's complement of 7. In code notation or conversation the statement "convert x to two's complement" may be ambiguous, as it could describe either the change in representation of x to two's-complement notation from some other format, or else (if the writer really meant "convert x to its two's complement") the calculation of the negated value of x.


See also

Several algorithms exist to perform division in digital designs. ... In mathematics, negative numbers in any base are represented in the usual way, by prefixing them with a − sign. ...

References

  1. ^ David J. Lilja and Sachin S. Sapatnekar, Designing Digital Computer Systems with Verilog, Cambridge University Press, 2005 online
  2. ^ E.g. "Signed integers are two’s complement binary values that can be used to represent both positive and negative integer values.", Section 4.2.1 in Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006
  3. ^ http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154
  4. ^ For the summation of 1 + 2 + 4 + 8 + · · · without recourse to the 2-adic metric, see Hardy, G.H. (1949). Divergent Series. Clarendon Press. LCC QA295 .H29 1967.  (pp.7-10)
  • Ivan Flores, The Logic of Computer Arithmetic, Prentice-Hall (1963)
  • Israel Koren, Computer Arithmetic Algorithms, A.K. Peters (2002), ISBN 1-56881-160-8
Godfrey Harold Hardy FRS (February 7, 1877 Cranleigh, Surrey, England [1] – December 1, 1947 Cambridge, Cambridgeshire, England [2]) was a prominent English mathematician, known for his achievements in number theory and mathematical analysis. ... Library of Congress reading room The Library of Congress Classification (LCC) is a system of library classification developed by the Library of Congress. ...

  Results from FactBites:
 
Floating point accumulator circuit - Patent 4825400 (0 words)
The exponent comparison and twos' complementing section is used to determine which mantissa--that of the input floating point number, or that of the accumulated number--will have to be shifted in order to align the binary points so that addition in the accumulation section may proceed.
A register at the end of this section stores the twos' complement mantissa, a shift code, some control signals to indicate which of the mantissas is the smaller (and therefore to be shifted), and the largest exponent (which is also fed back to this section for the next exponent comparison).
Which of the two signs is selected is determined by the Bypass signal, which controls the action of a 1-bit multiplexer 53 whose two inputs are the New Sign signal generated in the accumulation section and the original input sign.
6502.org Tutorials: The Overflow (V) Flag Explained (0 words)
The carry flag has two purposes: first, it allows the 6502 to (easily) extend additions and subtractions beyond 8-bit numbers, and second, it indicates when the result is outside the range of 0 to 255.
So the range of an 8-bit twos complement number is -128 to 127, where -128 to -1 are represented by $80 to $FF, and 0 to 127 are resprented by $00 to $7F.
First, the range 0 to 127 (the overlap of the unsigned and twos complement ranges) is represented by $00 to $7F, regardless of whether it is unsigned or twos complement.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m