Chapter F.1: How a Computer Computes§

Authors: Shrey Patel and Jay Patel, Coconut Labs
Book: Think Like an OS (see book/00-INDEX.md)

This chapter builds the mental machine that every later chapter runs on. By the end you will read 0xdeadbeef as casually as you read a phone number, know why -1 and 255 are the same eight bits, build an adder out of logic gates on paper, and hand-execute a three-instruction computer, the same fetch-decode-execute loop that a real CPU runs billions of times per second. Nothing here requires prior hardware exposure. If you write JavaScript, Python, or Swift for a living and have never thought about what is underneath the runtime, this is the floor of the building, unfolded slowly.

The problem§

Every chapter after this one describes software in terms of a machine: registers, addresses, instruction pointers, interrupts, page tables. If those words are fuzzy, the later material reads as incantation. "The kernel saves the userspace registers into pt_regs" is a plain, almost boring sentence. It stays plain only if you already know what a register is, why there is a program counter, and why memory is a flat run of numbered bytes that holds code and data with no distinction between them.

There is also a practical, daily payoff. Hex dumps, bitmask flags, wraparound bugs, "why is this negative number huge when I cast it": all of these are two's complement and base-16 fluency, nothing more. Engineers lose real debugging hours to gaps this chapter closes in an afternoon.

Both destinations this book serves stand on this floor. If you are heading for kernel work, the words below (register, program counter, address, fixed-width integer) are the words the source tree is written in, and you cannot read pt_regs without them. If you are heading for low-latency or trading systems, your day involves binary wire formats where a value is a fixed-width integer packed into a known number of bytes, and counters that wrap at 2^n instead of growing forever. The floating-point section below is deliberately one paragraph, and the reason it is short matters to both of you.

So this chapter answers one question thoroughly: what is a computer, mechanically, at the layer just above physics? Everything else in the book is a consequence of the answer.

Unfolded§

Information is bits; hex is just shorthand§

A bit is the smallest possible unit of information: one of two states. Call them 0 and 1, off and on, low voltage and high voltage. The physics does not matter yet, only that there are exactly two states and the hardware can tell them apart reliably.

One bit alone can distinguish two things. Bits in a row multiply: two bits give four combinations, three give eight, and in general n bits give 2^n combinations. Eight bits grouped together form a byte, which gives 2^8 = 256 combinations. The byte is the unit memory is addressed in: when we say a machine has 16 GB of RAM, we mean roughly 16 billion individually numbered bytes.

Binary numbers work exactly like decimal numbers, just with place values that are powers of 2 instead of powers of 10. In decimal, 237 means 2×100 + 3×10 + 7×1. In binary, 1101 means 1×8 + 1×4 + 0×2 + 1×1 = 13.

Binary is what the machine uses, but it is miserable for humans: too many digits, too easy to misread. Hexadecimal (base 16) fixes this with one clean trick: 16 is 2^4, so one hex digit corresponds to exactly four bits. Convert each group of four bits independently, and you are done. No such clean grouping exists for decimal, which is why systems programmers write hex, not decimal.

The sixteen hex digits are 0 to 9, then a to f:

HexBinaryDecimalHexBinaryDecimal
000000810008
100011910019
200102a101010
300113b101111
401004c110012
501015d110113
601106e111014
701117f111115

The 0x prefix means "what follows is hex." So 0xdeadbeef, a classic filler value programmers use to mark memory, decodes four bits at a time:

  d    e    a    d    b    e    e    f
1101 1110 1010 1101 1011 1110 1110 1111

Eight hex digits, 32 bits, decimal value 3,735,928,559. You never need to know the decimal value; the point of hex fluency is that 0xff is "all eight bits set," 0x80 is "just the top bit," and 0xdeadbeef is eight nibbles you can decode on sight. A nibble, genuinely the technical term, is four bits, half a byte.

Unsigned integers, and what overflow really is§

An unsigned integer treats all its bits as plain place value. Eight bits span 0 to 255, sixteen bits span 0 to 65,535, thirty-two bits span 0 to 4,294,967,295. Nothing is reserved for a sign.

