Integer Representation

The previous lesson 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:

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:

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:

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.

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:

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=2TMax+1$, since flipping the sign bit's weight from $-2^{w-1}$ to $+2^{w-1}$ shifts every negative value up by $2^w$.

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.¹

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$.

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.

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.

Ask the machine for $-TMin$ anyway and fixed-width arithmetic (the subject of the next lesson) 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).²

#include <limits.h>
#include <stdlib.h>

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

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:

This conversion is usually silent. In C, an expression mixing signed and unsigned operands converts the signed one to unsigned, which can flip comparisons.

#include <stdio.h>

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.³

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.

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.⁴

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$:

For a signed value, the kept bits are read by $B2T$ on the narrower width, so the result is $U2T_k\left(x\mathrm{mod}{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$.

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$.⁵

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.⁶ 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.

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.