--- title: Integer Arithmetic module: Foundations moduleNumber: 0 lessonNumber: 3 order: 3 summary: > Fixed-width integer arithmetic is arithmetic modulo a power of two: add past the top and the result wraps. We work out unsigned and two's-complement addition and the rules that detect their overflow, why negation is a complement-plus-one, how multiplication truncates to the low-order bits and how compilers turn constant multiplies into shifts and adds, why C declares signed overflow undefined, and the bias fix that keeps shift-based signed division rounding toward zero. topics: [Foundations] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §2.3 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](/computer-architecture/foundations/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$: $$ u +^u_w v = (u + v) \bmod 2^w = \begin{cases} u + v & u + v < 2^w \quad \text{(normal)}, \\ u + v - 2^w & u + v \ge 2^w \quad \text{(overflow)}. \end{cases} $$ **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. $$ % caption: Unsigned addition on the mod-2^w circle (w=4, circumference 16). % caption: Adding 11 + 7 = 18 walks past the top and lands on 2; the result is % caption: smaller than both operands, the signature of unsigned overflow. \begin{tikzpicture}[font=\footnotesize, >=stealth] \definecolor{acc}{HTML}{2348F2} \def\R{2.2} \draw[black] (0,0) circle (\R); \foreach \p in {0,...,15} \node[black] at ({90-\p*22.5}:\R+0.32) {\p}; % start at 11 \fill[acc] ({90-11*22.5}:\R) circle (2.2pt); \node[text=acc, anchor=south east] at ({90-11*22.5}:\R) {start 11}; % arc 11 -> 18==2, sweeping clockwise 7 steps \draw[acc, very thick, ->] ({90-11*22.5}:\R-0.18) arc (90-11*22.5:90-18*22.5:\R-0.18); \fill[acc] ({90-2*22.5}:\R) circle (2.2pt); \node[text=acc, anchor=west] at ({90-2*22.5}:\R+0.85) {land 2}; \node at (0,0.32) {11 + 7 = 18}; \node at (0,-0.32) {18 mod 16 = 2}; \end{tikzpicture} $$ 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. > **Theorem (Unsigned overflow detection).** Let $s = u +^u_w v$. The addition > overflowed if and only if $s < u$ (equivalently, $s < v$). 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: ```c [uadd_check.c] /* 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 -^u_w 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. $$ % caption: Ripple addition of 1011 + 0111 (11 + 7, w = 4). Each column's carry % caption: feeds the next; the final carry-out has no column and is dropped, % caption: leaving 0010 = 2, the same wrap the circle showed. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east, text=acc] at (-1.6,1.65) {carries}; \node[text=acc] at (-0.85,1.65) {1}; \draw[acc] (-1.14,1.36) rectangle (-0.56,1.94); \foreach \i in {0, 1, 2} \node[text=acc] at (\i*0.85,1.65) {1}; \node[anchor=south, text=acc] at (-0.85,2.05) {dropped}; \node[anchor=east] at (-1.6,0.8) {11}; \foreach \i/\v in {0/1, 1/0, 2/1, 3/1} \node[bit] at (\i*0.85,0.8) {\v}; \node[anchor=east] at (-1.6,0) {+ 7}; \foreach \i/\v in {0/0, 1/1, 2/1, 3/1} \node[bit] at (\i*0.85,0) {\v}; \draw[black] (-1.5,-0.5) -- (3.0,-0.5); \foreach \i/\v in {0/0, 1/0, 2/1, 3/0} \node[bit, fill=acc!8] at (\i*0.85,-1.0) {\v}; \node[anchor=west] at (3.05,-1.0) {= 2, not 18}; \end{tikzpicture} $$ 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](/computer-architecture/digital-logic/multiplexers-decoders-and-the-alu); 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$: $$ u +^t_w v = \begin{cases} u + v - 2^w & u + v > TMax \quad \text{(positive overflow)}, \\ u + v & TMin \le u + v \le TMax, \\ u + v + 2^w & u + v < TMin \quad \text{(negative overflow)}. \end{cases} $$ 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.[^tadd] > **Definition (Signed overflow).** For $w$-bit two's-complement $u, v$, the sum > $u +^t_w v$ overflows iff $u, v$ have the same sign but the stored result has the > opposite sign. Positive overflow when $u + v > TMax$; negative overflow when > $u + v < TMin$. 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 = 1\,0100$; dropping the carry leaves $0100 = 4$. Two negatives produced a positive: **negative overflow**, off by $+16$ from $-12$. - $(-3) + 5$: $1101 + 0101 = 1\,0010$; 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: $$ % caption: True sums of two 4-bit signed operands span [-16, 14]. The middle % caption: window [-8, 7] is stored exactly; sums past TMax = 7 wrap down by 16 % caption: and sums below TMin = -8 wrap up by 16, landing with the wrong sign. \begin{tikzpicture}[font=\footnotesize, >=stealth] \definecolor{acc}{HTML}{2348F2} \fill[acc!8] (-5.76,-0.16) rectangle (-3.24,0.16); \fill[acc!18] (-2.88,-0.16) rectangle (2.52,0.16); \fill[acc!8] (2.88,-0.16) rectangle (5.04,0.16); \draw[->, thick] (-6.3,0) -- (6.0,0); \foreach \v in {-16, -8, 0, 7, 14} { \draw ({\v*0.36},0.09) -- ({\v*0.36},-0.09); \node[below] at ({\v*0.36},-0.13) {\v}; } \node[align=center] at (-0.18,0.85) {representable\\stored exactly}; \node[align=center, text=acc] at (-4.5,0.85) {negative overf\/low\\stored = sum + 16}; \node[align=center, text=acc] at (4.35,0.85) {positive overf\/low\\stored = sum - 16}; \end{tikzpicture} $$ 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. $$ -x = \;\sim\! x + 1. $$ 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$. ```c [negate.c] 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.[^ub] 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. ```c [signed_ub.c] #include /* 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. $$ (u \cdot v) \bmod 2^w = \big(T2U(u) \cdot T2U(v)\big) \bmod 2^w. $$ 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 $\bmod\ 2^w$. So a single multiply instruction serves both interpretations, just as one adder served both additions.[^tmul] 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$: $$ 14x = 8x + 4x + 2x = (x \ll 3) + (x \ll 2) + (x \ll 1). $$ $$ % caption: Computing 14 x 5 with no multiplier. Each left shift of x = 5 doubles % caption: it; the three shifted copies 40 + 20 + 10 sum to 70. In each row the % caption: set bits of 0000 0101 march left together. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=6.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.5,3.0) {x}; \foreach \i/\v in {0/0,1/0,2/0,3/0,4/0,5/1,6/0,7/1} \node[bit] at (\i*0.7,3.0) {\v}; \node[anchor=west] at (5.35,3.0) {= 5}; \node[anchor=east] at (-0.5,2.1) {x$<<$1}; \foreach \i/\v in {0/0,1/0,2/0,3/0,4/1,5/0,6/1,7/0} \node[bit] at (\i*0.7,2.1) {\v}; \node[anchor=west] at (5.35,2.1) {= 10}; \node[anchor=east] at (-0.5,1.2) {x$<<$2}; \foreach \i/\v in {0/0,1/0,2/0,3/1,4/0,5/1,6/0,7/0} \node[bit] at (\i*0.7,1.2) {\v}; \node[anchor=west] at (5.35,1.2) {= 20}; \node[anchor=east] at (-0.5,0.3) {x$<<$3}; \foreach \i/\v in {0/0,1/0,2/1,3/0,4/1,5/0,6/0,7/0} \node[bit] at (\i*0.7,0.3) {\v}; \node[anchor=west] at (5.35,0.3) {= 40}; \draw[black] (-1.3,-0.2) -- (6.3,-0.2); \node[anchor=east] at (-0.5,-0.7) {sum}; \foreach \i/\v in {0/0,1/1,2/0,3/0,4/0,5/1,6/1,7/0} \node[bit, fill=acc!8] at (\i*0.7,-0.7) {\v}; \node[anchor=west] at (5.35,-0.7) {= 70 = 14 x 5}; \end{tikzpicture} $$ 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.[^kmul] On x86-64 the compiler leans on `lea`, which computes $x + 2x$, $x + 4x$, or $x + 8x$ in a single address calculation: ```asm [mul14.s] 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](/computer-architecture/machine-level-x86-64/the-machines-view). 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. $$ % caption: Right-shifting 1011 0100 by 2. Logical shift feeds in zeros (treats the % caption: value as unsigned); arithmetic shift copies the sign bit, preserving a % caption: negative two's-complement value as it divides. \begin{tikzpicture}[font=\footnotesize, >=stealth, bit/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % original \foreach \i/\v in {0/1,1/0,2/1,3/1,4/0,5/1,6/0,7/0} \node[bit] at (\i*0.75,2.0) {\v}; \node[anchor=east] at (-0.55,2.0) {value}; % logical >> 2 : feed zeros at top \foreach \i in {0,1} \node[bit, draw=acc, text=acc] at (\i*0.75,0.7) {0}; \foreach \i/\v in {2/1,3/0,4/1,5/1,6/0,7/1} \node[bit] at (\i*0.75,0.7) {\v}; \node[anchor=east] at (-0.55,0.7) {logical}; % arithmetic >> 2 : copy sign bit (1) \foreach \i in {0,1} \node[bit, draw=acc, text=acc] at (\i*0.75,-0.6) {1}; \foreach \i/\v in {2/1,3/0,4/1,5/1,6/0,7/1} \node[bit] at (\i*0.75,-0.6) {\v}; \node[anchor=east] at (-0.55,-0.6) {arithmetic}; \end{tikzpicture} $$ 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.[^shift] ## 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$, $$ \frac{x}{2^k} \;\text{(toward zero)} = \left\lfloor \frac{x + (2^k - 1)}{2^k} \right\rfloor = (x + (2^k - 1)) \gg k, $$ 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$. $$ % caption: Dividing -7 by 4 (k = 2) in 8 bits. A bare arithmetic shift rounds % caption: down to -2, but C requires -1. Adding the bias 2^k - 1 = 3 before the % caption: shift carries the low bits across, and the shift lands on -1. \begin{tikzpicture}[font=\footnotesize, >=stealth, bit/.style={draw, minimum size=6mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[black] at (2.17,2.75) {bare shift}; \foreach \i/\v in {0/1,1/1,2/1,3/1,4/1,5/0,6/0,7/1} \node[bit] at (\i*0.62,2.05) {\v}; \node[anchor=west] at (4.75,2.05) {-7}; \draw[->, black] (2.17,1.65) -- (2.17,0.85); \node[anchor=west, black] at (2.35,1.25) {arith $>>$2}; \foreach \i/\v in {0/1,1/1,2/1,3/1,4/1,5/1,6/1,7/0} \node[bit] at (\i*0.62,0.45) {\v}; \node[anchor=west] at (4.75,0.45) {= -2 (down)}; \node[text=acc] at (9.37,2.75) {bias f\/irst}; \foreach \i/\v in {0/1,1/1,2/1,3/1,4/1,5/1,6/0,7/0} \node[bit, draw=acc] at (\i*0.62+7.2,2.05) {\v}; \node[anchor=west] at (11.95,2.05) {-7 + 3 = -4}; \draw[->, acc] (9.37,1.65) -- (9.37,0.85); \node[anchor=west, text=acc] at (9.55,1.25) {arith $>>$2}; \foreach \i/\v in {0/1,1/1,2/1,3/1,4/1,5/1,6/1,7/1} \node[bit, fill=acc!8] at (\i*0.62+7.2,0.45) {\v}; \node[anchor=west] at (11.95,0.45) {= -1 (toward 0)}; \end{tikzpicture} $$ 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. ```c [sdiv_pow2.c] /* 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 = \mathtt{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`.[^granlund] 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).[^granlund] The signed case adds the same toward-zero bias correction this lesson developed for powers of two. $$ % caption: Dividing x by 10 with no divide instruction. Multiply x by the magic % caption: constant 0x66666667 (about 2^35 / 10), take the high half of the % caption: product, and shift right; the result is floor(x / 10) exactly. \begin{tikzpicture}[font=\footnotesize, >=stealth, box/.style={draw, minimum width=26mm, minimum height=9mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box] (x) at (0,0) {dividend x}; \node[box, fill=acc!8] (mul) at (3.9,0) {x * 0x66666667}; \node[box] (shift) at (8.0,0) {high half,\\then $>>$ 3}; \node[box, draw=acc, text=acc] (res) at (12.0,0) {= f\/loor(x / 10)}; \draw[->] (x.east) -- (mul.west); \draw[->] (mul.east) -- (shift.west); \draw[->] (shift.east) -- (res.west); \end{tikzpicture} $$ 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. > **Takeaway.** Fixed-width integer arithmetic is arithmetic mod $2^w$. Unsigned > overflow wraps when the sum reaches $2^w$ (detect it with `u + v < u`); signed > overflow wraps when same-signed operands produce the opposite sign, and in C it > is undefined behavior — test against the limits _before_ adding. Negation is > $\sim\! x + 1$ (with $-TMin = TMin$); multiplication keeps the low $w$ bits, > identical signed or unsigned, and constant multiplies compile to shifts and adds. > Left shift multiplies; logical/arithmetic right shift divide unsigned/signed by > $2^k$, the signed case needing a $+(2^k{-}1)$ bias to round toward zero. 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](/computer-architecture/foundations/floating-point). [^tadd]: **Bryant & O'Hallaron**, _CS:APP_, §2.3.2 — Two's-Complement Addition: the same adder serves signed and unsigned, and the same-sign-in / opposite-sign-out overflow criterion. [^tmul]: **Bryant & O'Hallaron**, _CS:APP_, §2.3.4–2.3.5 — Multiplication: the low $w$ bits of a product agree for signed and unsigned operands; a single instruction suffices. [^ub]: **Bryant & O'Hallaron**, _CS:APP_, §2.3.2 — Two's-Complement Addition: the C standard leaves signed overflow unspecified; two's-complement wrapping is what most hardware does, not what the language promises. [^kmul]: **Bryant & O'Hallaron**, _CS:APP_, §2.3.6 — Multiplying by Constants: replacing constant multiplies with shifts, adds, and subtractions, including the run-of-ones form $(x \ll (n+1)) - (x \ll m)$. [^shift]: **Bryant & O'Hallaron**, _CS:APP_, §2.3.7 — Dividing by Powers of Two: logical vs. arithmetic right shift and the $2^k-1$ bias that makes signed division round toward zero. [^granlund]: **Granlund & Montgomery**, "Division by Invariant Integers using Multiplication," _PLDI_ 1994: the algorithm every mainstream compiler uses to replace division by a compile-time constant with a multiply-high and a shift, including the exact conditions on the magic constant $m$ and shift $s$ that make $\lfloor mx/2^s \rfloor = \lfloor x/d \rfloor$ over the whole input range.