Math and Logic Refresher

This appendix collects the mathematical and logical background used throughout the book. Most readers will know much of it; the appendix exists so that any reader who needs to refresh a particular topic can do so without leaving the volume. The treatment is concise — for a deeper introduction, any standard discrete-mathematics text covers the same material at length.

01. Number Systems

Computers operate in binary. Humans usually think in decimal. Hexadecimal (base 16) is the working notation for engineers because each hex digit corresponds to exactly four binary bits, so hex compactly represents binary values without losing the bit-level structure.

Bases

A number written in base $b$ with digits $d_n d_{n-1} \ldots d_1 d_0$ has value:

$$\sum_{i=0}^{n} d_i \cdot b^i$$

For binary, $b = 2$ and digits are $\{0, 1\}$. For hex, $b = 16$ and digits are $\{0, 1, \ldots, 9, A, B, C, D, E, F\}$ where $A = 10$ through $F = 15$.

Examples:

• Binary 1011 = $1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 1 \cdot 1 = 11$ in decimal.
• Hex 2F = $2 \cdot 16 + 15 = 47$ in decimal.
• Hex FF = $15 \cdot 16 + 15 = 255$.
• Hex 100 = 256; 1000 = 4096; 10000 = 65,536.

Common Conventions

In this book and most code:

• Binary is written with prefix 0b (e.g., 0b1011) or with subscript ($1011_2$).
• Hex is written with prefix 0x (e.g., 0x2F) or with subscript ($2F_{16}$).
• Decimal has no prefix.

In assembly, hex sometimes uses suffix h (Intel: 0FFh) or prefix $ (Motorola).

Conversions

Binary to hex: group from the right in 4-bit chunks; each chunk is one hex digit.

Hex to binary: expand each hex digit to 4 bits.

Decimal to binary: repeatedly divide by 2; the remainders read in reverse give the binary representation.

Binary to decimal: sum powers of 2 corresponding to set bits.

Powers of 2 to Memorize

Note the IEC distinction: KiB = $2^{10}$ = 1024 bytes; KB sometimes means $10^3$ = 1000 bytes (storage marketing). Memory and cache sizes always use binary (KiB/MiB), even when written as "KB"/"MB".

02. Two's Complement

Computers represent signed integers in two's complement. In an $n$-bit two's complement representation:

• The most significant bit has weight $-2^{n-1}$ (negative).
• Other bits have positive weights.
• The range is $[-2^{n-1}, 2^{n-1} - 1]$.

For 8-bit:

Computing Negation

To negate a two's complement number: invert all bits, then add 1.

Verify: $-128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = -5$. ✓

Why Two's Complement

The same hardware adder works for unsigned and signed addition; the result is the correct two's complement value (modulo $2^n$). Subtraction is just adding the negation. Only one representation of zero. These properties make two's complement universal in modern hardware.

Sign Extension and Zero Extension

When extending a smaller value to a larger width:

• Zero-extend: pad with zeros on the left (preserves unsigned value).
• Sign-extend: pad with copies of the MSB on the left (preserves signed value).

x86-64 has explicit MOVZX (zero) and MOVSX (sign) instructions; AArch64 has UXTB/SXTB etc. RISC-V has LB (sign-extend) and LBU (zero-extend).

Overflow

Two's complement addition overflows when the result has a different sign than both inputs (and the inputs have the same sign).

• Positive + positive = negative → overflow.
• Negative + negative = positive → overflow.
• Positive + negative → no overflow possible.

Hardware sets a flag (V on x86, V on ARM); on RISC-V there is no flag, so signed-overflow detection is done with a comparison.

03. Boolean Algebra

Digital logic is built on Boolean algebra over $\{0, 1\}$.

Basic Operators

Identities

Commutative: $A + B = B + A$; $A \cdot B = B \cdot A$.

Associative: $A + (B + C) = (A + B) + C$.

Distributive: $A \cdot (B + C) = A \cdot B + A \cdot C$.

Identity: $A + 0 = A$; $A \cdot 1 = A$.

Annihilator: $A + 1 = 1$; $A \cdot 0 = 0$.

Idempotent: $A + A = A$; $A \cdot A = A$.

Complement: $A + \overline{A} = 1$; $A \cdot \overline{A} = 0$.

Double negation: $\overline{\overline{A}} = A$.

De Morgan's Laws

$$\overline{A \cdot B} = \overline{A} + \overline{B}$$ $$\overline{A + B} = \overline{A} \cdot \overline{B}$$

These convert AND to OR and vice versa under negation. Heavily used in simplifying logic and reasoning about predicates in code.

Bit-level Operations in Code

In C/C++/Rust/Java/Go, bitwise operators work on integer types element by element:

• & AND
• | OR
• ^ XOR
• ~ NOT
• << shift left
• >> shift right (arithmetic for signed, logical for unsigned in C; language-dependent)

Common idioms:

04. Sets and Functions

Sets

A set is an unordered collection of distinct elements, written $\{a, b, c\}$. Operations: union $\cup$, intersection $\cap$, difference $\setminus$, complement.

Cardinality $|A|$ is the number of elements. Power set $\mathcal{P}(A)$ has $2^{|A|}$ elements.

Functions

