Negative Numbers: Two's Complement

Two's complement is simply the way computers store negative numbers: $-x$ is stored as whatever you'd have to add to $x$ to roll a $k$-bit counter over to all zeros. That's where the name comes from: the pattern for $-x$ is the complement of $x$ with respect to a power of two, $2^k$, meaning the two add up to exactly $2^k$. It's handy because the same adding circuit then works for positive and negative numbers alike. The formula $-x \equiv 2^k - x = \overline{x} + 1$ looks dense, but it's three small pieces: $2^k$ (one more than the biggest number $k$ bits can hold), $\overline{x}$ (flip every bit of $x$) and $+1$ (add one), with $\pmod{2^k}$ meaning the count wraps around like a clock. It's an odd-looking trick with a simple idea behind it; bear with it.

The number wheel. So far every bit pattern has meant a number 0 or bigger. What about negatives? Picture the sixteen 4-bit patterns around a clock face: 0000, 0001, …, 1111, and then back to 0000. Adding 1 steps clockwise and subtracting 1 steps back, so one step back from 0000 lands on 1111. It makes sense to call that $-1$. Two's complement reads the half of the wheel whose top bit is 1 as negative: 1000 through 1111 stand for $-8$ through $-1$.

The sign bit's weight. Equivalently, the top bit of a $k$-bit number is worth $-2^{k-1}$ instead of $+2^{k-1}$: $1011 = -8 + 2 + 1 = -5$. So $k$ bits hold $-2^{k-1}$ to $2^{k-1} - 1$, and a signed byte holds $-128$ to $127$.

Negating: flip and add 1. Here's why that recipe works. Add $x$ to its flipped version $\overline x$ and every column holds one 0 and one 1, so there are no carries and you get $11\ldots1 = 2^k - 1$. Move the 1 over: $\overline x + 1 = 2^k - x$, which is exactly the pattern for $-x$ on the wheel. For example $5 = 0101$, flipped is $1010$, plus one is $1011 = -5$.

A common mistake. It's tempting to think $-5$ is just $5$ with the top bit switched on, $1101$, because the top bit is "the sign bit." It isn't: $1101 = -8 + 4 + 1 = -3$. Turning on the top bit adds $-8$, it doesn't attach a minus sign. To negate, flip every bit and add 1.

It's modular arithmetic. The wheel is clock arithmetic, and that's no accident. A $k$-bit adder throws away the carry out of the top bit, so it adds mod $2^k$. Two's complement just names the residues $-2^{k-1}, \dots, 2^{k-1} - 1$ instead of $0, \dots, 2^k - 1$, and congruences don't care which names you use. So the same adder works for signed and unsigned numbers, and subtraction is $a - b = a + \overline b + 1$: the ALU inverts $b$ and sets the carry-in to 1. No separate subtractor needed.

Overflow. When the true answer leaves the range, it wraps around the wheel: in 8 bits, $127 + 1 = -128$. The tell is that adding two numbers with the same sign gives a result with the opposite sign. C defines unsigned arithmetic as arithmetic mod $2^k$, but overflowing a signed integer is undefined behavior, so careful firmware checks before it adds.

uint8_t a = 255;
a = a + 1;        // 0: unsigned math wraps mod 256
int8_t b = -5;    // stored as 1111 1011 (0xFB)
int16_t c = b;    // sign-extended to 0xFFFB, still -5

Sign extension. To widen a signed number, copy its sign bit into the new high bits: $1011$ ($-5$) becomes $1111\,1011$, still $-5$. Why does that keep the value? The top five 1s are worth $-128 + 64 + 32 + 16 + 8 = -8$, exactly what the old sign bit was worth on its own.

The 2038 problem. Unix systems count time as seconds since the start of 1970, traditionally in a signed 32-bit integer. It runs out at $2^{31} - 1 = 2{,}147{,}483{,}647$ seconds, at 03:14:07 UTC on 19 January 2038. One second later the bits wrap to $-2^{31}$, which reads as December 1901. Systems are moving to 64-bit time, which lasts about 292 billion years.

Every integer type in C, from int8_t to int64_t, is two's complement (C23 makes it official). That's why adding 1 to the largest int wraps to the most negative one, why sensor drivers have to sign-extend raw readings, and why the 2038 problem exists.