--- title: 'How Computers Work' source: 'https://academia.sh/en/courses/how-computers-work' language: en updated: '2026-08-17T04:39:35+00:00' license: 'CC BY-SA 4.0' lessons: 16 outcomes: - 'Explains the chain that carries a program from source text to processor instructions' - 'Shows how numbers, text and real values are represented in memory' - 'Explains with a worked example how the memory hierarchy affects program performance' --- # How Computers Work A prerequisite-free introductory course reaching from the representation of data in memory to instruction execution in the processor and the transformation of source code into a runnable program. ## Number Systems and Data Representation The topic that establishes the representation rules by which bits become numbers, text, and real values. ### Binary Number System Source: https://academia.sh/en/courses/how-computers-work/binary-number-system Positional number systems, binary representation, and conversion between bases. Everything that resides in a computer's memory — this lesson text, a photograph, the running program itself — is an object of the same kind: a sequence of two-state switches. This lesson asks the following question: how are numbers written in a medium that can hold nothing but two states? The answer turns out to be a special case of a more general rule that already governs the number system used in daily life. Before turning to the binary system, it is worth looking carefully at what the decimal system actually does. #### Positional Value When `4703` is written in the decimal system, four separate symbols are placed side by side, but the value expressed is not the sum of those symbols. Each symbol's contribution depends on its position: $$ 4703 = 4 \times 10^3 + 7 \times 10^2 + 0 \times 10^1 + 3 \times 10^0 $$ This scheme is called **positional notation**. It has three components: a **base** $b$, $b$ **digits** running from $0$ to $b-1$, and exponents that increase from right to left. In general, a number with digits $d_{n-1} d_{n-2} \dots d_1 d_0$ has the value: $$ \sum_{i=0}^{n-1} d_i \times b^{i} $$ The decimal system has nothing special about it; the base being ten is a historical consequence of having ten fingers on two hands. The rule works identically for every base. When the base is reduced to two, the digit set narrows to $\{0, 1\}$ — which corresponds directly to two-state hardware. #### Binary Representation In the **binary** system the base is $2$ and the digits are $0$ and $1$. A single binary digit is called a **bit**, a word that abbreviates "binary digit." Positional values are powers of two: $$ 1011_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11 $$ The subscript states which base the number is written in. This marker is necessary: the sequence `1011` reads as one thousand eleven if taken as decimal, and as eleven if taken as binary. The fact that the same symbol sequence carries different values in different bases will appear in a sharper form in later lessons — the same bit sequence can be a number, a letter, or an instruction, depending on who interprets it. The first ten binary numbers, with their counterparts: | Decimal | Binary | Decimal | Binary | |---|---|---|---| | 0 | 0 | 5 | 101 | | 1 | 1 | 6 | 110 | | 2 | 10 | 7 | 111 | | 3 | 11 | 8 | 1000 | | 4 | 100 | 9 | 1001 | A pattern stands out: every time the number reaches a power of two, one more digit becomes necessary. The same thing that happens when decimal moves from `9` to `10` happens in binary when moving from `1` to `10`. #### Binary to Decimal Converting a binary number to decimal is a direct application of the definition: sum the positional values of the bits. It suffices to add the positional values of the bits equal to $1$, since bits equal to $0$ contribute nothing. $$ 110101_2 = 32 + 16 + 4 + 1 = 53 $$ Here the positional values from right to left are $1, 2, 4, 8, 16, 32$; the bits equal to $1$ sit at positions $0$, $2$, $4$, and $5$. #### Decimal to Binary The opposite direction uses repeated division. Divide the number by two, record the remainder, continue with the quotient; once the quotient reaches zero, read the remainders in **reverse order**. For $53$: | Division | Quotient | Remainder | |---|---|---| | $53 \div 2$ | 26 | 1 | | $26 \div 2$ | 13 | 0 | | $13 \div 2$ | 6 | 1 | | $6 \div 2$ | 3 | 0 | | $3 \div 2$ | 1 | 1 | | $1 \div 2$ | 0 | 1 | Reading the remainders from bottom to top yields $110101_2$, consistent with the value computed in the previous section. Why the method works becomes clear from the definition of positional value. The remainder of dividing a number by two is that number's rightmost bit: even numbers end in $0$, odd numbers end in $1$. Taking the quotient shifts the number one digit to the right, and the same question is then asked for the next bit. #### Bits, Bytes, and Value Count A single bit distinguishes two states. Two bits distinguish four, three bits distinguish eight. In general, $n$ bits can write $$ 2^n $$ distinct patterns. This is the upper bound on representational capacity, and it is a counting fact independent of hardware: 8 bits allow 256 distinct patterns, and there is no 257th pattern. A group of eight bits is called a **byte**. A byte is the smallest addressable unit of memory; the processor reads at least a whole byte, never a single bit. When interpreted as an unsigned integer, a byte holds values between $0$ and $255$: the smallest pattern is `00000000`, the largest is `11111111`, that is, $2^8 - 1 = 255$. More generally, an $n$-bit unsigned integer ranges between $0$ and $2^n - 1$. The $-1$ arises because zero itself spends one pattern. Common widths and their bounds: | Width | Pattern count | Largest unsigned value | |---|---|---| | 8 bit | 256 | 255 | | 16 bit | 65,536 | 65,535 | | 32 bit | 4,294,967,296 | 4,294,967,295 | | 64 bit | $\approx 1{.}8 \times 10^{19}$ | $2^{64} - 1$ | This table holds a bound that later lessons will return to often. A variable's width determines the largest value it can hold; once that bound is exceeded, the number does not grow — its representation breaks. Overflow behavior will be detailed in the lesson on signed integers. #### Seeing the Conversion in Code The following program carries out the two conversions performed by hand in this lesson and compares the results against the built-in functions. ```python def decimal_to_binary(number: int) -> str: """Returns the binary representation of a non-negative integer.""" if number == 0: return "0" bits = [] while number > 0: bits.append(str(number % 2)) # remainder: rightmost bit number //= 2 # quotient: shift one digit right return "".join(reversed(bits)) def binary_to_decimal(representation: str) -> int: """Decodes a binary representation by summing positional values.""" value = 0 for bit in representation: value = value * 2 + int(bit) return value print(decimal_to_binary(53)) # 110101 print(binary_to_decimal("110101")) # 53 print(bin(53), int("110101", 2)) # 0b110101 53 ``` The line `value = value * 2 + int(bit)` inside `binary_to_decimal` is the left-to-right reading of the positional-value definition: each new bit shifts the value accumulated so far one digit to the left and adds its own contribution. Python's built-in `bin` function returns the binary representation with a `0b` prefix; the second parameter of the `int` function specifies which base to read. This prefix is only a notational convention, not part of the number itself. #### Summary - In positional notation, a digit's contribution is determined by the base raised to its position; the decimal system carries no special privilege. - In the binary system the base is $2$ and the digit set is $\{0, 1\}$; a single binary digit is called a bit. - Converting binary to decimal means summing the positional values of the bits equal to $1$; the reverse direction means reading the remainders of repeated division in reverse order. - With $n$ bits, exactly $2^n$ distinct patterns can be written; under an unsigned interpretation the largest value is $2^n - 1$. - A group of eight bits is called a byte, and memory is addressed at the byte level. #### Next Step Binary representation stays faithful to the hardware, but it is inconvenient for the human eye: a single 32-bit value is a sequence of zeros and ones that is hard to read without error. The next lesson takes up the hexadecimal base, which writes the same bit pattern with fewer symbols without breaking bit boundaries; that lesson will also establish a concrete example that the course will return to repeatedly. ### Hexadecimal and Octal Bases Source: https://academia.sh/en/courses/how-computers-work/hexadecimal-and-octal-bases Hexadecimal and octal representations, which give compact notation without breaking bit boundaries, and how to convert between them. The previous lesson established that binary representation matches the hardware exactly. That correspondence costs length: a 32-bit value is a thirty-two-symbol sequence such as `01000001010000100100001101000100`, and reading, writing, or comparing this sequence without error is inconvenient for a person. This lesson asks the following question: how can the same value be written with fewer symbols without hiding the bit structure? The answer lies in restricting the base choice to a power of two. #### Why Powers of Two If the base is chosen as $2^k$, every digit in that base corresponds to exactly $k$ bits. This reduces conversion from computation to grouping: it suffices to split the bits into blocks of $k$ and replace each block with a single digit. This does not hold for the decimal system, since $10$ is not a power of two. Looking at the decimal digits of `4703` says nothing about its bit pattern; conversion requires division. Hexadecimal and octal systems are therefore preferred: they give compactness while doing so without breaking bit boundaries. #### Hexadecimal System In the **hexadecimal** system the base is $16$. Sixteen digits are required; since the ten symbols of the decimal system are insufficient, the letters `A`–`F` are used for the remaining six values: | Hex | Decimal | Binary | Hex | Decimal | Binary | |---|---|---|---|---|---| | 0 | 0 | 0000 | 8 | 8 | 1000 | | 1 | 1 | 0001 | 9 | 9 | 1001 | | 2 | 2 | 0010 | A | 10 | 1010 | | 3 | 3 | 0011 | B | 11 | 1011 | | 4 | 4 | 0100 | C | 12 | 1100 | | 5 | 5 | 0101 | D | 13 | 1101 | | 6 | 6 | 0110 | E | 14 | 1110 | | 7 | 7 | 0111 | F | 15 | 1111 | Since $16 = 2^4$, every hexadecimal digit carries exactly four bits. A group of four bits is called a **nibble**. A byte is eight bits, that is, two nibbles; every byte is therefore written with exactly two hexadecimal digits. This is the real reason for the widespread use of hexadecimal notation: byte boundaries remain visible in the representation. Whether the letters are written in upper or lower case does not change the value; `0xFF` and `0xff` denote the same value. Within a single text, one form is chosen for consistency. #### Converting by Grouping To go from binary to hexadecimal, the bits are grouped in fours **starting from the right**, and each group is replaced by its counterpart in the table. If the leftmost group has fewer than four bits, it is padded with leading zeros. $$ \underbrace{0100}_{4}\ \underbrace{0001}_{1}\ \underbrace{0100}_{4}\ \underbrace{0010}_{2}\ \underbrace{0100}_{4}\ \underbrace{0011}_{3}\ \underbrace{0100}_{4}\ \underbrace{0100}_{4} $$ A thirty-two-bit sequence collapses to eight hexadecimal digits: `41424344`. The reverse direction applies the same rule in the opposite order: each hexadecimal digit is replaced by four bits. Grouping from the right matters. Grouping from the left, when the bit count is not a multiple of four, shifts every positional value and produces an incorrect result. #### The Course's Shared Example The value obtained above is the example this course will return to again and again: $$ \texttt{0x41424344} $$ Its decimal counterpart can be computed from the positional values: $$ 4 \times 16^7 + 1 \times 16^6 + 4 \times 16^5 + 2 \times 16^4 + 4 \times 16^3 + 3 \times 16^2 + 4 \times 16^1 + 4 \times 16^0 = 1{,}094{,}861{,}636 $$ This is the interpretation of the 32-bit pattern **as an unsigned integer**. The same pattern will be interpreted differently in later lessons: as a signed integer, as a real number, as a four-letter piece of text, and as a sequence that looks different depending on the byte order in memory. The bit pattern stays the same across all these readings; what changes is only the interpretation rule applied to it. This distinction carries the central idea of the lesson about the nature of data: memory contains no such thing as a "number" or "text" — it contains bit patterns and the interpretations applied to them. #### Octal System In the **octal** system the base is $8$; the digits range from $0$ to $7$. Since $8 = 2^3$, every octal digit carries three bits, and conversion again proceeds by grouping — this time in threes. $$ \underbrace{111}_{7}\ \underbrace{101}_{5}\ \underbrace{101}_{5} = 755_8 $$ Because groups of three do not align with byte boundaries, octal representation lags behind hexadecimal for general-purpose use: 8 bits, grouped in threes, yield two full digits and two leftover bits. Octal survives in domains whose natural unit is three bits. File permissions on Unix-derived systems are the standard example: read, write, and execute permissions form a group of three bits, and this group is repeated separately for owner, group, and others. The notation `755` encodes the permission `rwxr-xr-x`; the first digit $7 = 111_2$ states that all three permissions are granted, and the other two digits $5 = 101_2$ state that write permission is off. The permission model is treated in detail in the Linux curriculum. #### Notational Conventions Which base a number is written in must be stated in code just as it is in text. Common prefixes: | Prefix | Base | Example | Value | |---|---|---|---| | `0b` | 2 | `0b1011` | 11 | | `0o` | 8 | `0o755` | 493 | | `0x` | 16 | `0x1F` | 31 | | (none) | 10 | `31` | 31 | Prefixes are not part of the value; they only state which base to read. When the same value is written in four different forms, the same bit pattern results in memory. The following program shows the conversions and formatting: ```python value = 0x41424344 print(value) # 1094861636 print(hex(value)) # 0x41424344 print(bin(value)) # 0b1000001010000100100001101000100 print(f"{value:#010x}") # 0x41424344 (at least 8 digits, prefixed) print(f"{value:032b}") # 01000001010000100100001101000100 # Reading byte by byte: each byte is two hexadecimal digits. for shift in (24, 16, 8, 0): byte = (value >> shift) & 0xFF print(f"{byte:#04x}", byte) # 0x41 65 / 0x42 66 / 0x43 67 / 0x44 68 ``` It is worth noting that the `bin` output has 31 digits rather than 32: the built-in function does not print leading zeros. When fixed-width representation is required, a format specifier (`032b`, `#010x`) is used. Fixed width is needed to keep columns aligned when memory contents are inspected. The `>>` and `&` operators in the loop extract a specific byte from the pattern; these operators will be defined in the lesson on bit-level operations. #### Summary - When the base is chosen as $2^k$, conversion between bases is not computation but grouping in blocks of $k$. - In the hexadecimal system every digit carries four bits, so every byte is exactly two digits; byte boundaries remain visible in the representation. - Converting binary to hexadecimal groups from the right; a leftover left group is padded with zeros. - In the octal system every digit is three bits; because it does not align with byte boundaries, its use is limited to naturally three-bit fields such as file permissions. - The `0b`, `0o`, `0x` prefixes state the base to be read, not the value. - The course's shared example, `0x41424344`, has the value $1{,}094{,}861{,}636$ under an unsigned interpretation. #### Next Step Up to this point every number has been treated as non-negative. Hardware, however, has no separate place to hold a minus sign; the sign, too, must be encoded within the bit pattern. The next lesson takes up how this is done, and why the chosen method leaves the addition circuit unchanged. ### Signed Integers and Two's Complement Source: https://academia.sh/en/courses/how-computers-work/signed-integers How negative numbers are encoded within a bit pattern, two's complement representation, and overflow behavior. The previous two lessons treated numbers as non-negative. Hardware, however, has no extra place to hold a minus sign: a 32-bit register has only 32 bits. The sign must be encoded within the same pattern as the value itself. This lesson asks how that encoding is done. More than one answer is possible, but hardware has converged on essentially a single answer, and the reason is that this method leaves the addition circuit completely unchanged. #### Two Intuitive Approaches and Their Problems In **sign-magnitude** representation, the leftmost bit carries the sign and the remaining bits carry the magnitude. In eight bits, `0000 0101` is written for $+5$ and `1000 0101` for $-5$. This representation is close to human intuition and has two problems. First, zero has two representations: `0000 0000` and `1000 0000`. When two patterns carry the same value, equality comparison stops being a matter of comparing bits. Second, and more serious: addition is no longer plain addition. Computing $5 + (-5)$ at the bit level gives `0000 0101 + 1000 0101 = 1000 1010`; under the sign-magnitude interpretation this pattern means $-10$, whereas the result should have been zero. The hardware would need to strip out the signs, compare the magnitudes, and perform subtraction. In **one's complement** representation, a negative number is obtained by flipping every bit of the positive value: $-5$ becomes `1111 1010`. Addition comes closer to plain addition, but the carry bit must be added back at the start; zero is again represented twice (`0000 0000` and `1111 1111`). #### Two's Complement **Two's complement** representation eliminates both problems. Its definition fits in one sentence: the leftmost bit has a negative positional value. An $n$-bit pattern has the value: $$ -d_{n-1} \times 2^{n-1} + \sum_{i=0}^{n-2} d_i \times 2^{i} $$ For eight bits, the leftmost bit has weight $-128$, and the others carry the usual $+64, +32, \dots, +1$. Examples: | Pattern | Computation | Value | |---|---|---| | `0000 0101` | $4 + 1$ | $5$ | | `1111 1011` | $-128 + 64 + 32 + 16 + 8 + 2 + 1$ | $-5$ | | `1111 1111` | $-128 + 127$ | $-1$ | | `1000 0000` | $-128$ | $-128$ | | `0111 1111` | $127$ | $127$ | Zero has a single representation: `0000 0000`. The leftmost bit still gives away the sign — if it is $1$, the number is negative — but it is not a separate sign field; it is part of the value. The range of $n$-bit two's complement is: $$ [-2^{n-1},\ 2^{n-1} - 1] $$ The range is not symmetric: in eight bits, $-128$ is representable but $+128$ is not. There is one more value on the negative side, because zero consumes a pattern on the positive side. #### Producing the Negative Finding a number's negative takes two steps: **flip every bit, then add one.** For $5$: `0000 0101` $\rightarrow$ flip `1111 1010` $\rightarrow$ add one `1111 1011`. The result is the $-5$ pattern from the table. Applying the same operation to $-5$ returns to $5$: `1111 1011` $\rightarrow$ `0000 0100` $\rightarrow$ `0000 0101`. The operation is its own inverse. Why the rule works can be seen as follows: the sum of a pattern and its bitwise inverse is the pattern with every bit set to $1$, that is, $2^n - 1$. Adding one gives $2^n$; in an $n$-bit register, the value $2^n$ corresponds to zero. Hence adding $x$ to "flip and add one" yields zero — which is exactly the definition of a negative. There is a single exception: the smallest value. Applying the operation to $-128$ again yields `1000 0000`. Since $+128$ lies outside the range, this value has no negative in eight bits. #### Why Addition Is a Single Circuit The decisive hardware advantage of two's complement is this: signed addition is the **same** operation as unsigned addition. The bits are added, and the overflowing carry bit is discarded. Computing $5 + (-3)$ in eight bits: ``` 0000 0101 (5) + 1111 1101 (-3) ------------- 1 0000 0010 (carry bit discarded) 0000 0010 (2) ``` The result is correct, and the signs were never inspected. Subtraction, too, needs no separate circuit: computing $a - b$ is done by producing the negative of $b$ and adding it. Comparison operations are also built on the same adder. This is a concrete example of a representation choice directly reducing hardware complexity. The representation closest to intuition (sign-magnitude) gives the most expensive circuit; the representation furthest from intuition (two's complement) gives the cheapest one. #### Overflow Fixed width means results that fall outside the range cannot be represented. The result does not vanish; it wraps around from the other end of the range. **Under an unsigned interpretation**, in eight bits, $255 + 1$ gives `1111 1111 + 0000 0001 = 1 0000 0000`; discarding the carry leaves `0000 0000`, that is, $0$. The number has not grown — it has wrapped around. **Under a signed interpretation**, $127 + 1$ gives `0111 1111 + 0000 0001 = 1000 0000`, and this pattern means $-128$. The sum of two positive numbers has come out negative. The difference between the two cases is nothing but a different interpretation of the same bit operation. Hardware reports both kinds of overflow with separate flags; which one is meaningful is decided by the program, which knows whether the value is being read as signed or unsigned. The practical consequence of overflow is that numeric code can silently produce a wrong result. The sum of two large positive numbers coming out negative, loop counters wrapping around, and array indices pointing to unexpected locations all belong to this class. The security dimension of this behavior is treated separately in the cybersecurity curriculum. #### Extension When a value is moved into a wider type, the newly empty bits on the left must be filled. The rule for filling them depends on the interpretation, so that the value is preserved: - For **unsigned** values, the left bits are filled with zero (zero extension). - For **signed** values, the left bits are filled with a copy of the sign bit (sign extension). The eight-bit pattern `1111 1011` ($-5$) becomes `1111 1111 1111 1011` in sixteen bits, and its value is preserved. Applying the wrong rule silently changes the value: the eight-bit $-5$ pattern, under zero extension, becomes `0000 0000 1111 1011` in sixteen bits, that is, $251$. In the opposite direction, a sixteen-bit $-5$ pattern read as unsigned gives $65{,}531$. This is one of the typical sources of error in code that converts between types of different width. #### The Shared Example under a Signed Interpretation The leftmost bit of the course's shared example, the `0x41424344` pattern, is $0$ — the first hexadecimal digit is `4`, that is, `0100`. The pattern therefore carries the same value under a 32-bit signed interpretation as it does under the unsigned one: $1{,}094{,}861{,}636$. Had the first digit been `8` instead — that is, `0x81424344` — the leftmost bit would be $1$, and the same operations would give a very different value: $$ 2{,}168{,}603{,}460 - 2^{32} = -2{,}126{,}363{,}836 $$ No example shows the distance between a bit sequence and its meaning better than this one: changing a single bit shifts the value by more than two billion. #### Seeing It in Practice Python's integers are not fixed-width; they do not overflow, they grow. To observe fixed-width hardware behavior, masking is used: ```python def fixed_width(value: int, bits: int = 8) -> int: """Reduces a value to its bits-wide two's complement interpretation.""" mask = (1 << bits) - 1 # 0xFF for 8 bits value &= mask # discard excess bits sign_bit = 1 << (bits - 1) # 0x80 for 8 bits if value & sign_bit: value -= 1 << bits # the leftmost bit has negative weight return value print(fixed_width(0b11111011)) # -5 print(fixed_width(127 + 1)) # -128 (signed overflow) print(fixed_width(-1)) # -1 print((255 + 1) & 0xFF) # 0 (unsigned wraparound) print(fixed_width(0x41424344, 32)) # 1094861636 print(fixed_width(0x81424344, 32)) # -2126363836 ``` The body of `fixed_width` is a direct translation of this lesson's definition: the bits that do not fit the width are discarded first, then negative weight is applied to the leftmost bit. #### Summary - In a fixed-width representation, the sign is encoded within the pattern itself rather than in a separate field. - In two's complement representation the leftmost bit has a negative positional value; the range of $n$ bits is $[-2^{n-1}, 2^{n-1}-1]$, and zero has a single representation. - A number's negative is produced by flipping every bit and adding one; the smallest value is the exception to this operation. - Signed addition is performed by the same circuit as unsigned addition; this is the reason two's complement is preferred. - When the range is exceeded, the result does not vanish — it wraps around from the other end: under unsigned interpretation $255 + 1 = 0$, under signed interpretation $127 + 1 = -128$. - The fill rule under extension depends on interpretation; for signed values the sign bit is copied. #### Next Step Integers are exact within the range they can represent: every value either exists or it does not. Fractional numbers are a different matter — an infinite number of real values must be packed into a finite number of patterns. The next lesson takes up how this is done, and why the sum $0.1 + 0.2$ does not come out to exactly $0.3$. ### Floating-Point Numbers Source: https://academia.sh/en/courses/how-computers-work/floating-point-numbers Representing real values in finite bits, the IEEE 754 field layout, and the source of precision loss. For integers, representation is all or nothing: $200$ can be written in eight bits, $300$ cannot. Fractional numbers are more troubling still. There are infinitely many real numbers between $0$ and $1$; a finite set of bits can hold only a finite subset of them. The rest cannot be represented and are **rounded to the nearest representable value.** This lesson asks how that subset is chosen. The choice feeds directly into computation results: by the end of this lesson, the fact that $0.1 + 0.2$ does not come out to exactly $0.3$ will look like expected behavior rather than a quirk. #### Fixed Point and Its Limit The first solution that comes to mind is placing the decimal separator at a fixed position. The upper bits of an eight-bit value could be assigned to the integer part and the lower six to the fractional part; the positional values of the fractional bits then run $2^{-1}$, $2^{-2}$, $2^{-3}$, and so on: $$ \texttt{0101{.}1010}_2 = 4 + 1 + 0.5 + 0.125 = 5.625 $$ This is **fixed-point** representation, and it is still used in specific domains. Its problem is that range and resolution are locked together: every bit assigned to the fraction halves the largest representable number. If a single computation needs to carry both interplanetary distances and atomic radii, a fixed separator position cannot serve both needs at once. #### The Binary Counterpart of Scientific Notation The solution is to store the separator's position alongside the value itself. In scientific notation, writing $6.022 \times 10^{23}$ carries two pieces of information: significant digits and order of magnitude. The binary counterpart has the same structure: $$ (-1)^{s} \times 1.m \times 2^{e} $$ Here $s$ is the sign, $m$ is the fractional part (the **mantissa**), and $e$ is the exponent. The separator "floats" as the exponent changes — which is where the name of the representation comes from. One detail saves a bit: every nonzero number can be written in the form $1.\dots$ by choosing the exponent appropriately. Since the leading $1$ is always present, it does not need to be stored; hardware treats it as **implicit**. The entire mantissa field is then given over to the fractional part, and one bit is gained for free. #### The IEEE 754 Field Layout The bit-level details of floating-point representation are defined in the IEEE 754 standard. Two common widths: | Format | Total | Sign | Exponent | Mantissa | Exponent bias | |---|---|---|---|---|---| | binary32 (single precision) | 32 bit | 1 | 8 | 23 | 127 | | binary64 (double precision) | 64 bit | 1 | 11 | 52 | 1023 | The exponent field is not stored as a signed number but **biased**: the true exponent is found by subtracting a fixed bias from the value stored in the field. In binary32, if the field holds $130$, the true exponent is $130 - 127 = 3$. The reason for this arrangement is ordering: a biased exponent lets two positive floating-point numbers be sorted by comparing their bit patterns as if they were unsigned integers. The two extreme values of the exponent field are reserved for special meanings: - All bits $0$: the value is zero (if the mantissa is also zero) or a **subnormal** number. Subnormal numbers sustain resolution very close to zero by abandoning the implicit-$1$ rule. - All bits $1$: the value is **infinity** if the mantissa is zero, and **not a number (NaN)** if it is nonzero. Infinity and NaN carry the result of an overflowing or undefined operation without halting the program. $1/0$ gives infinity, $0/0$ gives NaN. NaN's distinguishing property is that it is not even equal to itself; this is the standard way to test whether a value is NaN. #### The Floating-Point Interpretation of the Shared Example The course's shared example, `0x41424344`, splits into the following fields when interpreted as binary32: $$ \underbrace{0}_{s}\ \underbrace{1000\,0010}_{\text{exponent field}}\ \underbrace{100\,0010\,0100\,0011\,0100\,0100}_{\text{mantissa}} $$ - The sign bit is $0$, so the number is positive. - The exponent field is $1000\,0010_2 = 130$; the true exponent is $130 - 127 = 3$. - The mantissa field is $4{,}342{,}596$; its fractional value is $4{,}342{,}596 / 2^{23} = 0.517677783966064453125$. Adding the implicit $1$ gives a significand of $1.517677783966064453125$. The value: $$ 1.517677783966064453125 \times 2^{3} = 12.141422271728515625 $$ The same 32 bits read as $1{,}094{,}861{,}636$ as an unsigned integer and as $12.141422271728515625$ as a floating-point number. The bit pattern has not changed; what changes is the interpretation rule applied to it. A variable's **type** in a programming language exists precisely to select that rule. #### Which Numbers Are Exactly Represented The mantissa is a binary fraction. The values represented exactly are therefore fractions whose denominator is a power of two: $0.5$, $0.25$, $0.75$, $3.125$, and the like. Such numbers are called **dyadic rationals**. $0.1$ is not one of them. This number, written with a single digit in the decimal system, has a repeating expansion in the binary system: $$ 0.1_{10} = 0.0001100110011\overline{0011}\dots_2 $$ A repeating expansion does not fit a finite mantissa; it is rounded to the nearest representable value. What binary64 stores is not $0.1$ but another number very close to it. The same holds for $0.2$ and $0.3$. This is not a flaw of the language or the hardware: it is exactly as natural that $1/10$ cannot be written with finitely many binary digits as it is that $1/3$ cannot be written with finitely many decimal digits. What changes is which denominators are "lucky." #### The Result of Addition When two rounded values are added, the result is rounded as well, and errors accumulate: ```python print(0.1 + 0.2) # 0.30000000000000004 print(0.1 + 0.2 == 0.3) # False print(f"{0.1:.20f}") # 0.10000000000000000555 import math print(math.isclose(0.1 + 0.2, 0.3)) # True import struct (value,) = struct.unpack(">f", bytes.fromhex("41424344")) print(value) # 12.141422271728516 ``` The comparison `0.1 + 0.2 == 0.3` giving a false result is not a bug — it follows directly from the representation. Floating-point values are therefore never **compared for equality**; instead, one checks whether the difference falls below an acceptable threshold. Functions such as `isclose` perform this comparison using a combination of relative and absolute tolerance. The `struct` module interprets four bytes of raw data according to a given format; the format string `">f"` means "big-endian, single-precision floating point." What the byte-order marker here means is the subject of this topic's final lesson. #### The Limit of Precision Mantissa width determines how many significant digits can be carried. binary32 carries about 7 significant decimal digits, binary64 about 15 to 17. This limit has two practical consequences. First: when a very large and a very small value are added, the smaller one can vanish. If a value below the mantissa's resolution is added to a large number, the result does not change. Second: computation order affects the result. Floating-point addition does not carry the associative property — $(a + b) + c$ and $a + (b + c)$ can give different results. This means algebraic properties familiar from integers do not carry over here, and it is one of the reasons numerical methods form a separate discipline. In domains where decimal precision is a matter of contract, such as monetary amounts, floating-point types are not used; fixed-precision decimal types, or integers storing the smallest unit (for example, cents), are preferred instead. #### Summary - Finite bits hold only a finite subset of the real numbers; the rest are rounded to the nearest representable value. - Floating-point representation stores a value as $(-1)^s \times 1.m \times 2^{e}$; the leading $1$ is implicit and gains one bit. - In IEEE 754 binary32 the fields are 1 / 8 / 23 bits, and the exponent is stored with a bias of $127$; the extreme values of the exponent field are reserved for zero, subnormal numbers, infinity, and NaN. - Exactly represented fractions are those whose denominator is a power of two; $0.1$ is not among them. - Floating-point values are compared with tolerance, not equality; addition does not carry the associative property. - The same `0x41424344` pattern reads as $1{,}094{,}861{,}636$ as an integer and as $12.141422271728515625$ as binary32. #### Next Step Up to this point, bit patterns have always been interpreted as a whole. Programs, however, frequently work with individual bits: turning on a flag, extracting a field, doubling a value. The next lesson defines the bit-level operators that do this; the `>>` and `&` operators used in previous lessons will also be given their rationale there. ### Bit-Level Operations Source: https://academia.sh/en/courses/how-computers-work/bit-level-operations The AND, OR, XOR, and NOT operators, shifts, and field extraction with masks. Previous lessons always interpreted bit patterns as a whole: thirty-two bits together formed an integer or a real number. Programs, however, frequently work with parts of a pattern — extracting a single byte, turning on a flag, clearing a field. This lesson covers the operators that perform these part-level operations. They are among the cheapest operations in hardware, and a large share of low-level code is written with them. #### Bitwise Logical Operators Four basic operators are defined by their truth tables over bits. The operators apply **bit by bit**: the $i$-th bit of the result depends only on the $i$-th bits of the inputs. | $a$ | $b$ | $a \mathbin{\&} b$ (AND) | $a \mid b$ (OR) | $a \oplus b$ (XOR) | |---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 1 | 1 | | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 1 | 1 | 0 | The **NOT** operator takes a single input and flips every bit: $\lnot 0 = 1$, $\lnot 1 = 0$. Over two eight-bit patterns: ``` 1100 1010 1100 1010 1100 1010 & 1010 0110 | 1010 0110 ^ 1010 0110 ----------- ----------- ----------- 1000 0010 1110 1110 0110 1100 ``` Each operator has a distinguishing use: - **AND** clears unwanted bits: every bit facing a $0$ is erased. - **OR** turns on desired bits: every bit facing a $1$ is set. - **XOR** flips selected bits, and is also the bit-level answer to "are these different?" A number XORed with itself is zero, which means XORing the same value twice returns to the starting value. These operators must not be confused with the logical `and`/`or` operators. Logical operators treat an entire value as true or false and short-circuit in most languages; bit-level operators process each bit independently and never short-circuit. #### Shifting **Left shift** (`<<`) moves every bit to the left, filling from the right with zeros. Since each shift doubles the positional values, it multiplies the number by two: $$ \texttt{0000 0101} \ll 2 = \texttt{0001 0100} \qquad (5 \times 4 = 20) $$ **Right shift** (`>>`) moves bits to the right and divides the number by two, discarding the fractional part. Which bit fills in from the left depends on how the value is interpreted: - **Logical shift** fills from the left with zero; correct for unsigned values. - **Arithmetic shift** fills from the left with a copy of the sign bit; it preserves the sign of signed values. This distinction is the same one as the sign-extension rule from the previous lesson. In Python, integers are signed and `>>` behaves arithmetically: `-8 >> 1` gives `-4`, `-5 >> 1` gives `-3` (the result rounds down, not toward zero). In fixed-width languages, shifting by a count equal to or greater than the data width is undefined behavior; shifting a 32-bit value 32 times does not give a portable result. This is one of the known sources of code that fails silently. #### Masking A **mask** is a fixed pattern that states which bits are of interest. Four basic operations are performed with a mask: | Purpose | Operation | Description | |---|---|---| | Test a bit | `value & mask` | If the result is nonzero, the bit is set | | Set a bit | `value \| mask` | Bits equal to $1$ in the mask are turned on | | Clear a bit | `value & ~mask` | Bits equal to $1$ in the mask are zeroed | | Flip a bit | `value ^ mask` | Bits equal to $1$ in the mask are flipped | Extracting a field is two steps: shift the field all the way to the right, then mask off the excess. Taking the second byte from the course's shared example: $$ (\texttt{0x41424344} \gg 16)\ \&\ \texttt{0xFF} = \texttt{0x42} $$ The shift amount states how many bits from the right the field begins; the mask states how many bits wide the field is. `0xFF` selects an eight-bit field, `0x0F` a four-bit field, `0x01` a single-bit field. The same method works in reverse as well: to write a value into a field, the field is first cleared, then the new value is shifted and placed with OR. #### Flag Sets Independent on/off options can each be assigned to a bit. This arrangement carries many options in a single integer and makes combining and testing options cheap. ```python READ = 0b100 # 4 WRITE = 0b010 # 2 EXECUTE = 0b001 # 1 permission = READ | WRITE # 0b110 = 6 print(bool(permission & WRITE)) # True — is write permission set? print(bool(permission & EXECUTE)) # False permission |= EXECUTE # add execute permission -> 0b111 permission &= ~WRITE # remove write permission -> 0b101 print(f"{permission:03b}") # 101 ``` The three bits in this example are exactly the file permissions written in octal notation in the second lesson: the pattern `0b101` is `5`, that is, the permission `r-x`. The reason octal notation is preferred in that domain is that groups of three bits map directly to a single digit. #### Common Idioms A few patterns built from bit operators recur frequently in source code: - `x & (x - 1)` — clears the rightmost set bit. If the result is zero, $x$ is a power of two (only one bit was set). The same expression, used in a loop, counts set bits. - `x & -x` — leaves only the rightmost set bit. This follows from the definition of negation in two's complement. - `x << k` and `x >> k` — multiplication and division by powers of two. Compilers already perform this transformation; writing a shift in source code does not improve performance and only reduces readability. - `x ^ mask` — flips selected bits; `x ^ x` is always zero. The following program shows two of these idioms together with field extraction: ```python def is_power_of_two(x: int) -> bool: """A positive x is a power of two if exactly one bit is set.""" return x > 0 and (x & (x - 1)) == 0 def count_set_bits(x: int) -> int: """Counts by clearing the rightmost set bit at each step.""" count = 0 while x: x &= x - 1 count += 1 return count value = 0x41424344 bytes_ = [(value >> k) & 0xFF for k in (24, 16, 8, 0)] print([hex(b) for b in bytes_]) # ['0x41', '0x42', '0x43', '0x44'] print(is_power_of_two(64)) # True print(is_power_of_two(48)) # False print(count_set_bits(value)) # 9 print(bin(value).count("1")) # 9 — same result, different route ``` The loop in `count_set_bits` runs once per set bit, not once per bit of width. The pattern `0x41424344` has nine set bits (`0x41` and `0x42` contribute two each, `0x43` three, `0x44` two), so the loop runs nine times rather than thirty-two. #### Summary - Bit-level operators process each bit independently; unlike logical operators, they do not treat the entire value as true or false. - AND clears bits, OR sets bits, XOR flips bits; a value XORed with itself is zero. - Left shift multiplies by two; right shift divides by two, and the fill rule from the left depends on whether the value is interpreted as signed. - Field extraction is two steps: shift the field right, then apply a mask the width of the field. - Independent options can be carried as flag bits in a single integer; combining uses OR, testing uses AND. - `x & (x - 1)` clears the rightmost set bit; the power-of-two test and bit counting are both built on this idiom. #### Next Step Representation rules for numbers are now complete. Text raises a different problem: letters are not naturally numbers, so every character must be mapped to a number, and this mapping has to be agreed upon worldwide. The next lesson takes up how that agreement is built, and why the difference between a code point and a byte sequence matters. ### Character Encodings Source: https://academia.sh/en/courses/how-computers-work/character-encodings Character sets from ASCII to Unicode, the distinction between code points and byte sequences, and UTF-8 encoding. For numbers, representation rules could be derived from the structure of the hardware: positional value, two's complement, and floating point were all designed around the requirements of arithmetic. Text has no such natural necessity. Which number the letter `A` maps to is a design decision, and that decision has to be **shared** by whoever writes and whoever reads. This lesson covers how that sharing is established. There are two separate questions, and confusing them is a common source of error: which number a given character receives, and how that number is written into bytes. #### Character Set and Encoding A **character set** states which characters exist and which number each one is assigned. This number is called a **code point**. An **encoding** states how a code point is written into bytes. In small sets these two layers coincide: if the character count does not exceed 256, every code point fits into a single byte and the distinction becomes invisible. Once the set grows, the distinction becomes unavoidable — there is more than one way to write a number that will not fit in a single byte, and which one is used must be stated. #### ASCII ASCII is a 7-bit character set: it defines $2^7 = 128$ code points. Its layout is not arbitrary; it is arranged for arithmetic convenience: | Range (hex) | Content | |---|---| | `00`–`1F` | Control characters (newline, tab, end of file, etc.) | | `20` | Space | | `30`–`39` | Digits `0`–`9` | | `41`–`5A` | Uppercase letters `A`–`Z` | | `61`–`7A` | Lowercase letters `a`–`z` | The digits being consecutive reduces going from a digit character to its numeric value to a single subtraction: `'7' - '0' = 7`. The difference between uppercase and lowercase letters is exactly `0x20`, that is, a single bit: `A` = `0x41` = `0100 0001`, `a` = `0x61` = `0110 0001`. Upper- and lowercasing, within ASCII's range, is a single bit operation. The course's shared example reaches its third interpretation here. The four bytes of the `0x41424344` pattern are `0x41`, `0x42`, `0x43`, `0x44`; their ASCII counterparts: $$ \texttt{0x41424344} \longrightarrow \texttt{"ABCD"} $$ The same thirty-two bits read as $1{,}094{,}861{,}636$ as an unsigned integer, $12.141422271728515625$ as binary32, and `ABCD` as text. Reading the contents of a file or a network packet correctly requires knowing which of these three interpretations applies; that is the job of a format definition. #### Code Pages and the Problem They Left Behind Because ASCII defines only 128 code points, the upper half of an eight-bit byte is left empty. Letters such as `ğ`, `ş`, and `ı` in Turkish were placed into this empty half — but since every language community made its own placement, mutually incompatible **code pages** resulted. The consequence is that the same byte gives a different letter depending on which code page it is read with. Text opened with the wrong code page turning into garbled symbols is a symptom of this incompatibility. There is also a harder limit: a single byte carries at most 256 characters, so a single multilingual document cannot be written with the code-page approach. #### Unicode Unicode solves this problem by separating the character set from the encoding. It assigns a code point to the characters of the world's writing systems within a single number space; the code point is written with a `U+` prefix, in hexadecimal: | Character | Code point | |---|---| | `A` | U+0041 | | `ç` | U+00E7 | | `ğ` | U+011F | | `漢` | U+6F22 | The code point space runs from U+0000 to U+10FFFF, that is, more than a million code points. The first 128 code points are identical to ASCII — a deliberate decision made to preserve backward compatibility. Unicode is not an encoding: it does not say how the number `U+011F` is to be written into bytes. Encodings say that. #### UTF-8 UTF-8 uses between 1 and 4 bytes, depending on the size of the code point. The byte structure is read from the prefix bits of the first byte: | Code point range | Byte count | Pattern | |---|---|---| | U+0000 – U+007F | 1 | `0xxxxxxx` | | U+0080 – U+07FF | 2 | `110xxxxx 10xxxxxx` | | U+0800 – U+FFFF | 3 | `1110xxxx 10xxxxxx 10xxxxxx` | | U+10000 – U+10FFFF | 4 | `11110xxx 10xxxxxx 10xxxxxx 10xxxxxx` | The code point's bits are placed left to right into the slots marked `x`. `ç` (U+00E7 = `0000 0000 1110 0111`) requires two bytes; its significant bits split into `00011 100111`: $$ \texttt{110}\underline{00011}\ \texttt{10}\underline{100111} = \texttt{0xC3\ 0xA7} $$ The same rule writes `漢` (U+6F22) in three bytes: `0xE6 0xBC 0xA2`. The design has three consequences: 1. **ASCII compatibility.** Code points up to U+007F are written in a single byte, with values identical to ASCII. A document containing only ASCII is also a valid UTF-8 document. 2. **Self-synchronization.** Continuation bytes always start with `10`; whether a given byte is the start of a character or a continuation of one can be read from its leading bits alone. In a corrupted stream, the boundary of the next character can still be located. 3. **Variable length.** How many bytes a character occupies depends on its content; this has direct consequences for text processing. UTF-16 and UTF-32 are alternative encodings. UTF-32 writes every code point in a fixed four bytes; access is direct but space usage is high. UTF-16 writes most characters in two bytes and uses a **surrogate pair** for the rest — meaning it, too, is variable length, contrary to the common assumption that it is fixed. #### Code Points, Bytes, and Graphemes In a variable-length encoding, "length" is not a single well-defined concept. There are three separate counts, and they can all differ: - **Byte count** — the space occupied on disk or on the wire. - **Code point count** — the number of Unicode numbers. - **Grapheme count** — the units a user perceives as "letters." The source of the third distinction is **combining marks**. The character `é` can be written in two different ways: as the single code point U+00E9, or as `e` (U+0065) followed by a combining acute accent (U+0301). The two forms look identical on screen, their code point counts differ, and they do not compare equal directly. The **normalization** operation removes this difference before comparison by choosing one of the two forms. It is here that upper- and lowercasing turn out not to be language-independent either. An operation that is a single bit in ASCII requires, in Turkish, the mappings `i` ↔ `İ` and `ı` ↔ `I`; a conversion performed without knowledge of the language gives the wrong result. ```python text = "ABCD" print(text.encode("utf-8")) # b'ABCD' — 4 bytes turkish_word = "çağ" # Turkish for "era" print(turkish_word.encode("utf-8")) # b'\xc3\xa7a\xc4\x9f' print(len(turkish_word), len(turkish_word.encode("utf-8"))) # 3 5 print(ord("ç"), hex(ord("ç"))) # 231 0xe7 — code point U+00E7 print(chr(0x6F22)) # 漢 decomposed = "e\u0301" # e + combining accent (U+0301) composed = "\u00e9" # single code point (U+00E9) print(decomposed == composed) # False print(len(decomposed), len(composed)) # 2 1 import unicodedata print(unicodedata.normalize("NFC", decomposed) == composed) # True ``` The fact that `len(turkish_word)` gives $3$ while its encoded form is $5$ bytes shows why the two counts must not be confused. A string operation that assumes fixed length — "take the first three bytes," for instance — cuts a multi-byte character in the middle and produces an invalid byte sequence. #### Summary - A character set assigns characters a number (code point); an encoding states how that number is written into bytes. The two layers are separate. - ASCII defines 128 code points; digits and letters are consecutive, and the upper/lowercase difference is a single bit. The course's shared example, `0x41424344`, reads as `ABCD` under an ASCII interpretation. - Single-byte code pages are both mutually incompatible and limited to 256 characters; multilingual text cannot be written with this approach. - Unicode defines a single code point space and overlaps with ASCII in its first 128 code points. - UTF-8 writes a code point in 1–4 bytes; it is ASCII-compatible and self-synchronizing because continuation bytes start with `10`. - Byte count, code point count, and grapheme count are different magnitudes; combining marks and language-dependent letter case reveal this difference. #### Next Step A character has been shown to sometimes span multiple bytes. In what order, then, do those bytes sit in memory? The same question applies to numbers: in which order do the four bytes of the value `0x41424344` sit in memory? The next lesson takes up how this order varies by hardware, and why it becomes a source of trouble when data moves between two systems. ### Byte Order Source: https://academia.sh/en/courses/how-computers-work/byte-order The order in which multi-byte values are laid out in memory, little- and big-endian representation, and the problems this creates when exchanging data. Up to this point, how many bits a value has and how those bits are interpreted have been established. One question remains open: memory is addressed at the byte level, yet the value `0x41424344` is four bytes. In which order do these four bytes occupy four consecutive addresses? The question has no single correct answer. Different families of hardware have given different answers, and this difference leads to silent corruption when data is moved between two systems. This lesson defines the difference and the safeguard taken against it. #### Two Layouts The value's most significant byte is `0x41`, and its least significant byte is `0x44`. There are two layout arrangements: In **big-endian** order, the most significant byte is written to the lowest address: | Address | $A$ | $A{+}1$ | $A{+}2$ | $A{+}3$ | |---|---|---|---|---| | Byte | `41` | `42` | `43` | `44` | In **little-endian** order, the least significant byte is written to the lowest address: | Address | $A$ | $A{+}1$ | $A{+}2$ | $A{+}3$ | |---|---|---|---|---| | Byte | `44` | `43` | `42` | `41` | The value is the same in both orders: $1{,}094{,}861{,}636$. What changes is the physical layout of that value in memory. The names are a reference to the dispute in *Gulliver's Travels* over which end an egg should be cracked from; the naming captures well the gap between the technical weight of the question and the practical fatigue it produces. #### The Rationale Behind Each Order The case for little-endian order is that a width conversion does not change the address. On a little-endian system, reading a single byte from the address of a 32-bit value gives that value's least significant byte; reading two bytes from the same address gives the low sixteen bits. Narrowing a value to a smaller type requires no address arithmetic. The case for big-endian order is readability and ordering. When a memory dump is read left to right, the bytes appear in the same order the number is written. Multi-byte values compared byte by byte also produce a comparison that matches numeric ordering, which is a convenience for structures that rely on lexicographic key ordering. Both cases are technically valid, and the choice is largely historical. What matters is that a system's chosen order is **known**, and that the order is **fixed explicitly** whenever data leaves that system. #### Same Bytes, Different Values The concrete form of the problem is this: when the four bytes `41 42 43 44` are read from a file, which number results? - Under a big-endian reading: `0x41424344` = $1{,}094{,}861{,}636$ - Under a little-endian reading: `0x44434241` = $1{,}145{,}258{,}561$ The two values differ by more than fifty million, and no error is raised anywhere: the program runs, and its result is wrong. This is the final instance of a principle repeated throughout previous lessons: bytes carry no meaning of their own — meaning comes from the rule used to read them. The situation differs for text. ASCII and UTF-8 are sequences made of single-byte units; a byte sequence's order is determined by the encoding itself, so the byte-order problem does not arise. The bytes `41 42 43 44` read as UTF-8 give `ABCD` on every system. By contrast, the units of UTF-16 and UTF-32 are two and four bytes; in these encodings, byte order must be stated explicitly. The way it is stated is by writing the code point U+FEFF, the **byte order mark**, at the start of the text. UTF-8 text does not need the same mark; its presence implies only the encoding, not the order, and it causes unexpected behavior in some parsers. #### Network Byte Order Network protocols must be independent of the layout of the hardware at either end. For this reason, a single order is fixed for multi-byte fields in protocol headers: big-endian. This convention is called **network byte order**. The program performs the conversion from host order to network order explicitly. Conversion functions do nothing if the host order is already big-endian; if it is little-endian, they reverse the bytes. Code working correctly on both kinds of hardware depends on this conversion never being skipped. The same discipline applies to file formats: when a binary format is defined, field widths and byte order are written into the documentation. Writing memory contents directly to disk or to the network as-is produces a file that depends on the hardware that created it. #### In Practice In Python, byte order is stated explicitly to the conversion functions: ```python import sys, struct print(sys.byteorder) # this system's order: 'little' or 'big' value = 0x41424344 print(value.to_bytes(4, "big").hex()) # 41424344 print(value.to_bytes(4, "little").hex()) # 44434241 raw = b"ABCD" # bytes 41 42 43 44 print(hex(int.from_bytes(raw, "big"))) # 0x41424344 print(hex(int.from_bytes(raw, "little"))) # 0x44434241 print(struct.pack(">I", value)) # b'ABCD' print(struct.pack("I", 0x41424344)` producing `b'ABCD'` ties together every lesson of this topic in a single line: the same thirty-two bits read as $1{,}094{,}861{,}636$ as an integer, $12.141422271728515625$ as a floating-point number, `ABCD` as text, and, in memory, as the sequence `41 42 43 44` or `44 43 42 41` depending on the system. The first character of the format string states the order: `<` little-endian, `>` big-endian, `!` network byte order (equivalent to big-endian). If this character is omitted, the running system's order is used — the situation that portable code must avoid. #### Not to Be Confused with Bit Order The endianness discussion concerns **bytes**, not bits. The positional values of the bits within a byte are the same under both orders: the most significant bit is on the left, the least significant bit is on the right. On a little-endian system, the byte `0x41` is still the pattern `0100 0001`; it is not reversed. Bit order is a separate concept that applies in a different context: in the hardware layers where data is transmitted serially over a wire, which end the bits are sent from depends on the protocol. This is a decision independent of the byte-level order that software sees, and it is treated in the physical layer topic of the networks curriculum. A third source of confusion is the memory layout of bit fields. The order in which fields with a specified bit width are packed inside a structure depends on the compiler, in addition to byte order. For this reason bit fields are not used in binary formats that need to be portable; fields are instead produced with explicit masking and shifting — exactly what the operators from the fifth lesson are for. #### The Discipline of Data Exchange The way to avoid the byte-order problem is to handle it explicitly at every boundary: 1. **Order is documented in binary formats.** Field widths and byte order are part of the format definition; both the reader and the writer conform to the same document. 2. **Conversion happens at boundaries.** A value is converted to host order as it enters the system, and to the fixed order as it leaves; the code in between never thinks about order at all. 3. **Memory contents are not transferred directly.** A raw copy of a structure is not portable, due to alignment and padding differences in addition to byte order. 4. **Text formats do not solve the problem by themselves.** Text-based formats such as JSON have no byte-order problem, but numeric precision and encoding decisions must be documented instead. This discipline will come up again in every layer that works with network protocols and file formats. #### Summary - The bytes of a multi-byte value can be laid out in memory in two different orders: little-endian places the least significant byte at the lowest address, big-endian places the most significant byte there. - The value stays the same; the layout changes — the same byte sequence gives a different number under the two orders. - Little-endian order frees width narrowing from address arithmetic; big-endian order gives memory-dump readability and lexicographic ordering. - Encodings made of single-byte units (ASCII, UTF-8) have no byte-order problem; UTF-16 and UTF-32 state their order with a byte order mark. - Network protocols fix big-endian order; the conversion is performed explicitly by the program. - In binary data exchange, byte order is part of the format definition; a raw memory copy is not portable. #### Next Step This topic established how data is represented in memory: bits, integers, real numbers, text, and byte layout. What comes next is what is done with that data. The next topic takes up how memory connects to the processor and the steps by which an instruction is executed in hardware; there, the `0x41424344` pattern will appear once more, this time possibly as an instruction itself. ## Processor and Memory Instruction execution, the transfer of data to the processor, and the memory hierarchy's effect on performance. ### Registers and Main Memory Source: https://academia.sh/en/courses/how-computers-work/registers-and-main-memory The model of memory as an addressed array, the role of registers, and the access-cost gap between them. The previous topic established how data is represented as bit patterns. These bit patterns have to reside somewhere, and where they reside directly determines program performance. This topic examines the structure of that place and how data is carried to the processor. This lesson asks: how does memory appear to a program, and where does the processor keep the data it operates on? #### Memory: An Addressed Array The memory model a program sees is plain: an array of cells, each holding one byte, numbered starting from zero. A cell's number is called its **address**, its contents its **value**. | Address | 1000 | 1001 | 1002 | 1003 | 1004 | |---|---|---|---|---|---| | Value | `41` | `42` | `43` | `44` | `00` | This model has two consequences. First, accessing memory requires two pieces of information: which address, and how many bytes. The value `0x41424344` from the previous topic is four bytes; reading it means requesting four bytes starting at address `1000`. How many bytes are interpreted, and in what order, is the rule defined in the byte order lesson. Second, an address is itself a number and can be stored in memory. A variable that holds another variable's address — a **pointer** — follows directly from this observation. Address width determines the largest amount of memory that can be addressed: 32-bit addresses can address $2^{32}$ distinct bytes, roughly four billion cells; the limit for 64-bit addresses is a size no hardware reaches in practice. #### Registers The processor does not keep the values it operates on in main memory; the arithmetic and logic unit can only read from small, fast storage units built into the processor itself, called **registers**. Registers have three distinguishing traits: - **They are few.** A processor's general-purpose registers number in the tens; main memory's cells number in the billions. - **They have no addresses.** Registers are referenced directly by name in an instruction, not by number. - **Their access is nearly free.** Reading a register takes on the order of one processor clock cycle. Some registers serve special roles: the program counter holds the address of the next instruction, the stack pointer holds the top of the call stack. Their function is defined in later lessons. An addition is therefore not a single step. Computing `a + b` first loads the two values from memory into registers, performs the addition between registers, and writes the result back to memory. The architectures that **require** this load–operate–store pattern are the RISC family; on architectures such as x86 an instruction can take one of its operands straight from memory. That the computation happens in registers is the same in both families. #### The Access-Cost Gap The speed gap between registers and main memory is large enough to shape program design. Exact durations vary by hardware; what does not vary is the **order-of-magnitude gap**: | Layer | Access order (clock cycles) | |---|---| | Register | ~1 | | First-level cache | a few | | Last-level cache | tens | | Main memory | hundreds | | Persistent storage | tens of thousands and up | Each row is noticeably slower and noticeably larger than the one before it. This layering is called the **memory hierarchy**, and its design rationale is economic: fast storage is expensive, cheap storage is slow. The hierarchy strikes a balance between the two. The consequence is this: a program's speed depends as much on where it accesses data from as on how many operations it performs. A single value read from main memory can take as long as hundreds of arithmetic operations. This observation is the reason the cache, covered in the next lesson, exists at all. #### How Storage Media Differ The layers of the hierarchy differ not only in speed and capacity but in physical mode of operation. Registers and cache are built from circuits that hold state as long as supply voltage is present; access is fast, cost per unit high. Main memory instead holds state in tiny electrical charges that leak over time, so it must be **refreshed** regularly. Refreshing is why main memory is both slower and cheaper: it uses fewer circuit elements per cell. These three layers share one property: **volatility**. Their contents are lost when power is cut. Persistent storage, by contrast, retains its contents without power, but its access is orders of magnitude slower and writes are typically performed at the block level. This volatility distinction explains why data a running program holds must be saved separately: state in memory is bounded by the lifetime of the process. #### Word Width and Alignment A **word** is the data width a processor natively operates on; it coincides with the width of its general-purpose registers. On a 64-bit processor, a word is eight bytes. An architecture's own use of the term can depart from this: the x86 manual counts a `word` as two bytes even on a 64-bit processor, and calls the eight-byte unit a `quadword`. Hardware performs multi-byte accesses relative to word boundaries. Because of this, the placement of data structures in memory follows the **alignment** rule: the address of an $n$-byte value is generally chosen to be a multiple of $n$. A four-byte integer is placed at address `1000`, not at `1001`. The cost of an unaligned access varies by hardware: some processors slow it down by splitting it into two memory operations, others raise a fault. The visible consequence of the alignment rule is **padding**. When small and large fields are declared consecutively in a structure, the compiler inserts unused bytes between them: ``` struct A struct B 1-byte field 8-byte field 7 bytes padding 1-byte field 8-byte field 7 bytes padding total: 16 bytes total: 16 bytes ``` Declaring the same fields in a different order can change the structure's size in memory. Ordering fields from largest to smallest width is a common habit that minimizes padding. This detail also explains why the previous lesson noted that a raw memory copy is not portable: the amount of padding depends on the compiler and the hardware. #### Seeing Memory Layout The following program examines different representations of the same data and the space an object occupies in memory: ```python import sys, array value = 0x41424344 # Four bytes to be written to memory (in big-endian order) raw = value.to_bytes(4, "big") for offset, byte in enumerate(raw): print(f"address+{offset}: {byte:#04x}") # 0x41 0x42 0x43 0x44 # Fixed-width arrays keep elements contiguous and aligned. arr = array.array("I", [1, 2, 3, 4]) # 'I': 4-byte unsigned integer print(arr.itemsize, len(arr)) # 4 4 print(arr.buffer_info()[1] * arr.itemsize) # 16 — total bytes # Python objects take up far more space than raw data. print(sys.getsizeof(1), sys.getsizeof(arr)) # sizes include object header ``` The `array` module stores elements at fixed width and contiguously; this is the closest Python equivalent to a hardware-friendly data structure layout. A general-purpose list, by contrast, holds pointers to its elements: the values themselves sit scattered in memory. The difference between the two layouts becomes visible in the cache behavior covered in the next lesson. #### Summary - To a program, memory is an array of addressed byte cells; access requires both an address and a width. - An address is itself a number and can be stored in memory; the concept of a pointer follows from this observation. - The processor operates only on registers; computation proceeds in a load–operate–store pattern. - There is an order-of-magnitude speed gap among registers, cache, main memory, and persistent storage; this layering is the memory hierarchy. - Multi-byte values are placed according to the alignment rule; the rule causes padding bytes and order-dependent size differences in structures. #### Next Step Where data resides has now been defined. Instructions themselves reside in memory too, and share the same address space. The next lesson covers the cycle by which the processor fetches an instruction from memory and executes it, and how that cycle produces program flow; there, the pattern `0x41424344` will be read once more, this time as an instruction. ### Instructions and the Program Counter Source: https://academia.sh/en/courses/how-computers-work/instructions-and-the-program-counter The encoding of instructions as bit patterns, the fetch-decode-execute cycle, and how program flow arises. The previous lesson established that data resides in memory as addressed bytes. Instructions reside in the same memory, in the same form: an instruction is nothing but a bit pattern encoded according to a defined rule. The distinction between program and data is not in the hardware but in the interpretation applied to those bytes. This lesson asks: how does the processor turn a bit pattern in memory into an action, and how does it determine the next action? #### The Instruction Set Every processor family has a defined **instruction set**: a contract specifying which operations exist, which bit pattern encodes each one, and which operands each takes. The instruction set is the interface between hardware and software; two different processors that implement the same instruction set can run the same program. The typical instruction classes are few: - **Data movement** — loading from memory into a register, storing from a register to memory. - **Arithmetic and logic** — addition, subtraction, comparison, bit operations. - **Control flow** — branching, subroutine call and return. - **System** — interrupts, changing privilege level, operating system calls. Every construct in a programming language ultimately reduces to instructions from these classes. #### How an Instruction Is Encoded An instruction encoding is a pattern divided into bit fields. One field, the **opcode**, says which operation to perform; the others specify the operands. To make the structure concrete, consider a 32-bit encoding defined purely for teaching purposes. This encoding does not belong to any real processor; field layout differs across architectures. | Bit range | Field | Width | |---|---|---| | 31-24 | opcode | 8 bits | | 23-16 | destination register | 8 bits | | 15-8 | first source | 8 bits | | 7-0 | second source | 8 bits | If the course's shared example is decoded under this rule: $$ \texttt{0x41424344} \rightarrow \underbrace{\texttt{0x41}}_{\text{op}}\ \underbrace{\texttt{0x42}}_{\text{dest}}\ \underbrace{\texttt{0x43}}_{\text{src 1}}\ \underbrace{\texttt{0x44}}_{\text{src 2}} $$ If opcode `0x41` is assumed to mean "add", the instruction says: add the contents of registers 67 and 68, write the result to register 66. The same thirty-two bits have now been interpreted four times over the course of this topic: as an integer, a floating-point number, text, and now an instruction. Which interpretation applies to the pattern is decided by where the processor reads those bytes from — as an instruction, or as data. Fixed-length encodings (every instruction the same width) simplify the decode stage. Variable-length encodings instead shrink program size by fitting frequently used instructions into fewer bytes. Both approaches are common, and the choice reflects the architecture's design priorities. #### Machine Language and Assembly Writing bit patterns by hand is error-prone. **Assembly** is a one-to-one representation that gives each instruction a readable name: ``` load r1, [1000] ; load the value at address 1000 into r1 load r2, [1004] add r3, r1, r2 ; r3 = r1 + r2 store [1008], r3 ``` The relationship between assembly and machine language is nearly one-to-one: each line translates to one instruction. A line in a high-level language, by contrast, can correspond to dozens of instructions; that translation is performed by the compiler and is covered in this topic's final lesson. #### The Fetch-Decode-Execute Cycle From the moment it powers on until it powers off, the processor repeats a single cycle: 1. **Fetch.** The instruction is read from the address the program counter points to. 2. **Decode.** The bit fields are parsed; the opcode and operands are determined. 3. **Execute.** The operation is carried out by the arithmetic and logic unit or the memory unit. 4. **Write back.** The produced value is written to the destination register or to memory. 5. The program counter advances to the next instruction, and the cycle starts over. The **program counter** is a special register that holds the address of the next instruction. For ordinary instructions it increases by the instruction width at every step; this is why a program flows "top to bottom". This cycle is the definition of everything the processor does. The difference between an operating system, a browser, or a game lies not in the cycle but in the sequence of instructions it reads. #### Overlapping the Steps The steps of the cycle use different hardware units: fetching occupies the memory interface, decoding the control unit, executing the arithmetic unit. Waiting for each step in sequence leaves most of these units idle at any given moment. A **pipeline** closes this gap: while one instruction executes, the next is decoded, and a third is fetched. The time to complete a single instruction does not change; the number of instructions completed per unit of time increases. The cost of a pipeline is branching. In a conditional branch, the address of the next instruction is unknown until the condition is computed; which instructions to feed into the pipeline is uncertain. The processor makes a prediction, and if the prediction is wrong, it discards the instructions already in the pipeline. Branches that are hard to predict therefore carry a measurable cost. This repeats an observation from the first topic: instruction count is not the sole determinant of duration. #### Changing the Flow The fact that the program counter can be written to directly is the source of every control structure. An **unconditional branch** writes a new address to the program counter; flow continues from there. A **conditional branch** first examines the result of a comparison. Comparison instructions write their result to flag bits — whether the result is zero, negative, or overflowed. A conditional branch reads these flags and changes the program counter only if the condition holds. The correspondence with high-level constructs is built this way: | Construct | Instruction equivalent | |---|---| | `if` | Compare; branch to the end of the block if the condition fails | | `while` | A branch testing the condition + a branch back to the top at the end of the body | | Function call | Save the return address, branch to the target; on return, branch to the saved address | Where the return address is saved during a function call is the function of the call stack; stack layout is covered in this topic's final lesson. The following program simulates the fetch-decode-execute cycle on the teaching encoding: ```python OP_NAMES = {0x41: "add", 0x42: "subtract", 0xFF: "halt"} def decode(instruction: int) -> tuple[str, int, int, int]: """Splits a 32-bit instruction into its fields.""" op = (instruction >> 24) & 0xFF dest = (instruction >> 16) & 0xFF src1 = (instruction >> 8) & 0xFF src2 = instruction & 0xFF return OP_NAMES.get(op, "unknown"), dest, src1, src2 def run(memory: list[int], registers: dict[int, int]) -> None: pc = 0 # program counter while pc < len(memory): op, dest, s1, s2 = decode(memory[pc]) if op == "halt": break if op == "add": registers[dest] = registers.get(s1, 0) + registers.get(s2, 0) elif op == "subtract": registers[dest] = registers.get(s1, 0) - registers.get(s2, 0) pc += 1 # advance to the next instruction print(decode(0x41424344)) # ('add', 66, 67, 68) memory = [0x41424344, 0x42024344, 0xFF000000] registers = {67: 10, 68: 4} run(memory, registers) print(registers[66], registers[2]) # 14 6 ``` The `pc += 1` line is the program counter's ordinary advance. If a branch instruction were added, all it would do is write a different value to this variable. #### Summary - Instructions reside in memory just like data; the distinction lies in the interpretation applied to the bytes. - The instruction set is the contract between hardware and software, and it contains a small number of instruction classes. - An instruction is a bit pattern divided into opcode and operand fields; field layout is architecture-specific. - The processor continuously repeats the fetch-decode-execute cycle; the difference between programs lies not in the cycle but in the sequence of instructions read. - The program counter holds the address of the next instruction; conditional and unconditional branches produce every control structure by changing this register. #### Next Step Every turn of the cycle requires at least one memory access, and as the previous lesson showed, main memory is hundreds of times slower than the processor. The next lesson covers the cache layer that closes this gap, and the access pattern a program must follow for the cache to work efficiently. ### The Processor Cache Source: https://academia.sh/en/courses/how-computers-work/processor-cache Cache layers, the locality principle, the cache line, and the effect of access pattern on performance. The previous two lessons placed two facts side by side: the processor operates only on registers, and a main memory access can take hundreds of clock cycles. If these two facts were combined directly, the processor would spend nearly all its time waiting. This lesson's subject is the layer that closes that gap: the **cache**. The cache is managed by hardware and is invisible to the program; but the program's behavior determines whether the cache does its job. This is why, despite being an invisible layer, it must be understood. #### The Locality Principle The cache's operation rests on a single observation: programs' memory accesses are not random. Two tendencies are observed. **Temporal locality:** An address accessed recently is likely to be accessed again soon. A loop counter is read and written on every iteration throughout the loop. **Spatial locality:** If an address has been accessed, neighboring addresses are likely to be accessed too. A loop that walks an array from start to end reads consecutive addresses in order; because instructions also sit consecutively in memory, instruction flow shows the same tendency. The cache exploits both tendencies: it keeps recently used data (temporal) and fetches a datum's neighbors along with it when requested (spatial). #### The Cache Line The exchange between cache and main memory is not carried out one byte at a time. The unit of transfer is the **cache line**; its width varies by hardware and is typically tens of bytes. This has a direct consequence: when a byte is requested, the entire line it belongs to is fetched. Reading one four-byte integer and reading the sixteen integers that share its line cost the same in terms of memory traffic. An access yields one of two outcomes: - **Hit:** The requested data is in the cache; access is fast. - **Miss:** The data is not in the cache; a line is fetched from a lower layer, and the processor waits during that time. Fetching a new line while the cache is full requires evicting an existing one. Which line gets evicted is decided by the **eviction policy**; the most common approach evicts the line that has gone unused the longest. The same principle recurs in every layer where the concept of caching appears — database caches, content delivery networks, browser caches. #### Layers The cache is not a single unit; it consists of layers graded from speed toward capacity. The layer closest to the core is the smallest and fastest; moving outward, capacity grows and latency increases. The lower layers are usually shared across cores. This layering fills the middle of the memory hierarchy introduced in the previous lesson. Numeric values vary by hardware; what does not vary is the principle that each layer is a slower, larger copy of the one above it. There is one more distinction: in most designs, instructions and data are kept in separate caches at the level closest to the core. Instruction flow and data flow have different access patterns, and neither is meant to evict the other's lines. #### The Consequence of Access Pattern The locality principle explains why two programs doing the same work can perform differently. Consider summing a two-dimensional table. The table is stored in memory row by row: a row's elements sit at consecutive addresses, and the row below it starts one row's length further along. **Traversing by row** reads consecutive addresses. The first access misses and fetches the whole line; the following accesses hit. **Traversing by column** skips one row's length on every step. Only one element of the fetched cache line is used; the rest can be evicted unused. Both loops perform the same number of additions; the difference lies in memory traffic. This difference can be computed without measuring time: by counting the number of cache lines fetched. ```python LINE_BYTES = 64 # example cache line width ELEMENT_BYTES = 8 # width of one integer N = 1024 # N x N table elements_per_line = LINE_BYTES // ELEMENT_BYTES # elements per line: 8 # By row: all eight elements of each fetched line are used. by_row = N * N // elements_per_line # By column: consecutive accesses are N * ELEMENT_BYTES bytes apart. # If the table does not fit in the cache, only one element of the fetched line is used. by_column = N * N print(by_row, by_column) # 131072 1048576 print(by_column / by_row) # 8.0 ``` For the same number of additions, the amount of data moved differs by a factor of eight, and that factor is the number of elements that fit in a cache line. As elements shrink, the factor grows: sixteen for four-byte elements, sixty-four for one-byte elements. This calculation does not directly yield the actual duration. The measured difference is determined together with prefetching, address translation, and the memory controller's behavior. In interpreted languages, the per-element interpretation cost masks most of the difference; the locality effect is therefore measured most clearly in languages that store elements contiguously and carry no per-element interpretation cost. #### Write Policies So far, reading has been described. Writing requires an additional decision: when is modified data transferred to the lower layer? In the **write-through** policy, every write is applied to both the cache and the lower layer. The layers are consistent at every moment; the cost is that every write reaches the slow layer. In the **write-back** policy, writing is done only to the cache; the line is marked **dirty** and is written to the lower layer only when evicted. Successive writes to the same line collapse into a single transfer; in exchange, the lower layer carries a stale value for a while. The same two options appear in every layer where caching is used; database and application caches refer to them by the same names. Multi-core systems raise an additional problem: a copy of the same memory line can sit in more than one core's cache. When one core modifies its copy, the copies held by the others become invalid. Hardware maintains this consistency through an inter-core protocol. The visible consequence is that threads running on different cores writing frequently to the same cache line degrade performance, even when the data is not logically shared. #### Consequences Visible to the Program The cache cannot be controlled directly, but data layout and access order can be chosen. The common traits of cache-friendly code are: - **Contiguous layout.** Arrays that store elements contiguously produce fewer misses than structures whose elements sit in separate locations linked by pointers. This is the performance dimension of the linked-list-versus-array comparison in the data structures course. - **Matching access order to layout order.** Data is placed in the order it will be read. - **Keeping hot data small.** If the data touched on every iteration of a loop fits in one cache layer, the loop draws only hits throughout. - **Not carrying unused fields.** Unused fields inside a structure reduce the amount of useful data per line. None of these principles requires premature optimization. The meaningful order is: correct and readable code first, then measurement, then applying these principles where the measurement points. #### Summary - The cache is a hardware-managed intermediate layer that closes the speed gap between the processor and main memory. - Its operation rests on the locality principle: temporal locality predicts that recently used data will be used again, spatial locality that neighboring addresses will be accessed. - The unit of transfer is the cache line; when a byte is requested, the entire line is fetched. - Hits are fast, misses are costly; when the cache is full, the eviction policy decides which line is removed. - Two loops doing the same work run in different times depending on access pattern; sequential access is faster than jumping access. - The cache cannot be controlled directly; what can be controlled is data layout and access order. #### Next Step Up to this point, the processor has been treated as a closed system executing instructions in an order it determines itself. But the outside world — the keyboard, the disk, the network interface, the timer — demands the processor's attention. The next lesson covers how that demand is communicated and how the flow is interrupted. ### Interrupts Source: https://academia.sh/en/courses/how-computers-work/interrupts Notifying the processor of external events, saving context, interrupt types, and the foundation of preemptive multitasking. The previous lessons treated the processor as a closed system: it fetches instructions, decodes them, executes them, and moves to the next one. A computer, however, interacts with the outside world. A key is pressed, a disk read completes, a packet arrives from the network. When these events will occur cannot be known in advance. This lesson asks: how is a processor occupied with its own cycle notified that something has happened in the outside world? #### Polling and Its Limit The first solution that comes to mind is **polling**: the program asks the device's status at regular intervals. ``` loop: read device status if data not ready, go to loop process data ``` Polling has two costs. If the device stays unready for a long time, the processor spins without producing any work; each query spends a memory access and a few instructions. If, on the other hand, the query interval is widened, latency increases instead: the time between the event occurring and it being noticed grows longer. Polling is not bad under every condition. When events arrive very frequently and at predictable intervals, polling can cost less than the fixed overhead of interrupt handling. It cannot, however, serve as a general solution. #### The Interrupt Mechanism An **interrupt** is a signal a device sends to the processor. When the processor receives this signal, it completes the instruction it is executing and transfers flow elsewhere on its own. The steps are: 1. The instruction currently executing completes. 2. **The context is saved:** the program counter and the necessary registers are written aside so that flow can later resume where it left off. 3. Using the interrupt number, the address of the relevant handler is read from the **interrupt vector table**. 4. This address is written to the program counter; the **interrupt handler** runs. 5. When the handler finishes, the context is restored, and the interrupted program continues without noticing it was interrupted. From the interrupted program's point of view, nothing has happened: the registers are the same, the program counter is where it is expected to be. Only the elapsed time differs. This mechanism's cost is not zero. Saving and restoring context does a few instructions' worth of work and can disturb cache contents. Keeping interrupt handlers short is therefore a design rule: the handler does only what is urgent, and leaves long-running work to a task that runs afterward. #### Types of Interrupts The events that interrupt flow are not all of one kind. A **hardware interrupt** is asynchronous: it comes from an external device and has no relation to which instruction the program is on. The keyboard, disk controller, network interface, and timer belong to this class. An **exception**, or **trap**, is synchronous: it is produced by the instruction currently executing. Division by zero, an invalid instruction, an unauthorized memory access, and a page fault belong to this class. Rerunning the same program with the same input produces the exception at the same point. The distinction is practical: an asynchronous interrupt can be deferred, a synchronous exception cannot — the instruction cannot complete until the exception is handled. A **software interrupt** is a trap the program produces at its own request, and it underlies operating system calls. A user program cannot directly access hardware for work that requires privilege (opening a file, creating a network socket); instead, it produces a trap, privileged code runs, and returns the result. The boundary between user mode and kernel mode is drawn at this point. #### The Timer Interrupt and Preemption The most important interrupt does not come from the outside world but from the processor's own timer. This timer produces an interrupt at regular intervals. The consequence is decisive: no program can hold the processor indefinitely. When the timer interrupt arrives, control passes to the operating system; the operating system saves the running program's context, loads another program's context, and flow continues from there. This scheme is called **preemptive multitasking**. Without preemption, multitasking would depend on programs' voluntary cooperation; a single program caught in an infinite loop would lock up the entire system. Process and thread scheduling, in the operating system concepts course, is built on this foundation. #### Direct Memory Access Interrupts make it cheap for a device to say "I'm ready"; but if moving the data is still the processor's job, the gain stays limited. Taking a block read from disk byte by byte into registers and writing it to memory ties the processor down to the moving work. **Direct memory access** hands the transfer off to a separate controller. The processor only defines the request: source, destination address, and length. The controller carries out the transfer itself; the processor executes other instructions in the meantime. When the transfer finishes, the controller produces an interrupt. This scheme reveals the real gain of interrupts: the processor neither waits for the data nor moves it; it only starts the transfer and is notified when it finishes. The same principle continues in higher layers — asynchronous input/output interfaces repeat the "issue the request, collect the result when notified" pattern at the software level. The cost is that shared memory now has two writers: while the controller modifies memory, the processor's cache may hold a stale copy of that region. Maintaining consistency is the responsibility of hardware and the driver. #### Masking and Priority A new interrupt can arrive while an interrupt handler is running. Hardware manages this with two tools. **Masking:** Specific interrupts can be temporarily suppressed. Short pieces of code that would produce an inconsistent state if interrupted — critical sections — run with interrupts disabled. Keeping this period long directly increases the system's delay in responding to external events. **Priority:** Interrupts are graded by importance; a high-priority interrupt can interrupt a low-priority handler. Nested interrupts mean contexts accumulate on the stack. There is also a class of interrupts that cannot be suppressed at all: non-maskable interrupts, reserved for events such as hardware failure, for which deferral would be meaningless. #### Reflection in the Program An interrupt is a hardware-level concept, but its traces are visible in software. An operating system signal is the process-level equivalent of an interrupt: wherever flow happens to be, the registered handler runs and flow then continues from where it left off. ```python import signal, time interrupt_count = 0 def timer_handler(signal_num, frame): """Runs wherever flow happens to be, then returns.""" global interrupt_count interrupt_count += 1 signal.signal(signal.SIGALRM, timer_handler) signal.setitimer(signal.ITIMER_REAL, 0.05, 0.05) # a signal every 50 ms start = time.perf_counter() counter = 0 while time.perf_counter() - start < 0.5: # half a second of a busy loop counter += 1 signal.setitimer(signal.ITIMER_REAL, 0) # stop the timer print(interrupt_count) # around 9 ``` The loop contains no line waiting for the signal; yet the handler has run roughly nine times. This is the distinguishing trait of the interrupt concept: control is transferred without the flow itself requesting it. The limit of this analogy should also be noted. Operating system signals are not hardware interrupts; the runtime processes them at safe points. Still, the idea of flow being interrupted from outside is the same. The same idea continues in higher layers: asynchronous input/output, event loops, and callback-based interfaces are the software-level equivalents of the "notify me when ready" principle. #### Summary - Polling queries device status at regular intervals; it either spends processor time or increases latency. - An interrupt is a signal a device sends to the processor; the processor saves the context, runs the handler, and resumes flow from where it left off. - Hardware interrupts are asynchronous, exceptions are synchronous; software interrupts underlie operating system calls. - The timer interrupt ensures no program can hold the processor indefinitely, and makes preemptive multitasking possible. - Interrupts are masked in critical sections; the longer masking lasts, the more the system's response delay grows. - Interrupt handlers are kept short; saving and restoring context is costly. #### Next Step This topic's remaining question is the operation itself: what happens in hardware when an add instruction runs? The next lesson shows how arithmetic is built from logic gates, and why two's complement representation needs no separate circuit for subtraction. ### The Hardware Implementation of Arithmetic Source: https://academia.sh/en/courses/how-computers-work/hardware-implementation-of-arithmetic From logic gates to adder circuits, how subtraction reuses the same circuit, and how status flags are produced. The second lesson stated that the `add` instruction writes a result to register 66, but left open how that result is produced. This lesson fills that gap: what structures in hardware carry out addition? The answer combines two lessons from the first topic: the AND, OR, and XOR operations defined in the bit-level operations lesson, and the two's complement representation defined in the signed integers lesson. Brought together, these two build the entire arithmetic unit. #### Logic Gates A **logic gate** is a physical circuit element that produces one output bit from one or two input bits. Its behavior is identical to the truth tables defined in the previous topic: an AND gate produces $1$ only if both inputs are $1$, an OR gate if at least one is $1$, an XOR gate if the inputs differ. This also explains the origin of that lesson's operators: the expression `a & b` means as many AND gates as the word is wide, all operating at once. This is why bit-level operations are cheap — a single gate suffices per bit, and bits do not wait on each other. Arithmetic, however, breaks this independence: a digit's result depends on the carry bit coming from the digits below it. #### The Half Adder Adding two bits is the same as addition done by hand. The operation $1 + 1$ leaves $0$ at that digit and carries $1$ to the digit above. | $a$ | $b$ | Sum | Carry | |---|---|---|---| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 | The sum column is identical to the XOR table, the carry column to the AND table: $$ \text{sum} = a \oplus b, \qquad \text{carry} = a \wedge b $$ This two-gate circuit is called a **half adder**. Its name reflects a deficiency: it does not account for the carry coming from the digit below. #### The Full Adder In a real addition, every digit has three inputs: two bits and the carry coming from the digit below. The circuit that processes these three inputs is the **full adder**: $$ \text{sum} = a \oplus b \oplus c_{\text{in}} $$ $$ c_{\text{out}} = (a \wedge b) \vee \big(c_{\text{in}} \wedge (a \oplus b)\big) $$ The carry expression can be read in words: a carry is produced if both bits are $1$; or if exactly one bit is $1$ and a carry comes from the digit below. #### The Ripple-Carry Adder An $n$-bit addition is built by chaining $n$ full adders: each adder's carry output connects to the carry input of the adder above it. This arrangement is called a **ripple-carry adder**. The chain has a cost: the top digit's result is not stable until the carry bit has propagated through every digit. The circuit's delay grows in proportion to the number of bits. Reducing this delay is a classic problem in digital design. Designs that compute carry bits directly from the input bits, rather than waiting for them digit by digit — carry-lookahead adders — achieve shorter delay by using more gates. This trade-off between area and speed repeats at every layer of hardware design. #### Subtraction Needs No Separate Circuit The signed integers lesson stated that two's complement is preferred because it leaves the addition circuit unchanged. Its counterpart in the circuit is this: $$ a - b = a + (\lnot b) + 1 $$ The value $\lnot b$ is produced by passing $b$'s bits through XOR gates; the trailing $+1$ is supplied by feeding $1$ into the lowest adder's carry input. A single control bit thus governs both the inversion and the carry input: at $0$ the circuit performs addition, at $1$ it performs subtraction. Comparison operations use the same circuit. Comparing two values means computing their difference and examining the result's flags; the result itself is not stored. #### Status Flags The arithmetic and logic unit produces, alongside the result, bits that qualify it. Four flags are common: | Flag | Condition that sets it | |---|---| | Zero | All bits of the result are $0$ | | Sign | The result's leftmost bit is $1$ | | Carry | The carry out of the top digit is $1$ (unsigned overflow) | | Overflow | The carry into and out of the top digit differ (signed overflow) | The last row is the hardware definition of signed overflow. When two positive numbers are added, if a carry enters the top digit but does not exit it, the result has overflowed into the sign bit — the value appears negative. This is exactly what happens in the example $127 + 1$. Keeping the carry and overflow flags separate lets the same addition circuit support both the unsigned and signed interpretations. Which flag is meaningful is decided by the program, which knows under which interpretation it is using the value. Conditional branch instructions also read these flags. #### Building the Circuit in a Program The following program builds the full adder and an eight-bit ripple-carry adder using bit-level operators: ```python def full_adder(a: int, b: int, carry_in: int) -> tuple[int, int]: """Produces the sum and carry-out bits from three input bits.""" total = a ^ b ^ carry_in carry_out = (a & b) | (carry_in & (a ^ b)) return total, carry_out def add(x: int, y: int, bits: int = 8, subtract: bool = False) -> dict: """Ripple-carry adder; if subtract=True, computes x - y.""" carry = 1 if subtract else 0 result = 0 for i in range(bits): a = (x >> i) & 1 b = ((y >> i) & 1) ^ (1 if subtract else 0) # b is inverted for subtraction if i == bits - 1: top_carry_in = carry # carry entering the top digit t, carry = full_adder(a, b, carry) result |= t << i return { "result": result, "zero": result == 0, "sign": ((result >> (bits - 1)) & 1) == 1, "carry": carry == 1, "overflow": top_carry_in != carry, } print(add(5, 3)) # 8, no overflow print(add(5, 3, subtract=True)) # 2, subtraction in the same circuit print(add(127, 1)["overflow"]) # True — signed overflow print(add(255, 1)["carry"]) # True — unsigned overflow print(add(255, 1)["result"]) # 0 — wrapped around ``` The `subtract` flag being used in two places at once — both in inverting `b`'s bits and in the initial carry — is the counterpart of the single control bit in hardware. The outputs confirm the claims made in the first topic: $255 + 1$ wraps around under the unsigned interpretation, $127 + 1$ sets the overflow flag under the signed interpretation. That lesson stated that "hardware reports both kinds of overflow through separate flags"; the circuit in this lesson is the very structure that produces those flags. #### Summary - Logic gates are the physical counterpart of bit-level operators; because every bit is processed independently, these operations are cheap. - A half adder adds two bits: the sum is produced by an XOR gate, the carry by an AND gate. - A full adder also accounts for the carry from the digit below; chaining $n$ full adders gives an $n$-bit adder. - Chaining delay grows with the number of bits; carry-lookahead designs reduce the delay by using more gates. - Subtraction needs no separate circuit: the second operand is inverted and $1$ is fed into the carry input. - Alongside the result, the arithmetic unit produces zero, sign, carry, and overflow flags; carry reports overflow under the unsigned interpretation, overflow under the signed one. #### Next Step This topic has established how data resides in memory and how instructions are executed in hardware. One link remains: how does the text a programmer writes turn into these instructions? The next topic covers the chain that reaches from source code to a running process — the steps of compiling, linking, and loading. ## From Source to Executable How source text is compiled, linked, and loaded into memory to become a running process. ### Compiler, Interpreter, and Virtual Machine Source: https://academia.sh/en/courses/how-computers-work/compiler-interpreter-and-virtual-machine Three models for executing source code, the trade-offs between them, and the distinction between a language and its implementation. The previous topic established that the processor executes bit patterns in memory as instructions. A programmer does not write bit patterns; a programmer writes readable text. A program closes the gap between the two. This lesson asks: how does the line `result = a + b` turn into instructions the processor can execute? This lesson defines three models that differ in when the conversion happens; the following lessons take up the conversion itself, step by step. #### Source Code Is Text A source file is a sequence of bytes written according to the rules defined in the character encodings lesson. The `if`, `+`, or variable names inside it carry no meaning for the computer yet; they are only characters. There are three ways to turn this text into executable behavior. All three do the same job; they differ in **when the translation** happens. #### Compilation A **compiler** translates the entire source text into the target machine's instructions before execution. The output is a directly executable file. Consequences: - There is no translation cost at run time; the program runs directly at processor speed. - Because the compiler sees the whole program, it can optimize extensively. - A portion of errors are caught before execution, during compilation. - The output is tied to a specific instruction set and operating system; another platform requires recompilation. - Every change to the source requires a compilation step before it can run. #### Interpretation An **interpreter** does not translate the source in advance; it reads constructs in sequence and carries out the corresponding operations itself. Translation continues while the program runs. Consequences: - The same source runs on any platform that has an interpreter for it; no separate compilation is required. - The cycle between writing and running is short. - Every construct is resolved anew each time it executes; this adds a fixed cost per instruction. - Most errors remain invisible until the corresponding line executes. This explains why the cache lesson's calculation was not demonstrated with a timing measurement: when interpretation adds a fixed cost per element, the difference coming from memory behavior is buried under that cost. #### Virtual Machine and Bytecode The third model combines the two: the source is translated not into a real processor's instruction set, but into that of a designed machine called a **virtual machine**. This intermediate representation is called **bytecode**. Bytecode is compact and cheap to parse compared to source text, and platform-independent compared to machine code. The virtual machine is the program that executes bytecode; writing one virtual machine per platform is less work than writing a separate compiler for each. The cost of this layer is speed: bytecode executes slower than native instructions. **Just-in-time compilation** reduces this cost. The virtual machine detects frequently executed sections while running and translates them into native machine code. The translation cost is paid once, and the gain is collected on every repetition. Just-in-time compilation has two observable consequences. The first is **warm-up**: a program's early iterations run slower than later ones, so performance measurements skip them. The second is access to run-time information: where a compiler must guess which branch actually runs, a just-in-time compiler can decide by observing. #### Separating a Language from Its Implementation A common confusion is assuming these models belong to the language itself. The phrases "compiled language" and "interpreted language" are misleading. A language is defined by its syntax and semantics; how it executes is a decision made by the **implementation**. The same language can have both a compiler and an interpreter, and in practice both are often written. Languages known for being interpreted have compilers, and languages known for being compiled have interpreters. The accurate statement is: *this implementation of this language translates the source into bytecode and executes it on a virtual machine.* This distinction shows which level a claim about a language's performance actually belongs to. #### Who Translates the Translator A compiler is itself a program, written in some language. This raises a question that looks circular at first: what language is a language's first compiler written in? The answer is simple: another language. The new language's first compiler is written in an existing language and translates a small subset of it. Once that compiler works, the language's own compiler can be rewritten in the language itself and built with the first one. From then on, the compiler compiles itself; this is called a **self-hosting** compiler. The same reasoning applies to interpreters and virtual machines. At the bottom of the chain, there is always a program that already runs on that platform. The practical consequence: a language's execution model depends not on its definition but on the history of its ecosystem. A later implementation of the same language can choose an entirely different model. #### Comparing the Three Models | Criterion | Compilation | Interpretation | Virtual machine | |---|---|---|---| | Translation time | Before execution | Continuously while running | First to bytecode, then while running | | Portability | Tied to the target platform | Anywhere an interpreter exists | Anywhere a virtual machine exists | | Execution speed | Highest | Lowest | In between; increases with just-in-time compilation | | Feedback loop | Requires a compilation step | Shortest | Short | | Error detection | A portion during compilation | At run time | Between the two | The boundaries are not sharp. A compiled language can have a runtime library; an interpreted language can translate the source into an intermediate representation first. The models are axes that real implementations sit on. #### Seeing the Two Stages Python stands between the second and third of these three models: the source is first translated into bytecode, then executed on a virtual machine. The two stages can be invoked separately: ```python source = "result = a + b" code = compile(source, "", "exec") # first stage: text -> code object print(type(code)) # print(code.co_names) # ('a', 'b', 'result') environment = {"a": 10, "b": 4} exec(code, environment) # second stage: execution print(environment["result"]) # 14 import dis dis.dis(code) # listing of the generated bytecode ``` The `compile` call executes nothing; it only parses the text and produces a code object. Execution is started separately with the `exec` call. That the two steps can be separated is direct proof that translation is a different task from execution. The instruction names and count in the `dis` output vary by the implementation's version; bytecode is not a standard but an internal detail of the virtual machine. What is stable is the existence of the listing: the source text has become a sequence of instructions before execution. #### Summary - Source code is text; it must be translated into machine instructions before it can execute. - A compiler translates before execution: it provides speed and compile-time error detection, and the output is tied to a platform. - An interpreter translates while running: it provides portability and a short feedback loop, and adds a cost per instruction. - The virtual machine model translates the source into platform-independent bytecode; just-in-time compilation closes the gap by translating frequently executed sections into native code. - Being compiled or interpreted is a property of the implementation, not the language. - A language's first translator is written in another language; it can later transition to a translator that compiles itself. #### Next Step This lesson addressed when translation happens, not how. The next lesson will open the source text's path from characters to instructions stage by stage: tokenizing, extracting structure, semantic checking, and code generation. ### Compilation Stages Source: https://academia.sh/en/courses/how-computers-work/compilation-stages The stages of lexical analysis, parsing, semantic checking, intermediate representation, and code generation. The previous lesson defined three models based on when translation happens. This lesson opens up the translation itself: what steps does source text pass through on its way to becoming instructions? The steps are nearly the same across almost every implementation. An interpreter and a compiler do the same work in the early stages; the paths diverge at the final generation step. #### Lexical Analysis The first stage splits the character sequence into the smallest meaningful units. These units are called **tokens**. The line `total = 3 + 4 * 2` splits into the following tokens: | Token | Type | |---|---| | `total` | name | | `=` | assignment operator | | `3` | number literal | | `+` | addition operator | | `4` | number literal | | `*` | multiplication operator | | `2` | number literal | At this stage, whitespace and comments are discarded, and number literals are converted from character sequences into numeric values. The lexical analyzer does not concern itself with structure: `3 + * 4` also tokenizes without a problem, because each token is valid on its own. Errors produced at this stage are cases such as characters that do not belong to the language's alphabet, or unterminated string literals. #### Parsing The second stage checks whether the tokens conform to the language's grammar and, if they do, builds the structure as a tree. This tree is called an **abstract syntax tree**. The tree for the expression `3 + 4 * 2` embeds operator precedence in its structure: ``` + / \ 3 * / \ 4 2 ``` That multiplication happens before addition is encoded by its node sitting deeper in the tree: a node above cannot be evaluated until the node below it has been. Precedence rules are enforced through how the grammar is written; there is no separate "precedence check" step. Errors from the parsing stage relate to the order of tokens: an unclosed parenthesis, a missing operand, an unexpected keyword. #### Semantic Checking Not every syntactically correct program is meaningful. The line `total = undefined_name + 1` conforms to the grammar, but it cannot execute if it is unknown what the name refers to. At this stage the compiler builds a **symbol table**: it records where each name is defined, its type, and its scope. The tree is checked against this table: - Are the names used defined? - Are the operand types of the operators compatible? - Is the type conversion in assignments valid? - Are the argument count and types correct in function calls? In statically typed languages, most of these checks happen during compilation. In dynamically typed languages, type information is carried on values at run time; the same errors surface when the corresponding line executes. The two approaches differ in **when** the error is seen. #### Intermediate Representation and Optimization The tree can be translated directly into machine code, but most compilers insert a layer in between: an **intermediate representation** that is not tied to any specific processor. The intermediate representation has two benefits. Optimizations are written here independently of the target machine; and for $m$ languages and $n$ target architectures, it is enough to write $m + n$ components, not $m \times n$. Typical optimizations at this level: - **Constant folding:** The expression `3 + 4 * 2` is computed during compilation rather than at run time, and `11` is put in its place. - **Dead code elimination:** Computations whose results are used nowhere are removed. - **Common subexpression elimination:** A repeated occurrence of the same computation is performed once and cached. - **Loop-invariant code motion:** A computation that does not change across a loop is moved before the loop. The limit of optimization is leaving the program's **observable behavior** unchanged. This explains why floating-point arithmetic cannot be freely reordered: addition lacks the associative property, so changing the order can change the result. #### Code Generation The final stage translates the intermediate representation into the target instruction set. Architecture-specific decisions are made here: - **Instruction selection:** The same operation can be carried out with more than one instruction sequence; the cheapest is chosen. - **Register allocation:** Which values are kept in registers and which are moved to memory. Because the number of registers is limited, this is one of the compiler's most difficult tasks. - **Instruction scheduling:** Instructions can be reordered so that the pipeline does not sit idle. One more external rule applies at this stage: the **calling convention**. It specifies which registers or stack locations hold arguments, where the return value is carried, and which registers the callee must preserve. Separately compiled files can call one another only if all of them follow the same convention; the convention is a definition of the target platform, not of the compiler. Interpreters skip this stage: they execute the tree or the bytecode directly. In the virtual machine model, the target is the virtual machine's instruction set, not a real processor. #### Error Reporting and Recovery A compiler can stop and exit at the first error. This behavior is inefficient for the developer: every error would require a separate compilation run. For this reason, parsers apply **error recovery** — they report the error, skip tokens up to a consistent point, and continue parsing. The cost of recovery is cascading errors: a single unclosed parenthesis can make the following constructs appear in the wrong position and produce dozens of additional error messages. The practical rule: the first message is the most reliable one; the ones after it may be derivatives of the first. The quality of an error message is also a design matter. A good message says three things: what the problem is, where it occurred, and what was expected. To this end, the parser carries the source location (line and column) on every node it produces; this information is preserved throughout the tree and used again during semantic checking. #### Seeing the Stages in Code The following program implements the first two stages on a small expression language and demonstrates the third stage using the standard library: ```python import re, ast PATTERN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|(.))") def tokenize(text: str) -> list[tuple[str, str]]: """Splits source text into (type, value) pairs.""" tokens = [] for number, name, symbol in PATTERN.findall(text): if number: tokens.append(("number", number)) elif name: tokens.append(("name", name)) elif symbol.strip(): tokens.append(("symbol", symbol)) return tokens print(tokenize("total = 3 + 4 * 2")) # [('name', 'total'), ('symbol', '='), ('number', '3'), ('symbol', '+'), # ('number', '4'), ('symbol', '*'), ('number', '2')] tree = ast.parse("3 + 4 * 2", mode="eval") print(ast.dump(tree.body, annotate_fields=False)) # BinOp(Constant(3), Add(), BinOp(Constant(4), Mult(), Constant(2))) ``` The `ast.dump` output is the text form of the tree from the parsing section: the outer node is addition, and its right operand is the multiplication node. Precedence is built into the shape of the tree. In the same program, the lexical analyzer can be shown to tokenize `3 + * 4` without any problem, while `ast.parse` raises a syntax error on the same input; this directly demonstrates that the two stages ask different questions. #### Summary - Lexical analysis splits the character sequence into tokens and discards whitespace. - Parsing checks whether the tokens conform to the grammar and builds the abstract syntax tree; operator precedence is encoded in the shape of the tree. - Semantic checking tests name and type compatibility against the symbol table; statically and dynamically typed languages perform this check at different times. - The intermediate representation makes optimizations independent of the target architecture and reduces the number of language-architecture combinations. - Code generation makes the decisions of instruction selection, register allocation, and instruction scheduling. - A compilation error is read more quickly when the stage that produced it is known. #### Next Step Code generation produces a separate output for each source file. But a program does not consist of a single file, and the libraries it uses have been compiled elsewhere. The next lesson takes up how these pieces are linked into a single executable whole and how they are loaded into memory at run time. ### Linking and Loading Source: https://academia.sh/en/courses/how-computers-work/linking-and-loading Object files, symbol resolution, static and dynamic linking, and loading a program into memory. The previous lesson said that code generation produces a separate output for each source file. A real program, however, consists of many files, and the libraries it uses have been compiled at different times and in different places. This lesson asks: how are separately compiled pieces brought together into a single running program? #### The Object File The output the compiler produces for a source file cannot be executed directly; it is called an **object file**. It contains machine code but carries incomplete information. An object file is divided into sections. Although naming varies by format, the content is common: | Section | Content | |---|---| | Code | Executable instructions | | Read-only data | Constants, string literals | | Initialized data | Global variables given an initial value | | Uninitialized data | Space to be zeroed, with only its size recorded | | Symbol table | Defined and required names | | Relocation records | Locations that require address fixing | Only the size of the uninitialized data section is stored; its content takes no space in the file, because all of it is zero. This explains why files that define large arrays can stay small. #### Symbols A **symbol** is an address bound to a name: the start of a function, or the location of a global variable. An object file lists two kinds of symbols: - **Defined symbols:** The names this file provides. - **Required symbols:** The names this file uses but that are defined elsewhere. When the compiler generates a call to a required symbol, it does not know the target address; it leaves a gap and records that gap in the relocation records — a note reading, in effect, "fill this address with the real address of the symbol named `add`." #### Linking The **linker** takes object files and libraries and produces a single output. It does three things: 1. **It merges the sections.** The code sections of all files are placed one after another, and the data sections one after another. 2. **It resolves symbols.** For every required symbol, the file that defines it is found. 3. **It fixes addresses.** The gaps in the relocation records are filled with the addresses that become final after merging. This stage has two well-known errors, and neither is a compiler error: - **Undefined symbol:** A name is used but not defined in any file. A typo, a missing library, or a function that has only a declaration and no written body produces this. - **Duplicate symbol:** The same name is defined in more than one file. The linker cannot know which one to choose. That these errors surface at the linking stage rather than compilation shows that a single file compiling without problems does not mean the whole program is correct. #### Visibility and Name Mangling Not every name in a file has to be visible to the linker. Languages divide symbols into two visibility levels: - **External visibility:** The name is written to the symbol table and can be resolved from other files. - **Internal visibility:** The name is valid only in its own file; the linker does not see it. Internal visibility serves two purposes: the same name can be used in different files without conflict, and the number of symbols the linker has to resolve is reduced. In large projects, this directly affects linking time. A second detail arises in languages where the same name can carry more than one meaning: two functions with the same name but different parameter types cannot sit under the same name in the symbol table. The compiler encodes type information into the name to produce a unique symbol; this is called **name mangling**. The name mangling scheme is specific to the compiler and is not standardized. This is the main reason object files produced by different compilers cannot be linked together; for cross-language calls, a declaration that turns off mangling is used instead. #### Static and Dynamic Linking How libraries join a program is resolved by two separate approaches. In **static linking**, the library code is copied into the output. The result is a single, large file; it looks for nothing else on the system it runs on. A fix made to the library afterward requires the program to be relinked. In **dynamic linking**, the library stays a separate file; the output only records which library it needs. Part of the linking work is deferred to the moment the program starts. | Criterion | Static | Dynamic | |---|---|---| | Output size | Large | Small | | Memory sharing | Each process carries its own copy | The same library is shared across processes | | Update | Requires relinking | All programs are affected when the library file changes | | Startup cost | None | Locating the library and resolving symbols | | Distribution | Self-sufficient | A compatible version must exist on the target system | The ease of updating in dynamic linking is also a source of fragility: finding a version different from what is expected produces a symbol error at run time. Documenting compatibility rules and version marking are, for this reason, an inseparable part of library development. #### Loading When a program is run, the **loader** takes over. What it does: 1. It places the executable file's sections into the process's address space. 2. It reserves space for the uninitialized data section and zeroes it. 3. It finds and loads the required dynamic libraries and resolves the remaining symbols. 4. It prepares space for the stack and places the starting arguments. 5. It writes the program counter to the entry point; from here, control belongs to the program. The fifth step is the beginning of the fetch–decode–execute cycle from the previous topic. The loader is the component that determines that cycle's first address. The loader may place code at an address not known in advance, so the generated code is required to be position independent. **Position independent code** uses relative addresses instead of absolute ones, letting the same library load at different addresses in different processes. #### Resolving Names at Run Time The idea behind dynamic linking — not fixing a name's target until the last moment — is taken even further in interpreted languages: name resolution happens on every access. ```python import math, sys # Importing binds the name to a module object at run time. print(type(math)) # print(math.__name__) # math # The module object is a dictionary that carries names. print("sqrt" in vars(math)) # True # The name is resolved at call time: the binding can be replaced. original_sqrt = math.sqrt math.sqrt = lambda x: "replacement" print(math.sqrt(9)) # replacement math.sqrt = original_sqrt # the original binding is restored print(math.sqrt(9)) # 3.0 # Loaded modules sit in a record similar to the table the loader keeps. print("math" in sys.modules) # True ``` The cost of this flexibility is the loss of the guarantees static linking provides: a misspelled name produces no error until the corresponding line runs. The relationship between linking time and error-detection time is the same one established for type checking in the previous lesson. #### Summary - The object file that is the compiler's output is incomplete: it lists the symbols it defines and requires, and leaves gaps for external addresses. - The linker merges sections, resolves symbols, and fixes addresses; undefined and duplicate symbol errors surface at this stage. - Static linking copies the library code into the output; dynamic linking leaves it in a separate file and defers resolution to startup. - Dynamic linking provides memory sharing and easy updates, and in return brings the responsibility of version compatibility. - The loader places sections into the address space, links the libraries, and writes the program counter to the entry point. #### Next Step The inside of the address space the loader prepares has not been opened up yet: where does the code sit, where are the global variables, where are a function call's local variables kept? The course's final lesson takes up these regions and the lifetime rule for each. ### Memory Layout — Stack and Heap Source: https://academia.sh/en/courses/how-computers-work/memory-layout A process's address space regions, how the call stack operates, allocation on the heap, and lifetime rules. The loader placed the executable file's sections into the process's address space and handed control to the program. This lesson opens up that address space: which data sits where, and for how long does it live? The question is practical. Why a function's local variable becomes invalid after the function returns; why unbounded recursion ends in a crash; why allocated memory must be freed — all of these are consequences of this layout. #### Regions of the Address Space A process's address space is divided into regions with different behaviors: ``` high addresses ┌────────────────────────────────┐ │ Stack │ grows downward ├────────────────────────────────┤ │ ... │ free space ├────────────────────────────────┤ │ Heap │ grows upward ├────────────────────────────────┤ │ Uninitialized data │ zeroed global variables ├────────────────────────────────┤ │ Initialized data │ global variables given a value ├────────────────────────────────┤ │ Read-only data │ constants ├────────────────────────────────┤ │ Code │ instructions; not writable └────────────────────────────────┘ low addresses ``` The stack and the heap growing from opposite ends lets the two share the free space between them: whichever needs more room expands into it. The code region being closed to writes is a security measure: it prevents a running program from modifying its own instructions. Likewise, data regions being closed to execution prevents bytes placed as data from being executed as instructions — this separation is one of the fundamental defenses against memory safety vulnerabilities. #### The Call Stack When a function is called, a **stack frame** for that call is pushed onto the top of the stack. A frame typically carries: - **Return address:** The address of the instruction where control resumes when the function ends. - **Arguments:** The ones that do not fit in registers. - **Local variables:** The function's own variables. - **Saved registers:** Register contents belonging to the caller that must be preserved. One register — the stack pointer — holds the address of the top. On a call, the top moves down; on a return, it moves back up. Because the only thing shifted is a register value, allocating and releasing a frame is nearly free. This layout fitting a stack structure is not a coincidence: calls are nested. The function called last is the first to return. This is the answer to the question of where the call and return instructions defined in the instructions lesson store the return address. The reason local variables become invalid when a function returns is also visible: the frame has been released, and that space will be used by the next call. Returning the address of a local variable means pointing at a location that another frame will occupy shortly after. #### Stack Overflow The stack is not infinite; it is created with a fixed upper limit per thread. The limit is exceeded in two ways: a call chain that is too deep, or local data per frame that is too large. Recursion without a base case is the canonical example of the first case. Every call adds a frame, none of them return, and the stack runs out. ```python import sys print(sys.getrecursionlimit()) # the limit set by the runtime def depth(n: int = 1) -> int: """Calls itself until the limit is reached and returns the depth attained.""" try: return depth(n + 1) except RecursionError: return n print(depth()) # a number close to the limit ``` The limit here is not the hardware's stack limit but a guard the runtime sets for itself: a controlled error is raised before the real stack runs out and the process crashes. In environments without this guard, the same program ends with the operating system terminating the process. Tail recursion, as it is defined in the Programming Fundamentals course, is one solution to this problem: if the call is in tail position, the existing frame can be reused instead of opening a new one. Not every implementation performs this transformation. #### Stack per Thread If more than one thread runs within a process, each must have its own stack: call chains are independent, and one thread's frames cannot mix with another's. The heap, on the other hand, is shared. This asymmetry sets up the fundamental tension of concurrent programming: local variables on the stack are naturally isolated, while heap data can be accessed by more than one thread at the same time. The need to protect shared state arises from this, and concurrency is the subject of the Operating System Concepts course. There is also a practical consequence: the stack space allocated per thread limits the number of threads that can be created. #### The Heap Some data has to outlive the function that created it, and its size is known only at run time. This data is allocated on the **heap**. Heap management is done by an **allocator**. The allocator tracks free blocks; it finds a block that fits the requested size, marks it, and returns its address. A freed block becomes available for reuse. This flexibility has three costs: - **Allocation is expensive.** Searching for a suitable block involves far more work than shifting a stack pointer. - **Fragmentation occurs.** Cycles of allocation and release can leave gaps that are sufficient in total but insufficient as a single block. - **Lifetime is managed by hand.** A block that is never freed is a **memory leak**; an address used after it has been freed is a **dangling pointer**, and produces undefined behavior. In languages that use a garbage collector, the third cost is handed off to the runtime: objects that become unreachable are collected automatically. The cost of this is the pauses that occur during collection and higher memory usage. The trade-off does not disappear; it only shifts location. #### Lifetimes Three separate lifetime rules correspond to three regions: | Lifetime | Location | Start | End | |---|---|---|---| | Static | Data regions | While the program loads | When the program ends | | Automatic | Stack | When the frame opens | When the function returns | | Dynamic | Heap | On an allocation request | On release or collection | A program's errors often arise from confusing these columns: accessing a value with automatic lifetime after its lifetime has ended; never releasing a block with dynamic lifetime; or modifying a shared value with static lifetime from multiple threads concurrently. #### Tying the Course Together At this point, the whole chain has been assembled. A program's text was tokenized, turned into a tree, passed through an intermediate representation and translated into machine instructions; the object files were linked, the loader placed the sections into the address space, and it wrote the program counter to the entry point. The processor began turning the fetch–decode–execute cycle; instructions operated on registers, data moved through cache layers, external events were reported through interrupts. And what all of these layers carried was the bit patterns that were the subject of the first topic. The pattern `0x41424344` was read five times across the course: as an unsigned integer, a signed integer, a floating-point number, the text `ABCD`, and an instruction. This is the course reduced to a single sentence: **memory carries no meaning; meaning comes from the interpretation rule applied to the pattern.** A programming language's type system, a file format's specification, and a network protocol's documentation all do the same job — they state which rule applies. #### Summary - A process's address space is divided into code, read-only data, initialized and uninitialized data, heap, and stack regions; the stack and the heap grow from opposite ends. - Every function call pushes a frame onto the stack; the frame carries the return address, the arguments, and the local variables. - Allocating a frame is a register shift; this makes it cheap, but the stack is bounded, and deep call chains exhaust it. - The heap is for data whose size or lifetime is determined at run time; allocation is expensive, and fragmentation and lifetime management bring cost. - Static, automatic, and dynamic lifetimes correspond to different regions; common memory errors arise from confusing the three. #### Next Step This course built the layers beneath a program — data representation, the processor, memory, and the compilation chain. The course after this one moves above that layer: **Programming Fundamentals** takes up the concepts of variables, control flow, functions, and recursion independently of any language. The code fragments used only as examples in this course will there become the subject of the lesson itself.