Here is the crucial mental shift: hardware integers are not math integers. Math integers go on forever. An 8-bit register is a ring of 256 positions. Compute 255 + 1 in eight bits and you get a ninth bit that has nowhere to live; the hardware keeps the low eight bits and the answer is 0. This is overflow, and the resulting behavior is wraparound: arithmetic modulo 2^n, like a clock face with 256 hours.

Wraparound is not a malfunction. The circuit did exactly what it is built to do. Whether it is a bug depends on whether your program expected it. The C language even codifies the split: unsigned arithmetic is defined to wrap modulo 2^n, while signed overflow is undefined behavior the compiler may assume never happens. That asymmetry causes real security bugs and gets a full treatment in a later chapter; for now, hold on to the ring.

(Python deliberately hides this: its integers grow without bound, which is why Python programmers can go years without meeting overflow. The lab makes the ring visible from Python anyway, with masking.)

Two's complement: one adder to rule both signs§

Now, negative numbers. We have bit patterns and we need to decide which patterns mean which negative values. This is pure convention; the bits do not care. History tried three of them.

Sign-magnitude is the one you would invent first: reserve the top bit as a sign flag, use the rest as the magnitude. It has two ugly problems. First, there are two zeros (0000 and 1000 in four bits: +0 and −0). Second, and fatally, you cannot just feed these patterns into an adder. Try 3 + (−3) in four bits: 0011 + 1011 = 1110, which reads as −6. Wrong. Sign-magnitude hardware needs separate compare-and-subtract circuitry that inspects signs before every operation.

One's complement negates by flipping every bit. It is nearly as old and nearly as awkward: still two zeros (0000 and 1111), and the adder needs an "end-around carry" correction step.

Two's complement won, and the rule is: to negate a number, flip every bit, then add 1.

  5      = 0101
  flip   = 1010
  add 1  = 1011   ← this is -5

Equivalently: the top bit's place value is negative. In four bits, 1011 = −8 + 0 + 2 + 1 = −5. Same answer, one convention. The full 4-bit table:

BitsUnsignedTwo's complement
000000
000111
.........
011177
10008−8
10019−7
101010−6
101111−5
110012−4
110113−3
111014−2
111115−1

Notice: one zero, not two. The range is asymmetric (−8 to +7 in four bits; −128 to +127 in eight) because the negative side got the pattern that would have been −0. And 1111...1 is always −1, which is why casting −1 to unsigned yields the maximum value. That is a bug pattern you have probably already met.