A function $f: A \to B$ maps each element of $A$ to exactly one element of $B$. Important properties:

• Injective (one-to-one): different inputs give different outputs.
• Surjective (onto): every output is hit by some input.
• Bijective: both injective and surjective; has an inverse.

Hash functions in caches and translation lookaside buffers are non-bijective: many inputs map to the same output (collisions). Designing the hash to distribute inputs uniformly is important for cache performance.

05. Combinatorics for Architecture

Counting Principles

Multiplication rule: if there are $a$ ways for one event and $b$ ways for another, there are $a \cdot b$ ways for both.

Addition rule: if events are mutually exclusive, count separately and add.

A 4-way set-associative cache with 1024 sets has $1024 \cdot 4 = 4096$ entries.

Permutations and Combinations

Permutations (order matters): $P(n, k) = \frac{n!}{(n-k)!}$.

Combinations (order doesn't matter): $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

For the birthday paradox (relevant to hash collisions): in a set of $n$ items, the expected number of trials before a collision is roughly $\sqrt{n \cdot \pi / 2}$. For a 32-bit hash, expect a collision after roughly $2^{16}$ insertions.

Pigeonhole Principle

If $n+1$ items are placed in $n$ buckets, at least one bucket has 2 or more items. Useful for proving cache-conflict guarantees.

06. Probability for Architecture

Basic Probability

For a discrete event with possible outcomes $1, \ldots, k$ with probabilities $p_i$ (summing to 1), the expected value of a quantity $X$ is:

$$E[X] = \sum_i p_i \cdot X_i$$

Branch prediction and cache behavior are analyzed in expectation.

Cache Hit/Miss

If the hit ratio is $h$ and a hit costs $T_{\text{hit}}$ while a miss costs $T_{\text{miss}}$, the average memory access time is:

$$\text{AMAT} = h \cdot T_{\text{hit}} + (1-h) \cdot T_{\text{miss}}$$

For a multi-level cache:

$$\text{AMAT} = T_{L1} + (1 - h_{L1}) \cdot (T_{L2} + (1 - h_{L2}) \cdot (T_{L3} + (1 - h_{L3}) \cdot T_{\text{mem}}))$$

Branch Prediction Accuracy

If the branch is correctly predicted with probability $p$ and mispredicting costs $C$ cycles, the expected penalty per branch is $(1 - p) \cdot C$. For typical $C = 15$ and $p = 0.97$, the expected penalty is $0.45$ cycles per branch.

Geometric Distribution

The expected number of trials to get a single success when each trial has probability $p$ is $1/p$. Used in modeling rare events (TLB miss after how many memory accesses, etc.).

Independence

Events $A$ and $B$ are independent if $P(A \cap B) = P(A) \cdot P(B)$. In real workloads, cache misses and branch mispredicts are often correlated (both happen on irregular access patterns), so naive independence assumptions are optimistic.

07. Asymptotic Notation (Big-O)

Used to describe how cost scales with input size $n$.

• $O(f(n))$: upper bound. The actual cost grows no faster than $f(n)$ asymptotically.
• $\Omega(f(n))$: lower bound.
• $\Theta(f(n))$: tight bound (both upper and lower).

Common growth rates, in increasing order:

$$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

For computer architecture analysis:

• Cache size scaling: a fully-associative LRU cache has $O(n)$ tag-comparison cost per access.
• Set-associative cache: $O(\text{ways})$ comparisons per access (constant w.r.t. cache size).
• TLB walk: $O(\text{levels})$ memory accesses (4-5 in modern systems).
• Sorting (relevant to data layout for cache): merge sort is $O(n \log n)$ in time but $O(n)$ in extra space; in-place quicksort is also $O(n \log n)$ on average.

Constants Matter in Practice

Big-O ignores constants, but architecture is largely about constants. An $O(n)$ algorithm that does cache-friendly sequential access can outperform a "better" $O(n / \log n)$ algorithm that pointer-chases through memory. Cache-aware analysis (the external memory model and the cache-oblivious model) is the formal way to capture this — counting cache-line transfers rather than just operations.

08. Logarithms and Exponentials

For computer architecture, base-2 logarithms dominate.

$$\log_2(2^k) = k$$

A cache with $S$ sets needs $\log_2 S$ index bits. A 4 KiB page (4096 = $2^{12}$ bytes) has 12 offset bits.

The change of base identity: $\log_b x = \log_a x / \log_a b$.

For asymptotic analysis the base doesn't matter (logs in different bases differ only by a constant), so we usually write $O(\log n)$ without specifying base.

09. Summary

This appendix has reviewed:

• Number systems: binary, decimal, hex; conversions; common powers of 2.
• Two's complement: representation, negation, sign extension, overflow.
• Boolean algebra: operators, identities, De Morgan's laws, bit-level idioms.
• Sets, functions, combinatorics, the pigeonhole principle.
• Probability: expected values, AMAT, branch-prediction penalty.
• Asymptotic notation: big-O and where constants matter.
• Logarithms.

These are the recurring tools in architectural analysis. Specific applications appear throughout the book: cache analysis (Ch 18-19), branch prediction (Ch 24, 51), TLB hierarchy (Ch 17), instruction encoding (Ch 11-15), and microarchitecture timing (Part V).