Integer Arithmetic

A $w$-bit register has only $2^w$ states, so arithmetic that should produce a $(w+1)$-bit answer has nowhere to put the extra bit. The hardware simply drops it, and the result is arithmetic modulo $2^w$: numbers live on a circle of circumference $2^w$, and adding past the top wraps around to the bottom. This single fact — wrap-around — explains unsigned and signed overflow, complement-and-add-one negation, the low-order half of a product, and why a right shift is a division. Building on integer representation, this lesson works through the arithmetic the ALU actually performs.

Modular addition and unsigned overflow

For two unsigned values $u,v$ in $[0,2^w-1]$, the true sum $u+v$ may reach up to $2^{w+1}-2$, needing $w+1$ bits. The machine keeps only the low $w$, so the stored result is the true sum reduced modulo $2^w$:

Overflow is the second case: the true sum reached or passed $2^w$, the $(w+1)$th bit was discarded, and the stored value is $2^w$ too small.

Because the discarded bit is worth exactly $2^w$, a wrapped sum is always $2^w$ smaller than the true one, and that gives a detection rule requiring no extra width.

Both directions are one line. If there is no overflow, $s=u+v\ge u$ because $v\ge 0$. If there is, $s=u+v-2^w$, and since $v<2^w$ the correction drags $s$ below $u$. In C the test is safe to write after the addition, because unsigned arithmetic is defined to wrap:

/* unsigned overflow: the wrapped sum is smaller than either operand */
int uadd_overflows(unsigned u, unsigned v) {
  return u + v < u;     /* defined behavior: unsigned wraps mod 2^w */
}

Subtraction wraps in the mirrored direction. The difference $u{-}_w^{u}v$ is exact when $u\ge v$ and otherwise wraps up by $2^w$, so unsigned subtraction overflows (borrows) exactly when $u<v$. The classic casualty is len - 1 when len is zero: the result is $UMax$, and a loop bounded by it walks off the end of a buffer.

The carry chain, one column at a time

The wrap falls out of how the adder works. Binary addition proceeds column by column from the right, exactly like decimal long addition: column $i$ adds $a_i$, $b_i$, and the incoming carry $c_i$, emits the low bit of that count as the sum bit $s_i$, and passes the high bit along as $c_{i+1}$. The carry that emerges from the last column would be worth $2^w$, and a $w$-bit register has no column for it, so it is dropped. That dropped carry is the $-2^w$ in the overflow case above.

Every column here carries: $1+1$ in the ones column, then $1+1+1$, and so on up the chain. How fast that chain can run, and how hardware shortcuts it, is the subject of the ALU lesson; for now the point is that one adder circuit produces the modular sum, and the carry-out is a one-bit signal that a wrap happened.

Two's-complement addition and signed overflow

Two's complement lets the very same adder work for signed values. Add the bit patterns, drop the carry-out, and reinterpret the $w$ kept bits with $B2T$. The result equals the true sum unless it leaves the signed range $[TMin,TMax]$, in which case it wraps by $\pm 2^w$:

Signed overflow has a cleaner signature than the unsigned case: it can happen only when both operands share a sign, and it always produces a result of the opposite sign. Two positives summing to a negative is positive overflow; two negatives summing to a non-negative is negative overflow. Adding numbers of opposite sign can never overflow, since the true sum lies between them.¹

For example, consider three 4-bit additions. All three run through the same adder; only the diagnosis differs.

• $5+6$: $0101+0110=1011$, which reads as $-5$. Two positives produced a negative: positive overflow, off by $-2^4=-16$ from the true $11$.
• $(-6)+(-6)$: $1010+1010=10100$; dropping the carry leaves $0100=4$. Two negatives produced a positive: negative overflow, off by $+16$ from $-12$.
• $(-3)+5$: $1101+0101=10010$; dropping the carry leaves $0010=2$, which is correct. A carry-out occurred, yet no signed overflow: the carry-out flags unsigned wrap, and the two signals are independent.

That last case is worth dwelling on, because the hardware reports both. An x86 addition sets the carry flag CF (unsigned overflow) and the overflow flag OF (signed overflow) on every add, and the branch instruction chosen afterward decides which flag matters — the bits themselves carry no signedness. The true sum of two $w$-bit signed operands spans $[2\cdot TMin,2\cdot TMax]$, less than one full turn of the circle in each direction, so a single $\pm 2^w$ correction always lands the stored result back in range:

Unlike the unsigned case, C offers no safe after-the-fact test — by the time the sum exists, the behavior is already undefined, a point taken up below. The portable detection compares against the limits before adding: positive overflow occurs iff $v>0$ and $u>TMax-v$, negative iff $v<0$ and $u<TMin-v$, both computed entirely in range.

Negation: complement and add one

Because addition is modular, the negative of $x$ is whatever you add to reach $2^w\equiv 0$. That value is $2^w-x$, and there is a bitwise shortcut: flip every bit (which gives $\sim x=-x-1$, since $x+\sim x=UMax=2^w-1$) then add one.

At $w=4$: $5=0101$, complement $1010$, plus one $1011=-5$.

The one exception is $TMin$. Negating it should give $-TMin=2^{w-1}$, which exceeds $TMax$ and is not representable, so $-TMin$ wraps back to $TMin$ itself. This is the arithmetic shadow of the asymmetric range from the previous lesson: $\sim TMin+1=TMax+1=TMin$.

int x   = 5;          /* 0x00000005 */
int neg = ~x + 1;     /* 0xfffffffb == -5, same as -x */
int tmin = INT_MIN;   /* -2147483648 */
/* -tmin overflows back to INT_MIN: ~tmin + 1 == tmin */

Signed overflow is undefined in C, and compilers act on it

Everything above describes what the hardware does: x86-64 wraps signed sums exactly as it wraps unsigned ones. The C language makes a sharper distinction. Unsigned arithmetic is defined to wrap modulo $2^w$, which is why u + v < u was a legal test. Signed overflow is undefined behavior: the standard does not promise a wrap, an exception, or anything else, and a compiler is entitled to assume it never happens.²

That assumption has real consequences. Because x + 1 can never overflow in a program the compiler considers correct, the comparison x + 1 > x is always true for signed x, and optimizers fold it to the constant 1 — deleting exactly the guard a defensive programmer meant to write. Loop analyses lean on the same license: in for (int i = 0; i <= n; i++) the compiler may assume i never wraps, which lets it prove the loop terminates and vectorize it.

#include <limits.h>

/* looks like a wrap test; an optimizer may fold it to 0 */
int bad_check(int x) { return x + 1 < x; }

/* test BEFORE adding, using only in-range arithmetic */
int add_overflows(int u, int v) {
  if (v > 0) return u > INT_MAX - v;
  return u < INT_MIN - v;
}

The rule of thumb: on the machine, signed and unsigned addition are the same instruction; in C, they are different contracts. When wraparound is the intended behavior — hashes, checksums, sequence numbers — compute in unsigned and cast, keeping every operation on the defined side of the language.

Multiplication and the low-order truth

The full product of two $w$-bit numbers needs up to $2w$ bits, but a C multiplication that stores into a $w$-bit type keeps only the low $w$ bits. Those low $w$ bits are identical whether the operands are read as signed or unsigned. The high bits differ, but the part you keep does not.

The reason is that signed and unsigned values of the same bits differ only by multiples of $2^w$ (recall $T2U$ adds $2^w$ to negatives), and those multiples vanish under $\mathrm{mod}{2}^w$. So a single multiply instruction serves both interpretations, just as one adder served both additions.³ Because the kept half is taken mod $2^w$, a multiplication can silently overflow with no signal at all — a frequent source of buffer-size bugs when count * sizeof(elem) quietly wraps to a small allocation.

Multiplying by constants: shifts and adds

A hardware multiply has historically cost ten or more clock cycles against one for a shift or an add, and the gap has never fully closed. Compilers therefore rewrite x * K for a constant K as a short sequence of shifts, adds, and subtracts. The starting point is that a left shift multiplies by a power of two: x << k computes $x\cdot 2^k$ (for both encodings, since the low bits behave identically). Any constant then decomposes along its binary digits. Take $K=14=1110_2$:

Three operations replace one multiply, and a run of ones does even better. Since $1110_2=10000_2-10_2$, the same product is $14x=(x\ll 4)-(x\ll 1)$: two operations. In general each run of consecutive ones from bit $m$ up to bit $n$ contributes $(x\ll (n+1))-(x\ll m)$, so a constant like $60=111100_2$ costs two instructions no matter how long its run of ones.⁴ On x86-64 the compiler leans on lea, which computes $x+2x$, $x+4x$, or $x+8x$ in a single address calculation:

leaq    (%rdi,%rdi), %rax      # rax = 2x
salq    $4, %rdi               # rdi = 16x
subq    %rax, %rdi             # rdi = 16x - 2x = 14x

In this notation $ marks a constant and %rdi a register, syntax made precise in the machine-level module.

The reverse direction is harder: division by a constant is far slower in hardware (tens of cycles) and has no shift-and-add decomposition, though for powers of two a shift still works, as the next section shows.

Division by powers of two

Multiplication by $2^k$ is a left shift, x << k, appending $k$ zero bits; division by $2^k$ is a right shift, but the correct shift depends on signedness, and that is where the two right shifts diverge.

A logical right shift fills the vacated high bits with zeros, the correct behavior for unsigned division: u >> k computes $\lfloor u/2^k\rfloor$. An arithmetic right shift copies the sign bit into the vacated positions, preserving the sign of a two's-complement value. In C, right shift on an unsigned is logical and on a signed int is arithmetic.⁵

The rounding bias for signed division

Arithmetic right shift alone does not divide signed numbers correctly, because shifting rounds down (toward $-\infty$) while C integer division must round toward zero. For a non-negative dividend the two agree, but for a negative one they differ whenever the division is inexact: $-7/2$ should be $-3$, yet (-7) >> 1 rounds down to $-4$.

The fix is to bias a negative dividend up by $2^k-1$ before shifting, which nudges any negative inexact result up to the toward-zero answer. For $x<0$,

so the full expression for either sign is (x < 0 ? x + (1 << k) - 1 : x) >> k. Biasing a positive inexact dividend would over-round: $(5+3)\gg 2=2$, not $5/4=1$.

The bias is applied only when $x<0$; non-negative dividends already shift correctly. This is precisely the code a compiler emits for x / 2 when x is signed.

/* divide a signed int by 2^k, rounding toward zero like C's / */
int div_pow2(int x, int k) {
  int bias = (x >> 31) & ((1 << k) - 1);  /* bias = 2^k-1 if x<0, else 0 */
  return (x + bias) >> k;
}
/* div_pow2(-7, 1) == -3, matching (-7)/2; (-7)>>1 alone gives -4 */

The x >> 31 extracts the sign bit (all ones if negative, all zeros otherwise), so the bias is applied only to negative dividends — non-negative ones already shift correctly. With that one correction, a shift reproduces division exactly, which is why power-of-two divisors are the fastest case in any integer-heavy code.

Dividing by a non-power-of-two

CS:APP stops at powers of two, where a single shift suffices. But compilers turn every constant divisor into shifts and multiplies, not just the powers of two, and the technique is worth knowing because it explains why x / 10 compiles to no div instruction at all. The idea is multiply by a reciprocal: to divide by a constant $d$, precompute an integer approximation of $1/d$ scaled up by a power of two, multiply, then shift back down. Dividing by $10$, for instance, a compiler multiplies by the magic constant $\lceil 2^{35}/10\rceil =0x66666667$ and shifts the 64-bit product right by $35$ — equivalently, keeps the high 32 bits (a shift of $32$) then shifts $3$ more — which reproduces $\lfloor x/10\rfloor$ exactly for every 32-bit int.⁶

The reason this is exact and not merely close is a small theorem: for a divisor $d$ there exists a shift $s$ and a multiplier $m\approx 2^s/d$ such that $\lfloor x/d\rfloor =\lfloor mx/2^s\rfloor$ for all $x$ in range, and the error introduced by rounding $m$ up is absorbed by choosing $s$ large enough. Granlund and Montgomery worked out the exact conditions and the algorithm every compiler now uses (Granlund & Montgomery, Division by Invariant Integers using Multiplication, PLDI 1994).⁶ The signed case adds the same toward-zero bias correction this lesson developed for powers of two.

The payoff is a division replaced by a multiply and a shift — perhaps five cycles instead of twenty or more — for any divisor the compiler can see at compile time. The catch, and the reason x / n for a variable n stays slow, is that the magic constant depends on the divisor, so it can only be precomputed when the divisor is a literal. Performance-sensitive code that divides by the same runtime value many times sometimes computes the magic constant once by hand for exactly this reason.

These integer rules give exact answers within a fixed range. The next lesson trades that exactness for enormous range, encoding real numbers in floating point.