Why did this convention win? Because of the adder. Two's complement is exactly "unsigned arithmetic modulo 2^n, with the top half of the ring relabeled as negatives." Since wraparound arithmetic doesn't care how you label the positions, one ordinary binary adder produces correct results for signed and unsigned values alike: no sign-checking logic, no second circuit, no correction step. Watch 6 + (−3) in four bits:

   0110      6
 + 1101     -3   (two's complement of 3)
 ------
  10011
  ^ carry out of the top - the hardware drops it
   0011  =  3   ✓

Subtraction becomes "flip the bits of the second operand, add, and feed in a carry of 1," which is a handful of extra gates bolted onto the same adder. When every gate was an expensive vacuum tube or transistor, halving the arithmetic circuitry was decisive.

The history matches the logic. John von Neumann's 1945 First Draft of a Report on the EDVAC, the paper that laid out the stored-program computer we will meet below, already specified two's complement arithmetic precisely because it simplified subtraction. Rival conventions survived for two decades in real machines (the CDC 6600 used one's complement; early IBM scientific machines used sign-magnitude), but IBM's System/360 in 1964 standardized on two's complement, and its market dominance made that the industry default. The endgame: the C standard, which for decades permitted all three representations, dropped the pretense. C23 requires two's complement for signed integers, matching every processor that matters (x86, ARM, RISC-V).

Floating point exists (a paragraph, not a chapter)§

Fractions and huge magnitudes use a different representation entirely: floating point, standardized as IEEE 754 (first published 1985, revised in 2008 and 2019). A float is scientific notation in binary: one sign bit, some exponent bits, some fraction bits. That is 1/8/23 in the 32-bit format, 1/11/52 in the 64-bit format that JavaScript numbers and Python floats use. The one thing to carry forward now: floats are approximations with their own rounding rules, which is why 0.1 + 0.2 != 0.3 in every language that defaults to binary floating point (JavaScript, Python, Swift, C…), and why nothing in a kernel's bookkeeping ever touches a float. Addresses, sizes, counters, permissions are all integers, and integers rule below the application layer. If you need a computation to reproduce bit for bit across machines and runs, that same rounding is the reason integer arithmetic keeps winning. A later chapter unfolds IEEE 754 properly.

From switches to logic gates§

Drop down one level. All of the arithmetic above is performed by circuits, and circuits are built from transistors, electrically controlled switches. A voltage on a control terminal decides whether current flows between two others. That is all the physics this book needs: a switch controlled by another signal, and modern chips have billions of them.

Wire a few transistors together and you get a logic gate: a tiny circuit computing a fixed function of one or two input bits.

| A | B | AND | OR | XOR | | A | NOT |
|---|---|-----|----|-----|-|---|-----|
| 0 | 0 | 0 | 0 | 0 | | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | | | |
| 1 | 1 | 1 | 1 | 0 | | | |

In words: AND fires when both inputs are 1. OR fires when at least one is. XOR ("exclusive or") fires when exactly one is, which is the same as saying the inputs differ. NOT flips its single input. These compose like functions, and from AND/OR/NOT (in fact from NAND alone, AND's negation) you can build every digital circuit that exists, including the machine running this sentence. The rest of this section builds one honest piece of it.

Adding with gates: half adder, full adder, ripple carry, ALU§

Add two one-bit numbers. The possible results are 0, 1, or 2, and 2 in binary is 10, two output bits. Call them sum (the low bit) and carry (the high bit). Stare at the truth table and two gates fall out: the sum column is XOR, the carry column is AND.

            ┌─────┐
  A ────┬───┤     │
        │   │ XOR ├──── Sum    (A differs from B)
  B ──┬─┼───┤     │
      │ │   └─────┘
      │ │   ┌─────┐
      │ └───┤     │
      │     │ AND ├──── Carry  (both A and B are 1)
      └─────┤     │
            └─────┘

This is a half adder. It is "half" because it cannot accept a carry coming in from a lower bit position, and multi-bit addition needs exactly that, the same way grade-school column addition carries a 1 leftward. A full adder takes three inputs (A, B, carry-in) and produces sum and carry-out. Build it from two half adders plus an OR:

         ┌────────────┐  sum1                ┌────────────┐
  A ─────┤ half adder ├─────────────────────┤            │
  B ─────┤     #1     │           Cin ──────┤ half adder ├──── Sum
         └─────┬──────┘                     │     #2     │
               │ carry1                     └─────┬──────┘
               │                                  │ carry2
               │              ┌────┐              │
               └──────────────┤ OR ├──────────────┘
                              │    ├──── Cout
                              └────┘

(The OR is safe because at most one of the two internal carries can fire for any input combination.)

Now the payoff move, the one that turns gates into arithmetic: chain full adders, one per bit, each one's carry-out feeding the next one's carry-in. This is a ripple-carry adder, here 4 bits wide:

     A3 B3         A2 B2         A1 B1         A0 B0
      │ │           │ │           │ │           │ │
     ┌┴─┴──┐  C3   ┌┴─┴──┐  C2   ┌┴─┴──┐  C1   ┌┴─┴──┐
C4 ──┤ FA  ├───────┤ FA  ├───────┤ FA  ├───────┤ FA  ├── Cin = 0
     └──┬──┘       └──┬──┘       └──┬──┘       └──┬──┘
        S3            S2            S1            S0

The carry "ripples" from bit 0 leftward, exactly like your pencil does. Widen it to 64 full adders and you add 64-bit numbers. (Real CPUs use cleverer carry circuits because rippling through 64 stages is slow, but the ripple version is the honest conceptual core.) And recall the two's complement section: this same circuit does signed addition for free, and subtraction with a row of NOT gates and Cin = 1.

The final leap: put an adder, a subtractor path, AND/OR/XOR applied bit-by-bit across the width, and shift circuits side by side; feed all of them the same two inputs; use a few selector bits to choose which result to output. That box is the ALU (arithmetic logic unit), the part of the CPU that computes. The selector bits will shortly have another name: part of an instruction.

If you followed the chain from XOR to full adder to ripple carry to ALU, you built arithmetic out of switches with no step taken on faith. Nothing between here and the addq instruction you will read in Chapter F.2 is deeper than what you just did.

State: flip-flops, registers, and the clock§

Gates compute but cannot remember. Outputs track inputs, and when inputs vanish, so do outputs. A computer needs memory, and the trick is feedback: cross-couple two gates so each one's output feeds the other's input, and the pair settles into one of two stable, self-reinforcing states. It holds a bit. Add a bit of steering logic so the stored bit can be overwritten on command and you have a flip-flop: a 1-bit memory cell.

A register is a row of flip-flops written and read as a unit: 64 flip-flops make one 64-bit register. A CPU keeps a small set of them (x86-64 has 16 general-purpose integer registers, plus special ones) as its working values: the numbers currently being computed on, an address about to be accessed. Registers are the fastest storage in the machine precisely because they live inside the CPU, wired directly to the ALU.

What keeps millions of flip-flops from updating chaotically is the clock: a signal ticking at a fixed rate, with all state updates synchronized to its tick. Between ticks, values flow through gate networks (like the ripple-carry adder) and settle; on the tick, registers capture the settled results, which become inputs for the next interval. A "3 GHz" processor has a clock ticking 3 billion times per second: three billion machine-wide state updates per second, with modern cores typically finishing one or more instructions per tick. That number is the exchange rate between human time and machine time, and it is worth feeling. In the ~16 milliseconds of one animation frame, a 3 GHz core ticks about 48 million times. If your work is measured in microseconds rather than frames, it is the same exchange rate, counted in thousands of ticks instead of millions.

The von Neumann machine: fetch, decode, execute§

Assemble the pieces. We have an ALU (computes), registers (fast state), and main memory: a flat sequence of numbered bytes, scaled far up and built from denser cells than flip-flops. A byte's number is its address. An address is an integer, so addresses can themselves be stored, added to, and passed around like any other number. Half of systems programming, and every pointer you will ever meet, is downstream of that one property.

The architecture nearly every real computer follows is the von Neumann model, after the 1945 EDVAC report: programs are stored in the same memory as data, encoded as bytes. An instruction ("add these," "load that") is a byte pattern, sitting in the same address space as your strings and spreadsheets, readable and writable by the same mechanisms.

  ┌─────────────────────┐
  │         CPU         │
  │  ┌───────────────┐  │  addresses  ┌───────────────────────┐
  │  │ registers     │  │────────────▶│        MEMORY         │
  │  │  A, PC, ...   │  │             │  one flat run of      │
  │  ├───────────────┤  │    data     │  numbered bytes,      │
  │  │ ALU           │  │◀───────────▶│  code AND data live   │
  │  │ control unit  │  │             │  here, identically    │
  │  └───────────────┘  │             └───────────────────────┘
  └─────────────────────┘

One special register makes the stored program run: the program counter (PC, called the instruction pointer on x86). It holds the address of the next instruction. The CPU's control unit loops forever:

        ┌──────────────────────────────────────────────┐
        │                                              │
        ▼                                              │
  ┌───────────┐      ┌────────────┐      ┌──────────┐  │
  │   FETCH   │─────▶│   DECODE   │─────▶│ EXECUTE  │──┘
  │ read the  │      │ which op?  │      │ do it;   │
  │ bytes at  │      │ which      │      │ advance  │
  │ PC        │      │ operands?  │      │ the PC   │
  └───────────┘      └────────────┘      └──────────┘

That is the whole secret. There is no interpreter underneath, no smaller turtle. A CPU is a fetch-decode-execute loop implemented in gates and driven by the clock.

Make it concrete with a toy machine you can run on paper. It has one register A, a PC, and 32 bytes of memory. Every instruction is two bytes: an opcode, then an address operand.

OpcodeNameMeaning
01LOADA ← mem[addr]
02ADDA ← A + mem[addr]
03STOREmem[addr] ← A

The program "add the numbers at addresses 0x10 and 0x11, store the result at 0x12" assembles to six bytes at addresses 0 to 5, with the data placed further up:

addr:  00 01 02 03 04 05 ...  10 11 12
byte:  01 10 02 11 03 12 ...  07 05 00
       └─LOAD─┘└─ADD──┘└STORE┘  7  5  (result)

Execute it, one loop iteration per row:

StepPCFetchedDecodedEffectA afterPC after
1001 10LOAD 0x10A ← mem[0x10] = 772
2202 11ADD 0x11A ← 7 + mem[0x11] = 12124
3403 12STORE 0x12mem[0x12] ← 12126

Afterward, mem[0x12] holds 0c, twelve. Real machines differ from this toy only in scale and encoding density: more registers, hundreds of opcodes, variable-length instructions, plus instructions that write the PC itself. That last one is all a jump, branch, or function call is. Assign to the PC and you have control flow.

Code is data§

One consequence of the stored-program design deserves its own flag, because three later chapters grow out of it. Look at the memory dump above: nothing marks bytes 0 to 5 as "code." 01 10 is LOAD only because the PC passed through address 0. Point the PC at your data and the machine will cheerfully decode your data; store bytes into memory and then jump to them, and you have manufactured code at runtime.

Everything interesting about this cuts both ways. It is why a loader works: running a program is copying bytes from a file into memory and aiming the PC at them. It is why JIT compilers work: V8 and the JVM write machine code into buffers mid-run and jump to it, a program creating a faster program from inside itself. And it is why classic exploits work: if an attacker can get their bytes into memory and bend the PC toward them, the machine executes the attacker's program with the victim's privileges. Modern defenses (no-execute page permissions, W^X policies) exist to re-impose, by force, the code/data distinction that von Neumann machines natively lack. A later chapter unfolds that arms race; for now, hold the symmetry: the same property powers the loader, the JIT, and the exploit.

The real thing in Linux§

Every abstraction in this chapter has a literal file in the Linux 6.12-era tree.

To watch bytes decode into instructions on your own machine: otool -tv /bin/ls on macOS, or objdump -d /bin/ls in a Linux container, prints each instruction's bytes next to its decoded meaning. That is the DECODE stage of the loop, run offline for your eyes.

Coconut tie-in§

Coconut OS is a Linux 6.12 fork, so this chapter's objects are the project's raw material: the agent_* syscalls at numbers 472 to 479 are reached by placing a plain integer in a register before entering the kernel, and the saved pt_regs from this chapter is how the kernel sees the caller's state. The audit pipeline (04-HLD) hash-chains byte sequences exactly as this chapter describes them, and the capability work lives or dies on bit-level flag handling in u32/u64 fields. If you can hand-execute the toy machine, kernel entry code stops being magic.

Lab§

Runs directly on a macOS host (any recent macOS ships python3 with the Xcode Command Line Tools; zsh and printf are built in). Everything works identically inside a Docker Linux container if you prefer. QEMU is not needed. Format is red-then-green: write your prediction down before running each command.

Drill 1: hex and binary, predict-then-check§

For each line, predict the output, then run it.

sh
python3 -c "print(bin(0xa5))"
python3 -c "print(hex(0b11011110))"
python3 -c "print(0xdeadbeef)"
python3 -c "print(hex(3735928559))"
python3 -c "print(format(0xdeadbeef, '032b'))"
printf '%x\n' 255

Expected:

0b10100101
0xde
3735928559
0xdeadbeef
11011110101011011011111011101111
ff

Check your 0xdeadbeef binary prediction nibble by nibble against the table in this chapter. If any drill surprised you, decode it by hand before moving on.

Drill 2: two's complement§

Python integers are arbitrary-precision, so Python shows negatives with a minus sign rather than as raw two's complement. Masking with & 0xff forces a value into an 8-bit ring, which is exactly what real 8-bit hardware does implicitly. Predict each output first.

sh
python3 -c "print(bin(-1 & 0xff))"
python3 -c "print(hex(-16 & 0xff))"
python3 -c "print(bin(-5 & 0xf))"
python3 -c "v = 0b1011; print(v - 16 if v & 0b1000 else v)"

Expected:

0b11111111
0xf0
0b1011
-5

The last two are inverses: line 3 encodes −5 into four bits, line 4 decodes four bits back to −5 (by applying the "top bit is worth −2^(n−1)" rule).

Drill 3: wraparound§

Predict, then run. All arithmetic is on the 8-bit ring.

sh
python3 -c "print((250 + 10) & 0xff)"
python3 -c "print((127 + 1) & 0xff)"
python3 -c "v = (127 + 1) & 0xff; print(v - 256 if v & 0x80 else v)"

Expected:

4
128
-128

The last line is the classic signed-overflow surprise: 127 + 1 = −128 when eight bits are read as two's complement. Same bits, two readings.

Drill 4: paper-execute the toy machine§

On paper, execute this memory image with the three-instruction machine from this chapter (01=LOAD, 02=ADD, 03=STORE; PC starts at 0; execution stops when PC reaches 6). Write the full trace table before running the checker: PC, fetched bytes, decoded meaning, A, memory changes.

addr:  00 01 02 03 04 05 ...  10 11 12
byte:  01 11 02 10 02 10 ...  09 04 00

Then check yourself with an 11-line Python implementation of the machine:

python
mem = [0] * 32
mem[0:6] = [0x01, 0x11, 0x02, 0x10, 0x02, 0x10]
mem[0x10], mem[0x11] = 9, 4
a, pc = 0, 0
while pc < 6:
    op, arg = mem[pc], mem[pc + 1]
    if op == 0x01: a = mem[arg]              # LOAD
    elif op == 0x02: a = (a + mem[arg]) & 0xff  # ADD
    elif op == 0x03: mem[arg] = a            # STORE
    pc += 2
print("A =", a)

Expected:

A = 22

(The program loads 4, then adds 9 twice.) Note what the checker is: a fetch-decode-execute loop in eleven lines. You have now implemented a von Neumann machine. Two extensions worth trying: add opcode 04 = "JUMP: pc ← arg, skipping the normal advance" and write a loop; then point the initial PC at 0x10 and predict what happens when the machine decodes your data. That second one turns the "code is data" section from a claim you read into an experiment you ran.

Optional: a real gate-level build§

The Nand2Tetris project (https://www.nand2tetris.org, companion to The Elements of Computing Systems by Noam Nisan and Shimon Schocken) provides a free hardware simulator, including a browser-based IDE, in which you build the gates, the adder, the ALU, the registers, and finally a working CPU from NAND up. Projects 1 to 3 cover this chapter's hardware content hands-on; the software tools page is https://www.nand2tetris.org/software.

Bridge notes§

If you have taken microprocessor and digital-logic coursework, this chapter is a vocabulary refresher, not new material. Skim the Unfolded section headings and move on, with three exceptions worth a slower pass. First, "The real thing in Linux": the mapping from coursework concepts to actual 6.12-tree files (pt_regs's ip field as the saved program counter; int-ll64.h as the kernel's fixed-width vocabulary) is book-specific plumbing later chapters lean on. Second, the C-standard framing in the overflow discussion is newer than most coursework and matters for kernel code review: unsigned wraps by definition, signed overflow is undefined behavior, and C23 finally mandated two's complement representation. Third, the "code is data" section's forward pointers (loader, BPF JIT, W^X) set up the security chapters; note the file names even if the concept is old news to you.

Sources§