Two's complement
Two's complement is a method for representing signed integers in binary form, widely used in digital computing to encode both positive and negative numbers within a fixed number of bits, where the most significant bit serves as the sign bit and negative values are obtained by inverting all bits of the corresponding positive value and adding one.[1] For an n-bit system, this representation allows values ranging from -2n-1 to 2n-1 - 1, providing a single unique encoding for zero and enabling efficient arithmetic operations without separate handling for signs.[2][3] The process of computing the two's complement for a negative number involves writing the absolute value in binary, inverting (or "complementing") all its bits, and then adding 1 to the result, which effectively shifts the numerical range to include negatives while preserving binary addition rules.[1] For example, in an 8-bit system, the positive integer 5 is represented as00000101; its two's complement (for -5) is obtained by inverting to 11111010 and adding 1, yielding 11111011.[2] This approach contrasts with earlier methods like signed magnitude or one's complement, which suffered from dual representations of zero and required more complex hardware for arithmetic.[4]
Historically, two's complement was first proposed by John von Neumann in his 1945 First Draft of a Report on the EDVAC, as a way to simplify subtraction in electronic stored-program computers by treating it as addition of the complement.[5] It gained widespread adoption with systems like IBM's System/360 in 1964, becoming the de facto standard for signed integer representation in modern processors due to its hardware efficiency.[5] Key advantages include the ability to perform addition and subtraction using the same binary adder circuitry, automatic handling of overflow detection via sign bit comparison, and streamlined design of arithmetic logic units (ALUs) in computer architecture.[6][4] Today, it underpins integer operations in virtually all general-purpose computers, facilitating reliable computation across programming languages and embedded systems.[3]
Fundamentals
Definition and Motivation
Two's complement is a method for representing signed integers in binary notation, widely used in computer systems to encode both positive and negative numbers using a fixed number of bits. In this system, the most significant bit (MSB) serves as the sign bit, where a value of 0 indicates a non-negative number and 1 indicates a negative number. Positive integers are represented in the standard binary form, while negative integers are derived from their positive counterparts by inverting all bits (changing 0s to 1s and 1s to 0s) and then adding 1 to the result. This approach builds upon the foundation of unsigned binary representation, where all bits contribute to the magnitude without a dedicated sign bit.[1][7] For example, in a 4-bit system, the positive integer 3 is represented as 0011. To obtain the two's complement representation of -3, first invert the bits of 0011 to get 1100, then add 1, resulting in 1101. Interpreting 1101 as a two's complement number yields -3, as the MSB is 1 (negative) and the value is calculated accordingly. This binary encoding allows for a seamless integration of signed values into hardware arithmetic operations.[1][8] The motivation for adopting two's complement stems from its ability to resolve key limitations in earlier signed integer representations, such as sign-magnitude and one's complement systems. Sign-magnitude uses a dedicated sign bit followed by the binary magnitude, leading to redundant representations of zero (+0 as 0000 and -0 as 1000 in 4 bits), which complicates comparisons and arithmetic. One's complement, which simply inverts bits for negatives, also produces two zeros (+0 as 0000 and -0 as 1111) and requires an "end-around carry" in addition to handle the dual zeros correctly. In contrast, two's complement provides a unique representation for zero (all bits 0) and enables simplified arithmetic, where addition and subtraction can use the same binary adder circuitry without special handling for signs or carries, making it more efficient for computer hardware implementation.[8][7][1]Representation Procedure
The two's complement representation of a negative integer -x in an n-bit system is obtained by starting with the binary representation of the positive value x and applying a two-step process: first, invert all bits of x to form its ones' complement, then add 1 to the least significant bit of that result.[1] This method ensures that the representation aligns with modular arithmetic properties for efficient arithmetic operations.[9] Mathematically, the two's complement of -x is given by the formula -x \equiv 2^n - x \pmod{2^n}, where n is the number of bits, effectively subtracting x from the modulus $2^n.[9] For positive numbers, the representation remains the standard unsigned binary form, padded with leading zeros if necessary to fit n bits.[1] The value zero is represented as all zeros (000...0) in n bits, unchanged from its unsigned form.[9] To illustrate the bit-level walkthrough for an 8-bit system, consider computing the representation of -5, where the positive 5 is 00000101 in binary:- Invert all bits: 11111010 (ones' complement of 5).
- Add 1 to the least significant bit: 11111010 + 1 = 11111011.
Historical Development
The concept of two's complement representation for signed binary integers was first formally proposed by John von Neumann in his 1945 "First Draft of a Report on the EDVAC," where negative numbers were specified to be stored in two's complement form within 31-bit signed binary integers, enabling efficient arithmetic operations in the planned electronic stored-program computer.[10] This proposal marked a shift toward binary fixed-point arithmetic, contrasting with the decimal representations prevalent in earlier machines like ENIAC, by leveraging the mathematical properties of complements to simplify subtraction as addition.[10] The first electronic implementation of two's complement appeared in the EDSAC computer, completed in 1949 at the University of Cambridge and directly inspired by von Neumann's EDVAC draft, which used 17-bit or 35-bit two's complement binary numbers for internal arithmetic.[11] In contrast, contemporary machines like the UNIVAC I (delivered in 1951) relied on binary-coded decimal with excess-three notation for signed values, while later UNIVAC 1100 series systems adopted ones' complement for binary integers, highlighting the initial diversity in sign representation schemes during the early 1950s.[12] This period saw two's complement gain traction in binary architectures due to its elimination of dual zeros and streamlined hardware for addition and subtraction. Widespread adoption occurred with the IBM System/360 family, announced in 1964, which standardized two's complement for 16-bit halfwords and 32-bit fullwords across its integer operations, representing negative numbers by inverting bits and adding one to the least significant bit.[13] As IBM dominated the mainframe market, this choice propelled two's complement into subsequent architectures, including the binary implementations that evolved into modern instruction sets like x86 and ARM, solidifying its role by the 1970s.[13]Conversion Techniques
To Two's Complement
To convert a positive integer to its two's complement representation, the binary form of the number is used directly, with leading zeros padded to the desired bit width to indicate positivity.[1] For a negative integer, the process involves first representing the absolute value in binary, then inverting all bits (replacing 0s with 1s and 1s with 0s) to obtain the one's complement, and finally adding 1 to that result; any carry-out from the most significant bit is discarded.[3] This method ensures the representation aligns with the two's complement system's arithmetic properties.[1] An alternative approach to computing the two's complement of a positive integer x in n bits is to calculate $2^n - x using unsigned binary subtraction, which yields the same result as the invert-and-add method.[9] This subtraction-based technique highlights the modular arithmetic foundation of two's complement, where negative values wrap around from the modulus $2^n.[14] To convert from one's complement representation to two's complement, examine the most significant bit (MSB): if 0 (positive or zero), the bit pattern remains unchanged, as representations are identical; if 1 (negative), add 1 to the bit pattern, discarding any carry-out. This adjustment corrects the dual-zero issue, mapping all-ones (-0 in one's complement) to all-zeros (+0 in two's complement).[1] For example, in a 4-bit one's complement system, -2 is represented as 1101 (the bitwise inversion of positive 2, which is 0010). Adding 1 gives 1110, the two's complement representation of -2. For +2 (0010), no addition is performed, retaining 0010. For manual calculation without full inversion, the least significant bit (LSB) to most significant bit (MSB) method can be used to find the two's complement of a positive binary number: starting from the LSB, copy bits unchanged until reaching the first 1 in the original number (including that 1), then invert all remaining higher bits.[15] This technique efficiently simulates the add-1 carry propagation from the LSB, avoiding explicit addition in simple cases.[2] For instance, applying this to 4-bit positive 2 (0010) copies the trailing 0, then the first 1, and inverts the leading 0 to 1, yielding 1110 for -2.[15]From Two's Complement
To convert a binary number represented in two's complement to its signed decimal equivalent, first examine the most significant bit (MSB), which serves as the sign bit: a value of 0 indicates a positive number or zero, while 1 indicates a negative number.[16][17] For positive numbers (MSB = 0), perform a standard binary-to-decimal conversion by summing the positional weights of the bits set to 1, where the rightmost bit has weight $2^0 and each subsequent bit doubles in weight up to the leftmost.[16] For negative numbers (MSB = 1), compute the value using the formula \text{Value} = -(2^n - U), where n is the number of bits and U is the unsigned decimal interpretation of the binary number; alternatively, invert all bits to obtain the one's complement, add 1 to get the magnitude, and apply a negative sign.[17][3] Consider a 4-bit example: the binary 1101 has MSB = 1, so it is negative. Interpreting 1101 as unsigned gives U = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 13; thus, \text{Value} = -(2^4 - 13) = -3. Alternatively, invert to 0010 (decimal 2), add 1 to get 0011 (decimal 3), yielding -3.[17][3] In two's complement, the all-zero bit pattern represents +0, and there is no distinct representation for -0, as inverting and adding 1 to the all-ones pattern (which is -1) produces all zeros.[16][17]Sign Extension
Sign extension is a technique used to increase the bit width of a two's complement integer while preserving its signed numerical value. For positive numbers, which have a most significant bit (MSB) of 0, the extension involves padding leading zeros on the left. For negative numbers, with an MSB of 1, leading ones are added by replicating the sign bit until the desired width is achieved. This process ensures that the representation remains consistent with the two's complement system across different bit lengths.[18][19] Consider an example of extending an 8-bit two's complement representation of -5, which is11111011, to 16 bits. By replicating the sign bit (1), the extended form becomes 11111111 11111011, maintaining the value of -5. Similarly, the 8-bit positive value +5 (00000101) extends to 00000000 00000101 by padding zeros. These operations demonstrate how sign extension avoids altering the integer's magnitude or sign.[18][19]
The mathematical basis for sign extension lies in the two's complement value formula, which ensures equivalence between the original and extended representations. For an N-bit number a = a_{N-1} a_{N-2} \dots a_0 with value X = -a_{N-1} \cdot 2^{N-1} + \sum_{i=0}^{N-2} a_i \cdot 2^i, extending to M bits (M > N) by setting b_i = a_{N-1} for i = N to M-1 yields:
X = -a_{N-1} \cdot 2^{M-1} + \sum_{i=N-1}^{M-2} a_{N-1} \cdot 2^i + \sum_{i=0}^{N-2} a_i \cdot 2^i.
The middle sum simplifies to a_{N-1} \cdot (2^{M-1} - 2^{N-1}), canceling with the first term to recover the original X, thus preserving the value modulo $2^M. This equivalence holds because the padded bits effectively add a multiple of $2^N that aligns with the modular arithmetic of two's complement.[20]
In practice, sign extension is crucial in compiler design for integer promotion, such as converting a narrower signed type like int (typically 32 bits) to a longer type like long (64 bits), ensuring operations on mixed-width values do not change the semantic meaning. For instance, the C programming language employs sign extension during promotions of signed integers to wider types, preventing unintended value shifts in arithmetic expressions. This is essential for maintaining correctness in variable-length computations, such as in assembly code generation or hardware instructions that handle different register sizes.[21][22]
A common pitfall arises when confusing sign extension with zero extension used for unsigned integers, where leading zeros are always padded regardless of the MSB, which would incorrectly alter the value of negative numbers if applied to signed representations. This distinction is vital in systems programming to avoid sign mismatches during type conversions.[19][23]
Key Properties
Range and Most Negative Number
In an n-bit two's complement system, the representable integers range from -2^{n-1} to $2^{n-1} - 1.[24][4] This asymmetric range arises because the sign bit allocates $2^{n-1} possible values to negative numbers (including the most negative) and $2^{n-1} - 1 to non-negative numbers (from 0 to the maximum positive), as zero occupies one slot in the non-negative portion.[6][25] For example, in an 8-bit system, the range spans from -128 to +127.[26] The most negative value, -2^{n-1}, is represented by the bit pattern $1followed byn-1zeros (e.g., 10000000 in [binary](/page/Binary) forn=8).[](https://dc.etsu.edu/cgi/viewcontent.cgi?filename=0&article=1019&context=computer-organization-design-oer&type=additional) There is no corresponding positive value of +2^{n-1}because the leading [sign bit](/page/Sign_bit) must be 0 for positive numbers, limiting the maximum magnitude for positives to2^{n-1} - 1$.[6] This asymmetry can lead to subtle issues in arithmetic operations, particularly with overflow detection methods that rely on sign changes. For instance, adding two values of -2^{n-2} (e.g., -64 in 8 bits) yields exactly -2^{n-1} (e.g., -128), which remains within the representable range but involves wraparound in the underlying modular arithmetic; standard sign-based overflow detection does not flag this as an error since the result retains a negative sign.[27][28]Theoretical Justification
The two's complement representation of signed integers leverages modular arithmetic modulo $2^n, where n is the number of bits, to unify signed and unsigned operations on the same hardware. In this system, the value of a negative number -x (where $0 < x < 2^{n-1}) is encoded as $2^n - x \pmod{2^n}, ensuring that the bit patterns correspond to equivalence classes in the integers modulo $2^n.[29] This equivalence means that arithmetic operations performed modulo $2^n yield correct results under the two's complement interpretation, as the representation preserves the additive structure of the integers within the bounded range.[30] A key property is the negation rule, where the two's complement of a positive x is $2^n - x, so adding a number to its negation gives x + (2^n - x) = 2^n \equiv 0 \pmod{2^n}. This holds because the hardware addition discards any carry out beyond n bits, effectively computing the sum modulo $2^n. For addition of two signed numbers a and b, the result (a + b) \mod 2^n matches the signed interpretation provided the result fits within the representable range, as the bit-level addition is identical to unsigned addition followed by modular reduction.[29] To illustrate, in 4 bits, +3 is $0011_2 and -3 is $1101_2 (since $16 - 3 = 13 = 1101_2); their sum is $0011_2 + 1101_2 = 10000_2, which modulo $16 is $0000_2 (0), with the carry out ignored.[30] This framework aligns with ring theory, where the n-bit two's complement integers form the ring \mathbb{Z}/2^n\mathbb{Z} under addition and multiplication modulo $2^n, with the sign bit enabling a consistent signed interpretation across operations. Sign extension maintains this ring structure by padding with the sign bit, preserving congruence modulo $2^n.[31]Ones' Complement Relation
In ones' complement representation, the negative of a positive integer is obtained by inverting all bits of its binary form, without adding 1.[32] This method results in two distinct representations for zero: the positive zero (all bits 0) and the negative zero (all bits 1), which complicates zero detection and equality comparisons in hardware.[33] The relationship between ones' complement and two's complement is direct: for negative numbers, the two's complement representation is the ones' complement plus 1.[1] Conversely, to derive the ones' complement from the two's complement of a number, perform a bitwise XOR with $2^n - 1 (where n is the bit width), equivalent to inverting all bits.[32] For example, in 4 bits, the positive value 3 is0011; its ones' complement (representing -3) is 1100, and adding 1 yields the two's complement 1101 for -3.[1]
Ones' complement has notable drawbacks, including the dual zeros that necessitate special handling in arithmetic operations.[33] Addition in ones' complement requires an "end-around carry" mechanism, where any overflow carry is added back to the least significant bit of the sum, increasing hardware complexity and inefficiency compared to standard binary addition.[32]
Two's complement is preferred in modern computer architectures because it features a single zero representation, eliminating the need for end-around carry and allowing the same adder circuitry to handle both signed and unsigned operations uniformly.[33] This design simplifies implementation and improves performance in processors.[32]
Arithmetic Operations
Addition
In two's complement representation, the addition of two signed integers is performed using the identical binary addition procedure as for unsigned integers: bits are added pairwise from the least significant bit (LSB) to the most significant bit (MSB), with carries propagated between positions, and the final carry-out from the MSB is simply discarded without affecting the result. The n-bit result is then interpreted directly as a signed two's complement value, leveraging the fact that this representation ensures arithmetic operations behave correctly modulo $2^n.[7][34][35] This uniformity simplifies hardware design, as the same adder circuitry handles both unsigned and signed addition, with overflow detection providing the key distinction for signed operations. Unlike one's complement addition, which requires an "end-around carry" (adding the carry-out back to the LSB to resolve dual representations of zero), two's complement addition needs no such adjustment due to its unique zero and proper additive inverses.[7][35] For example, consider adding +5 and -3 in 4-bit two's complement: +5 is represented as0101, and -3 as 1101 (obtained by inverting 0011 and adding 1). Performing binary addition yields:
The result0101 (+5) + 1101 (-3) ------- 0010 (with carry-out 1 discarded)0101 (+5) + 1101 (-3) ------- 0010 (with carry-out 1 discarded)
0010 interprets as +2, correctly reflecting $5 + (-3) = 2.[7]
Overflow in two's complement addition occurs when the true sum falls outside the representable range [-2^{n-1}, 2^{n-1} - 1] for n bits, and it can be detected in two equivalent ways. First, hardware-level detection checks if the carry-in to the MSB differs from the carry-out of the MSB during addition.[35] Second, a simpler sign-based check verifies whether both operands have the same sign (both positive or both negative) but the result has the opposite sign; if the operands have different signs, no overflow is possible.[36][35]
Subtraction
In two's complement representation, subtraction of two numbers a and b is implemented as the addition of a to the two's complement negation of b, expressed as a - b = a + (-b).[1] The negation -b is computed by inverting all bits of b (one's complement) and adding 1 to the result.[1] A representative 4-bit example illustrates this process: subtracting 4 (binary0100) from 7 (binary 0111) requires first negating 4 to obtain -4 as 1100 (invert 0100 to 1011, then add 1). Adding 0111 + 1100 yields 0011 (binary for 3), confirming the result.[37]
In hardware, the arithmetic logic unit (ALU) performs subtraction using the identical adder circuitry employed for addition; negation is achieved by inverting the subtrahend bits and asserting a carry-in of 1 to the least significant bit.[38] Overflow detection during subtraction follows the same procedure as in addition, examining whether the carry into the sign bit matches the carry out from the sign bit.[37]
This unified approach enhances efficiency by obviating the need for dedicated subtractor hardware, allowing a single adder design to handle both operations in digital systems.[1]