Signed Integers and Two's Complement

The previous two lessons treated numbers as non-negative. Hardware, however, has no extra place to hold a minus sign: a 32-bit register has only 32 bits. The sign must be encoded within the same pattern as the value itself.

This lesson asks how that encoding is done. More than one answer is possible, but hardware has converged on essentially a single answer, and the reason is that this method leaves the addition circuit completely unchanged.

Two Intuitive Approaches and Their Problems

In sign-magnitude representation, the leftmost bit carries the sign and the remaining bits carry the magnitude. In eight bits, 0000 0101 is written for $+5$ and 1000 0101 for $-5$. This representation is close to human intuition and has two problems.

First, zero has two representations: 0000 0000 and 1000 0000. When two patterns carry the same value, equality comparison stops being a matter of comparing bits.

Second, and more serious: addition is no longer plain addition. Computing $5 + (-5)$ at the bit level gives 0000 0101 + 1000 0101 = 1000 1010; under the sign-magnitude interpretation this pattern means $-10$, whereas the result should have been zero. The hardware would need to strip out the signs, compare the magnitudes, and perform subtraction.

In one’s complement representation, a negative number is obtained by flipping every bit of the positive value: $-5$ becomes 1111 1010. Addition comes closer to plain addition, but the carry bit must be added back at the start; zero is again represented twice (0000 0000 and 1111 1111).

Two’s Complement

Two’s complement representation eliminates both problems. Its definition fits in one sentence: the leftmost bit has a negative positional value. An $n$-bit pattern has the value:

$$-d_{n-1} \times 2^{n-1} + \sum_{i=0}^{n-2} d_i \times 2^{i}$$

For eight bits, the leftmost bit has weight $-128$, and the others carry the usual $+64, +32, \dots, +1$. Examples:

Pattern	Computation	Value
0000 0101	$4 + 1$	$5$
1111 1011	$-128 + 64 + 32 + 16 + 8 + 2 + 1$	$-5$
1111 1111	$-128 + 127$	$-1$
1000 0000	$-128$	$-128$
0111 1111	$127$	$127$

Zero has a single representation: 0000 0000. The leftmost bit still gives away the sign — if it is $1$, the number is negative — but it is not a separate sign field; it is part of the value.

The range of $n$-bit two’s complement is:

$$[-2^{n-1},\ 2^{n-1} - 1]$$

The range is not symmetric: in eight bits, $-128$ is representable but $+128$ is not. There is one more value on the negative side, because zero consumes a pattern on the positive side.

Producing the Negative

Finding a number’s negative takes two steps: flip every bit, then add one.

For $5$: 0000 0101 $\rightarrow$ flip 1111 1010 $\rightarrow$ add one 1111 1011. The result is the $-5$ pattern from the table.

Applying the same operation to $-5$ returns to $5$: 1111 1011 $\rightarrow$ 0000 0100 $\rightarrow$ 0000 0101. The operation is its own inverse.

Why the rule works can be seen as follows: the sum of a pattern and its bitwise inverse is the pattern with every bit set to $1$, that is, $2^n - 1$. Adding one gives $2^n$; in an $n$-bit register, the value $2^n$ corresponds to zero. Hence adding $x$ to “flip and add one” yields zero — which is exactly the definition of a negative.

There is a single exception: the smallest value. Applying the operation to $-128$ again yields 1000 0000. Since $+128$ lies outside the range, this value has no negative in eight bits.

Why Addition Is a Single Circuit

The decisive hardware advantage of two’s complement is this: signed addition is the same operation as unsigned addition. The bits are added, and the overflowing carry bit is discarded.

Computing $5 + (-3)$ in eight bits:

  0000 0101      (5)
+ 1111 1101      (-3)
-------------
1 0000 0010      (carry bit discarded)
  0000 0010      (2)

The result is correct, and the signs were never inspected. Subtraction, too, needs no separate circuit: computing $a - b$ is done by producing the negative of $b$ and adding it. Comparison operations are also built on the same adder.

This is a concrete example of a representation choice directly reducing hardware complexity. The representation closest to intuition (sign-magnitude) gives the most expensive circuit; the representation furthest from intuition (two’s complement) gives the cheapest one.

Overflow

Fixed width means results that fall outside the range cannot be represented. The result does not vanish; it wraps around from the other end of the range.

