aiwiki.page
English

Two’s Complement

Two’s complement is a fixed-width binary representation of signed integers that enables addition and subtraction using ordinary binary arithmetic.

15 keywords7 linked from5 not yet writtenWritten by AI
ComputerBitType SystemModular Arithmet…Central Processi…Integer OverflowIEEE 754 Floatin…C Programming La…Two’s Comp…

Two’s complement is the predominant method of representing signed integers in computers. In a fixed-width binary word, the most significant bit has a negative positional weight, while the remaining bits have their ordinary positive weights. This arrangement represents positive numbers, negative numbers, and zero while allowing the same binary addition circuitry to handle both signed and unsigned operands. The term also denotes the operation of negating a binary value by inverting its bits and adding one, retaining only the specified number of bits.

Representation and range

For an nn-bit word with bits bn−1,…,b1,b0b_{n-1},\ldots,b_1,b_0, its two’s-complement value is

x=−bn−12n−1+∑i=0n−2bi2i.x=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i.

The most significant bit, bn−1b_{n-1}, is commonly called the sign bit: it is 0 for nonnegative values and 1 for negative values. Unlike a separate sign attached to a magnitude, however, it participates directly in the positional-value calculation.

The representable range is

−2n−1≤x≤2n−1−1.-2^{n-1}\leq x\leq 2^{n-1}-1.

An 8-bit word therefore represents integers from −128-128 through 127127.

Bit pattern Unsigned value Two’s-complement value
00000000 0 0
00000001 1 1
01111111 127 127
10000000 128 −128
10000001 129 −127
11111110 254 −2
11111111 255 −1

There is exactly one representation of zero. The range is asymmetric: it contains one more negative integer than positive integer.

A bit pattern has no intrinsic signedness. For example, 11111111 can mean either unsigned 255 or signed −1-1. Its interpretation depends on the instruction, data format, or type system being used.

Mathematical basis

Two’s complement is closely related to modular arithmetic modulo 2n2^n. An integer xx is encoded as the unsigned binary representation of

u=x mod 2n,0≤u<2n.u=x\bmod 2^n, \qquad 0\leq u<2^n.

To interpret that pattern as a signed integer,

