--- title: Integer Representation module: Foundations moduleNumber: 0 lessonNumber: 2 order: 2 summary: > A fixed-width byte string is just a pattern; what makes it a number is the rule we read it by. We define unsigned encoding and two's complement — where the top bit carries a negative weight — derive the ranges UMax, TMin, and TMax, and show how the same bits reinterpret between signed and unsigned, how widening sign-extends, and what truncation throws away. topics: [Foundations] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §2.2 Integer Representations" --- The [previous lesson](/computer-architecture/foundations/bits-bytes-and-words) left a $w$-bit string as a raw pattern with no meaning of its own. Two rules turn that pattern into an integer. The **unsigned** rule reads it as a plain base-2 magnitude; the **two's-complement** rule reads it as a signed integer by making the top bit count _against_ the total. Both rules cover all $2^w$ patterns, neither wastes one, and the machine implements both with the same adder. This lesson fixes those two encodings, the ranges they span, and the three operations — reinterpretation, extension, and truncation — that move a value between widths and meanings. ## Unsigned encoding Let $\vec{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$ be a bit vector, $x_{w-1}$ the most significant bit. The **unsigned** value reads each bit at its positional weight and sums the ones, exactly as the byte figure from the last lesson did: $$ B2U(\vec{x}) = \sum_{i=0}^{w-1} x_i\, 2^i. $$ Every bit carries a non-negative weight, so $B2U$ ranges from $0$ (all bits clear) up to a maximum when every bit is set. That maximum is one of the three numbers worth memorizing for the rest of the course: $$ UMax_w = \sum_{i=0}^{w-1} 2^i = 2^w - 1. $$ The map $B2U$ is a **bijection**: it pairs each of the $2^w$ bit patterns with a distinct value in $[0, 2^w - 1]$ and leaves nothing out. That property, full coverage with no collisions, is what lets us speak of _the_ unsigned value of a pattern, and it will hold for two's complement too. ## Two's complement and the sign bit's weight To represent negatives we keep every bit's weight the same except the most significant, whose weight we _negate_. That single change defines **two's complement**: $$ B2T(\vec{x}) = -x_{w-1}\, 2^{w-1} + \sum_{i=0}^{w-2} x_i\, 2^i. $$ The leading term is the only difference from $B2U$: the top bit, the **sign bit**, now contributes $-2^{w-1}$ when set instead of $+2^{w-1}$. Everything below it is an ordinary unsigned magnitude. So a negative value is the sign bit's $-2^{w-1}$ plus an unsigned offset from the lower bits. $$ % caption: The same eight bits read two ways. Every bit but the top keeps its % caption: positive weight; the sign bit's weight flips from +128 to -128, turning % caption: the unsigned 233 into the two's-complement -23. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\v in {1/1, 2/1, 3/0, 4/1, 5/0, 6/0, 7/1} \node[bit] at (\i,0) {\v}; \node[bit, draw=acc, very thick, text=acc] at (0,0) {1}; \node[text=acc] at (0,0.95) {-128}; \foreach \i/\w in {1/64, 2/32, 3/16, 4/8, 5/4, 6/2, 7/1} \node at (\i,0.95) {\w}; \node[anchor=west, text=acc] at (8.4,0.95) {B2T = -128+64+32+8+1 = -23}; \node[anchor=west] at (8.4,0) {B2U = 128+64+32+8+1 = 233}; \end{tikzpicture} $$ Like $B2U$, the map $B2T$ is a bijection onto its range, but the range is shifted to straddle zero. Setting only the sign bit gives the most negative value; clearing the sign bit and setting everything below gives the most positive: $$ TMin_w = -2^{w-1}, \qquad TMax_w = 2^{w-1} - 1. $$ Two facts follow, and both matter in practice. First, the range is **asymmetric**: there is one more negative number than positive, because zero occupies a slot on the non-negative side. So $|TMin| = TMax + 1$, and $-TMin$ is _not representable_. Second, $UMax = 2\,TMax + 1$, since flipping the sign bit's weight from $-2^{w-1}$ to $+2^{w-1}$ shifts every negative value up by $2^w$. > **Definition (Two's complement).** For a $w$-bit vector $\vec{x}$, the signed > value is $B2T(\vec{x}) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i$. The encoding > covers $[TMin_w, TMax_w] = [-2^{w-1},\ 2^{w-1}-1]$, one bijection over all $2^w$ > patterns, with the sole negative weight on the sign bit. For $w = 8$ the landmarks are $UMax = 255$, $TMin = -128$, $TMax = 127$; for $w = 32$, $UMax \approx 4.29 \times 10^9$, $TMin \approx -2.15 \times 10^9$, $TMax \approx 2.15 \times 10^9$. These are the limits a C `unsigned`, `int`, `UINT_MAX`, and `INT_MIN`/`INT_MAX` actually take on a typical machine.[^cmax] A short table of 4-bit values shows the two readings side by side and exactly where they diverge. The first eight patterns (sign bit clear) read the same under both rules; the last eight (sign bit set) diverge by $2^4 = 16$. | Bits | Unsigned $B2U$ | Two's comp. $B2T$ | | --- | --- | --- | | `0000` | 0 | 0 | | `0001` | 1 | 1 | | `0111` | 7 | 7 (= $TMax$) | | `1000` | 8 | $-8$ (= $TMin$) | | `1001` | 9 | $-7$ | | `1110` | 14 | $-2$ | | `1111` | 15 (= $UMax$) | $-1$ | The pattern `1111` is worth a second look: it is $UMax$ read one way and $-1$ read the other, and the reason $-1$ is _all ones_ in two's complement is that $-1 = 0 - 1$ borrows through every column, filling the whole word. This is worth committing to memory — an all-ones word is $-1$ signed and $UMax$ unsigned at every width — because it turns up constantly in masks and error returns. ## The number wheel: same bits, two readings Because both encodings are bijections over the same $2^w$ patterns, they differ only in _where they cut the circle_. Counting bit patterns $0, 1, \dots, 2^w-1$ and reading each as unsigned gives a monotone climb; reading the top half as two's complement wraps those patterns around to the negative side. $$ % caption: A 4-bit number wheel. The outer ring is the bit pattern; inside, the % caption: unsigned reading climbs 0..15 while the two's-complement reading sends % caption: the top half (1000..1111) to -8..-1. The sign bit splits the circle. \begin{tikzpicture}[font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \def\R{2.5} % 16 positions, pattern p at angle 90 - p*22.5 \foreach \p/\u/\t in {% 0/0/0, 1/1/1, 2/2/2, 3/3/3, 4/4/4, 5/5/5, 6/6/6, 7/7/7, 8/8/{-8}, 9/9/{-7}, 10/10/{-6}, 11/11/{-5}, 12/12/{-4}, 13/13/{-3}, 14/14/{-2}, 15/15/{-1}} { \node at ({90-\p*22.5}:\R) {\u}; \node[text=acc] at ({90-\p*22.5}:\R-0.72) {\t}; } \draw[dashed, black] (\R+0.45,0) arc (0:-180:{\R+0.45}); \node[anchor=north, black] at (0,-\R-0.78) {sign bit set}; \node at (0,0.3) {unsigned}; \node[text=acc] at (0,-0.3) {two's comp}; \end{tikzpicture} $$ The dashed boundary marks the sign bit: every pattern in the lower half has $x_{w-1} = 1$, and exactly there the two readings diverge by $2^w$. Converting between the two encodings never touches the bits, only the rule we apply to them. ## The asymmetry of TMin The signed range $[-2^{w-1},\ 2^{w-1}-1]$ holds one more negative value than positive, and the odd one out is $TMin$ itself. Every other value has a negation partner across zero: $3$ pairs with $-3$, $TMax$ with $-TMax$. The partner of $TMin$ would be $+2^{w-1}$, one step past $TMax$, and no $w$-bit pattern encodes it. $$ % caption: Negation mirrors the 4-bit number line across zero, pairing each value % caption: with its opposite. TMin = -8 is the exception: its mirror +8 sits one % caption: step past TMax = 7, so negating -8 hands back -8. \begin{tikzpicture}[font=\footnotesize, >=stealth] \definecolor{acc}{HTML}{2348F2} \draw[->, thick] (-6.4,0) -- (6.6,0); \foreach \v in {-8,...,7} { \draw ({\v*0.72},0.08) -- ({\v*0.72},-0.08); \node[below] at ({\v*0.72},-0.12) {\v}; } \draw[black, dashed] (5.76,0) circle (2.6pt); \node[below, black] at (5.76,-0.12) {+8}; \draw[<->, acc] (-2.16,0.22) .. controls (-2.16,0.95) and (2.16,0.95) .. (2.16,0.22); \node[text=acc] at (0,1.02) {negate}; \draw[->, acc, dashed] (-5.76,0.22) .. controls (-5.76,2.1) and (5.76,2.1) .. (5.76,0.28); \node[text=acc] at (0,1.86) {-(-8) needs +8: not representable}; \end{tikzpicture} $$ Ask the machine for $-TMin$ anyway and fixed-width arithmetic (the subject of the [next lesson](/computer-architecture/foundations/integer-arithmetic)) wraps the missing $+2^{w-1}$ around to $-2^{w-1}$: negating $TMin$ returns $TMin$. For $w = 4$, negate $-8 = 1000_2$ by flipping the bits and adding one: $0111_2 + 1 = 1000_2$, the same pattern. Three practical consequences follow. - `abs(INT_MIN)` cannot produce the right answer, since $|TMin| = TMax + 1$ is out of range; on a two's-complement machine the call comes back _negative_, and the C standard leaves it undefined. - The innocuous normalization `if (x < 0) x = -x;` fails to make one input non-negative, a real bug in binary-search midpoints and absolute-difference code. - The literal `-2147483648` is a pitfall in C source: it parses as negation applied to the constant `2147483648`, which does not fit in an `int`, so `limits.h` spells the constant as `(-INT_MAX - 1)`.[^tminc] ```c [tmin.c] #include #include int a = abs(INT_MIN); /* undefined; wraps back to INT_MIN on x86-64 */ int m = -INT_MAX - 1; /* the portable way to write TMin */ ``` ## Signed ↔ unsigned: same bits, different meaning A C cast between `int` and `unsigned` of the same width is a **reinterpretation**: the bit pattern is left alone and only the reading rule changes. For a value $x$ in two's complement, the unsigned reading of the identical bits is $$ T2U(x) = \begin{cases} x & x \ge 0, \\ x + 2^w & x < 0. \end{cases} $$ Negative values gain $2^w$ because the sign bit's weight flips from $-2^{w-1}$ to $+2^{w-1}$, a swing of exactly $2^w$. Going the other way, an unsigned value at or above $2^{w-1}$ reads back as negative: $$ U2T(u) = \begin{cases} u & u < 2^{w-1}, \\ u - 2^w & u \ge 2^{w-1}. \end{cases} $$ This conversion is usually **silent**. In C, an expression mixing signed and unsigned operands converts the signed one to unsigned, which can flip comparisons. ```c [signedness.c] #include int main(void) { int a = -1; /* bits: 0xffffffff */ unsigned b = 1u; /* -1 is converted to unsigned 4294967295, so the test is FALSE */ printf("%d\n", a < b); /* prints 0, not 1 */ printf("%u\n", (unsigned) a); /* prints 4294967295 */ return 0; } ``` The comparison `a < b` looks like $-1 < 1$ and should be true, but C promotes `a` to `unsigned`, turning its bits `0xffffffff` into $UMax = 4{,}294{,}967{,}295$, which is _not_ less than $1$. The same bits, read under the unsigned rule, give the opposite answer.[^implicit] ## Widening: sign extension and zero extension Moving a value into a _wider_ type must preserve its numeric value, and the bits needed to do so depend on the encoding. For an **unsigned** value, prepend zeros (**zero extension**), since leading zeros never change a base-2 magnitude. For a **two's-complement** value, replicate the sign bit (**sign extension**), copying $x_{w-1}$ into every new high position. $$ % caption: Widening 4 bits to 8. Zero extension pads an unsigned value with 0s; % caption: sign extension copies the sign bit, so the negative -3 (1101) stays -3 % caption: (1111 1101) rather than becoming a large positive number. \begin{tikzpicture}[font=\footnotesize, >=stealth, bit/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % source 4-bit value 1101 \foreach \i/\v in {0/1, 1/0, 2/1, 3/1} \node[bit] at (\i*0.75,1.7) {\v}; \node[anchor=east] at (-0.5,1.7) {4-bit}; % zero-extended \foreach \i/\v in {0/0,1/0,2/0,3/0} \node[bit] at (\i*0.75,0.55) {\v}; \foreach \i/\v in {4/1,5/0,6/1,7/1} \node[bit] at (\i*0.75,0.55) {\v}; \node[anchor=east] at (-0.5,0.55) {zero-ext}; \node[text=acc, anchor=west] at (6.1,0.55) {unsigned 13 = 13}; % sign-extended \foreach \i/\v in {0/1,1/1,2/1,3/1} \node[bit, draw=acc, text=acc] at (\i*0.75,-0.6) {\v}; \foreach \i/\v in {4/1,5/0,6/1,7/1} \node[bit] at (\i*0.75,-0.6) {\v}; \node[anchor=east] at (-0.5,-0.6) {sign-ext}; \node[text=acc, anchor=west] at (6.1,-0.6) {signed -3 = -3}; \end{tikzpicture} $$ Sign extension keeps the value intact: the high copies of the sign bit re-create the $-2^{(w-1)} + 2^{(w-2)} + \dots$ telescoping that leaves $B2T$ unchanged. A C compiler picks the right one automatically from the _source_ type — `int` to `long` sign-extends, `unsigned` to `unsigned long` zero-extends — which is why declaring a width's signedness correctly matters.[^widen] ## Truncation: dropping the high bits The reverse, casting to a _narrower_ type, simply discards the high-order bits. This is **truncation**, and unlike widening it can change the value. For an unsigned value, dropping to $k$ bits computes the result **modulo** $2^k$: $$ B2U([x_{k-1}, \dots, x_0]) = B2U([x_{w-1}, \dots, x_0]) \bmod 2^k. $$ For a signed value, the kept bits are read by $B2T$ on the narrower width, so the result is $U2T_k\!\left(x \bmod 2^k\right)$ — the same low bits, but their top surviving bit may now act as a sign bit. Casting `int` $53191$ to a 16-bit `short`, for instance, keeps `0xCFC7` and reinterprets it as the negative $-12345$. $$ % caption: Truncating the int 53191 = 0x0000cfc7 to a 16-bit short. The dropped % caption: high half is all zeros, so no magnitude is lost, but the kept half now % caption: leads with a 1 bit, which the narrower signed type reads as -12345. \begin{tikzpicture}[font=\footnotesize, >=stealth, hx/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.6,1.8) {int 53191}; \foreach \i/\v in {0/0, 1/0, 2/0, 3/0} \node[hx, draw=black, text=black] at (\i*0.8,1.8) {\v}; \foreach \i/\v in {4/c, 5/f, 6/c, 7/7} \node[hx] at (\i*0.8,1.8) {\v}; \node[black] at (1.2,2.55) {dropped}; \node[text=acc] at (4.4,2.55) {kept: low 16 bits}; \foreach \i in {4,5,6,7} \draw[->, black] (\i*0.8,1.42) -- (\i*0.8,0.72); \node[hx, draw=acc, thick, text=acc] at (3.2,0.3) {c}; \foreach \i/\v in {5/f, 6/c, 7/7} \node[hx] at (\i*0.8,0.3) {\v}; \node[anchor=east] at (2.35,0.3) {short}; \node[anchor=west] at (6.15,0.3) {reads as -12345}; \node[text=acc, anchor=north] at (3.2,-0.18) {top bit now the sign}; \end{tikzpicture} $$ ```c [truncate.c] int x = 53191; /* 0x0000cfc7 */ short s = (short) x; /* keeps 0xcfc7 */ /* low 16 bits 0xcfc7 read as signed short = -12345 */ ``` Truncation is information loss: the high bits are gone, and whether the surviving value is the one you wanted depends entirely on whether it fit in the narrower range. Mixing it with the signedness reinterpretation above is a reliable source of bugs, which is why the next lesson treats overflow as a first-class topic. ## Why two's complement won CS:APP presents two's complement as _the_ signed encoding, which is accurate for every machine you will program — but it was not the only candidate, and seeing the alternatives explains why the industry converged on it. Three schemes competed in early computers, all of which reserve the top bit as a sign. **Sign-magnitude** stores the magnitude in the low bits and a sign in the top bit, exactly as humans write numbers: $-3$ is `1011` (sign 1, magnitude `011`). It is easy to read but has two flaws that sank it: there are _two_ zeros (`0000` and `1000`, positive and negative zero), wasting a pattern and complicating equality; and addition needs to inspect the signs and choose between adding and subtracting, so it cannot reuse the plain adder. **One's complement** negates by flipping every bit, which also produces a negative zero (`1111`) and needs an awkward "end-around carry" to add correctly. **Two's complement** negates by flipping and adding one, and its single decisive advantage is the one the next lesson develops in full: the _same adder circuit_ adds signed and unsigned values with no special cases, because the encoding is arithmetic modulo $2^w$.[^twoscomp] $$ % caption: Three signed encodings of -3, each negating +3 = 0011. Sign-magnitude % caption: flips only the sign bit; one's complement flips all bits; two's % caption: complement flips all bits and adds one. Only two's complement has a % caption: single zero and reuses the unsigned adder. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=6.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.5,2.4) {plus 3}; \foreach \i/\v in {0/0,1/0,2/1,3/1} \node[bit] at (\i*0.7,2.4) {\v}; \node[anchor=east] at (-0.5,1.3) {sign-mag}; \foreach \i/\v in {0/1,1/0,2/1,3/1} \node[bit] at (\i*0.7,1.3) {\v}; \node[anchor=west, black] at (2.9,1.3) {two zeros}; \node[anchor=east] at (-0.5,0.3) {one's-c}; \foreach \i/\v in {0/1,1/1,2/0,3/0} \node[bit] at (\i*0.7,0.3) {\v}; \node[anchor=west, black] at (2.9,0.3) {two zeros}; \node[anchor=east] at (-0.5,-0.7) {two's-c}; \foreach \i/\v in {0/1,1/1,2/0,3/1} \node[bit, draw=acc, text=acc] at (\i*0.7,-0.7) {\v}; \node[anchor=west, text=acc] at (2.9,-0.7) {one zero, reuses the adder}; \end{tikzpicture} $$ The design is old and its origins are usually credited to von Neumann's 1945 report on the EDVAC, which proposed complement arithmetic for exactly the hardware-economy reason above.[^edvac] A representation is a hardware decision as much as a mathematical one: two's complement won because it lets one adder, one comparison, and one multiply serve both signed and unsigned data, a theme that runs through the whole next lesson. > **Takeaway.** A $w$-bit pattern is a number only under a rule. Unsigned sums > positive weights up to $UMax = 2^w-1$; two's complement negates the top bit's > weight to span $[TMin, TMax] = [-2^{w-1},\ 2^{w-1}-1]$, asymmetrically: $-TMin$ > is not representable, so `abs` and `x = -x` both have a losing input. Signed ↔ > unsigned reinterprets bits without moving them, widening sign- or zero-extends to > preserve value, and truncation drops high bits modulo $2^k$. With both encodings in hand, the next lesson asks what happens when fixed-width arithmetic runs off the end of its range — the wrap-around behavior of [integer arithmetic](/computer-architecture/foundations/integer-arithmetic). [^cmax]: **Bryant & O'Hallaron**, _CS:APP_, §2.2.1 — Integral Data Types: the C `limits.h` constants `UINT_MAX`, `INT_MIN`, `INT_MAX` and the typical 32- and 64-bit widths. [^twoscomp]: **Bryant & O'Hallaron**, _CS:APP_, §2.2.2–2.2.3 — the aside contrasting two's complement with sign-magnitude and one's complement, and the observation that two's complement is the near-universal choice because it has a single zero and a uniform adder. [^edvac]: **von Neumann**, _First Draft of a Report on the EDVAC_ (1945): the early proposal to use complement arithmetic so that subtraction could be performed by the addition hardware, the hardware-economy argument that still explains two's complement today. [^implicit]: **Bryant & O'Hallaron**, _CS:APP_, §2.2.5 — Signed vs. Unsigned in C: implicit conversion of operands to unsigned and the comparison pitfalls it causes. [^widen]: **Bryant & O'Hallaron**, _CS:APP_, §2.2.6 — Expanding the Bit Representation of a Number: sign extension preserves the two's-complement value; zero extension preserves the unsigned value. [^tminc]: **Bryant & O'Hallaron**, _CS:APP_, §2.2.3 — Two's-Complement Encoding: the asymmetric range $|TMin| = TMax + 1$, and the aside on why C headers write $TMin$ as `(-INT_MAX - 1)`.