Under an unsigned interpretation, in eight bits, $255 + 1$ gives 1111 1111 + 0000 0001 = 1 0000 0000; discarding the carry leaves 0000 0000, that is, $0$. The number has not grown — it has wrapped around.

Under a signed interpretation, $127 + 1$ gives 0111 1111 + 0000 0001 = 1000 0000, and this pattern means $-128$. The sum of two positive numbers has come out negative.

The difference between the two cases is nothing but a different interpretation of the same bit operation. Hardware reports both kinds of overflow with separate flags; which one is meaningful is decided by the program, which knows whether the value is being read as signed or unsigned.

The practical consequence of overflow is that numeric code can silently produce a wrong result. The sum of two large positive numbers coming out negative, loop counters wrapping around, and array indices pointing to unexpected locations all belong to this class. The security dimension of this behavior is treated separately in the cybersecurity curriculum.

Extension

When a value is moved into a wider type, the newly empty bits on the left must be filled. The rule for filling them depends on the interpretation, so that the value is preserved:

• For unsigned values, the left bits are filled with zero (zero extension).
• For signed values, the left bits are filled with a copy of the sign bit (sign extension). The eight-bit pattern 1111 1011 ($-5$) becomes 1111 1111 1111 1011 in sixteen bits, and its value is preserved.

Applying the wrong rule silently changes the value: the eight-bit $-5$ pattern, under zero extension, becomes 0000 0000 1111 1011 in sixteen bits, that is, $251$. In the opposite direction, a sixteen-bit $-5$ pattern read as unsigned gives $65{,}531$. This is one of the typical sources of error in code that converts between types of different width.

The Shared Example under a Signed Interpretation

The leftmost bit of the course’s shared example, the 0x41424344 pattern, is $0$ — the first hexadecimal digit is 4, that is, 0100. The pattern therefore carries the same value under a 32-bit signed interpretation as it does under the unsigned one: $1{,}094{,}861{,}636$.

Had the first digit been 8 instead — that is, 0x81424344 — the leftmost bit would be $1$, and the same operations would give a very different value:

$$2{,}168{,}603{,}460 - 2^{32} = -2{,}126{,}363{,}836$$

No example shows the distance between a bit sequence and its meaning better than this one: changing a single bit shifts the value by more than two billion.

Seeing It in Practice

Python’s integers are not fixed-width; they do not overflow, they grow. To observe fixed-width hardware behavior, masking is used:

def fixed_width(value: int, bits: int = 8) -> int:
    """Reduces a value to its bits-wide two's complement interpretation."""
    mask = (1 << bits) - 1          # 0xFF for 8 bits
    value &= mask                   # discard excess bits
    sign_bit = 1 << (bits - 1)      # 0x80 for 8 bits
    if value & sign_bit:
        value -= 1 << bits          # the leftmost bit has negative weight
    return value


print(fixed_width(0b11111011))     # -5
print(fixed_width(127 + 1))        # -128   (signed overflow)
print(fixed_width(-1))             # -1
print((255 + 1) & 0xFF)            # 0      (unsigned wraparound)

print(fixed_width(0x41424344, 32)) # 1094861636
print(fixed_width(0x81424344, 32)) # -2126363836

The body of fixed_width is a direct translation of this lesson’s definition: the bits that do not fit the width are discarded first, then negative weight is applied to the leftmost bit.

Summary

• In a fixed-width representation, the sign is encoded within the pattern itself rather than in a separate field.
• In two’s complement representation the leftmost bit has a negative positional value; the range of $n$ bits is $[-2^{n-1}, 2^{n-1}-1]$, and zero has a single representation.
• A number’s negative is produced by flipping every bit and adding one; the smallest value is the exception to this operation.
• Signed addition is performed by the same circuit as unsigned addition; this is the reason two’s complement is preferred.
• When the range is exceeded, the result does not vanish — it wraps around from the other end: under unsigned interpretation $255 + 1 = 0$, under signed interpretation $127 + 1 = -128$.
• The fill rule under extension depends on interpretation; for signed values the sign bit is copied.

Next Step

Integers are exact within the range they can represent: every value either exists or it does not. Fractional numbers are a different matter — an infinite number of real values must be packed into a finite number of patterns. The next lesson takes up how this is done, and why the sum $0.1 + 0.2$ does not come out to exactly $0.3$.