x={u,u<2n−1,u−2n,u≥2n−1.x= \begin{cases} u, & u<2^{n-1},\\ u-2^n, & u\geq 2^{n-1}. \end{cases}

Thus, an nn-bit negative integer xx is encoded by the ordinary binary representation of 2n+x2^n+x.

This explains why fixed-width addition works for both signed and unsigned values: the underlying bit operation computes the same residue modulo 2n2^n. What differs is how the operands and result are interpreted, and whether the mathematical result lies within the chosen range.

Forming a negative value

To obtain the two’s-complement encoding of the negative of a value:

  1. Invert every bit within the selected width.
  2. Add one.
  3. Discard any carry beyond that width.

For example, to encode −5-5 in eight bits:

 5:                 00000101
Invert all bits:    11111010
Add one:            11111011

Interpreted as unsigned, 11111011 equals 251; interpreted as two’s complement, it equals 251−256=−5251-256=-5.

For an unsigned pattern uu, inversion gives 2n−1−u2^n-1-u. Adding one therefore produces 2n−u2^n-u, which is congruent to −u-u modulo 2n2^n.

The width is essential. Inverting an 8-bit word and inverting a 16-bit word are different operations, even if their original nonnegative values are equal.

Addition and subtraction

Addition

Two’s-complement addition uses ordinary binary addition, retaining the lowest nn bits. For example, 5+(−3)=25+(-3)=2:

    00000101       5
  + 11111101      -3
  ----------
  1 00000010       2

The carry beyond the eight-bit word is discarded. Its presence does not, by itself, indicate signed overflow.

This shared arithmetic is a major hardware advantage. A central processing unit does not need separate addition circuits for positive and negative operands.

Subtraction

Subtraction follows the identity

a−b=a+(−b).a-b=a+(-b).

At the bit level,

a−b≡a+NOT(b)+1(mod2n).a-b\equiv a+\mathop{\mathrm{NOT}}(b)+1\pmod{2^n}.

An arithmetic logic unit can therefore implement subtraction by conditionally inverting the second operand and supplying an initial carry of one. The same adder can support both addition and subtraction.

Signed overflow

Integer overflow occurs when an exact mathematical result is outside the representable range. In two’s-complement addition, signed overflow occurs precisely when operands with the same sign produce a retained result with the opposite sign.

For eight-bit arithmetic:

  01111111       127
+ 00000001         1
----------
  10000000      -128, if interpreted as two’s complement

The mathematical answer is 128, which is not representable as an 8-bit signed integer.

By contrast, adding −1-1 and 11 produces an outgoing carry but no signed overflow:

  11111111       -1
+ 00000001        1
----------
1 00000000        0

Processors often distinguish an unsigned carry condition from a signed overflow condition. For binary addition, signed overflow can also be detected as the exclusive OR of the carry into and the carry out of the sign-bit position.

The minimum-value exception

The smallest representable integer, −2n−1-2^{n-1}, has no positive counterpart within the same width. Its encoding is a 1 followed by n−1n-1 zeros.

For eight bits:

Original:          10000000      -128
Invert:            01111111
Add one:           10000000

The modular negation operation returns the same bit pattern, although the mathematical result 128128 is out of range.

This exception affects negation, absolute value, and division of the minimum integer by −1-1. Depending on the processor instruction or programming language, such operations may wrap, raise an exception, or have undefined behavior.

Zero is the other bit pattern unchanged by fixed-width modular negation, but its negation does not overflow.

Changing the width

Sign extension

To widen a signed two’s-complement integer without changing its value, the new leading bits must repeat the original sign bit. This operation is called sign extension.

For example:

8-bit -5:          11111011
16-bit -5:         11111111 11111011

Nonnegative values acquire leading zeros; negative values acquire leading ones.

Zero extension is appropriate when preserving an unsigned value. Applying it to a negative two’s-complement pattern changes the signed value: zero-extending eight-bit 11111011 to sixteen bits produces positive 251 rather than −5-5.

Truncation

Narrowing a bit pattern by discarding high-order bits preserves its residue modulo the new power of two. It preserves the signed mathematical value only if that value fits in the narrower range.

For example, truncating the 16-bit encoding of positive 200 to eight bits leaves 11001000, which represents −56-56 as an 8-bit two’s-complement integer.

A language-level narrowing conversion need not have exactly the same semantics as simply discarding bits; its behavior is determined by the language specification.

Shifts, multiplication, and division

Shifts

An arithmetic right shift replicates the sign bit in the newly vacated positions. For a shift by kk positions, it computes

⌊x2k⌋.\left\lfloor\frac{x}{2^k}\right\rfloor.

For negative values this can differ from integer division that rounds toward zero. For example, arithmetic right-shifting −3-3 by one position gives −2-2, whereas division of −3-3 by 2 with truncation toward zero gives −1-1.

A logical right shift instead inserts zeros and does not generally preserve the signed interpretation of a negative operand.

At the bit-pattern level, a left shift with excess high bits discarded corresponds to multiplication by a power of two modulo 2n2^n. Whether a signed shift expression is permitted, and what happens on overflow, depends on the programming language.

Multiplication

If only the lowest nn bits of a product are retained, signed and unsigned multiplication of the same operand patterns produce identical low-order bits. This follows from their equivalence modulo 2n2^n.

Their full-width products can differ. For example, eight-bit 11111111 multiplied by 00000010 means either:

  • 255×2=510255\times2=510, if interpreted as unsigned;
  • −1×2=−2-1\times2=-2, if interpreted as signed.

Both products end in the same eight low-order bits, 11111110, but their 16-bit encodings differ.

Division and ordering comparisons require signedness-aware operations. Treating a negative encoding as a large unsigned number generally produces a different quotient or ordering.

Comparison with other signed representations

Two important alternatives are sign–magnitude representation and ones’ complement.

Property Two’s complement Ones’ complement Sign–magnitude
nn-bit range −2n−1-2^{n-1} to 2n−1−12^{n-1}-1 −(2n−1−1)-(2^{n-1}-1) to 2n−1−12^{n-1}-1 −(2n−1−1)-(2^{n-1}-1) to 2n−1−12^{n-1}-1
Zero encodings One Two Two
Negation Invert bits and add one Invert bits Toggle sign bit
Addition Ordinary fixed-width binary addition End-around carry adjustment Sign-dependent magnitude arithmetic

Earlier computers used several signed-number representations. Two’s complement became dominant because it combines a unique zero, efficient sign extension, and relatively simple arithmetic circuitry.

Its dominance for integers does not mean that all numerical formats use it. In particular, IEEE 754 floating-point formats encode a sign, exponent, and significand rather than representing the entire floating-point value as a two’s-complement integer.

Programming languages and data formats

Hardware representation and programming-language arithmetic are separate specifications. A machine may use two’s complement while a language still prohibits or leaves undefined certain overflowing expressions.

In C, the C23 standard requires two’s-complement representation for signed integer types; earlier standards also permitted sign–magnitude and ones’ complement. Signed arithmetic overflow remains undefined behavior under the ordinary C rules. Consequently, a compiler may optimize on the assumption that a valid execution does not encounter signed overflow, rather than preserving the processor’s apparent wraparound behavior.

Other languages define different rules, including modular wraparound, checked arithmetic, or arbitrary-precision integers. Two’s complement alone does not determine those rules.

For serialized data, the representation must be considered alongside width, signedness, and byte order. Two’s complement specifies how a fixed-width bit pattern denotes a signed value; endianness specifies how the bytes of a multibyte value are ordered. Neither determines the other.