--- title: "Signed Integers and Two's Complement" source: 'https://academia.sh/en/courses/how-computers-work/signed-integers' course: 'How Computers Work' language: en updated: '2026-08-17T18:08:11+00:00' license: 'CC BY-SA 4.0' --- # Signed Integers and Two's Complement How negative numbers are encoded within a bit pattern, two's complement representation, and overflow behavior. 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: ```python 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$.