2 A simple model of the machine — the birth of C

What to know first

chapter 1, Setting the scene · why C is still in use

Looking back

Chapter 1 said that C is still alive inside operating systems, embedded devices and the infrastructure of the internet. How is a language past fifty still in that position?

A. Because the position C occupies is a special one. It is the lowest layer at which machine and human meet, and while machines have got faster over half a century, the skeleton of how they work is remarkably unchanged. This chapter looks straight at that skeleton. As long as the skeleton stays, so does C, the language that wraps it most thinly.

The need for this chapter, and its context

The answer to “why does C look like this” is in the hardware. So, right after chapter 1′s background and before any syntax, we start by sketching the simplest possible model of an imaginary machine. That picture will be corrected twice later — chapter 12 turns memory into a ladder, chapter 14 turns the compiler into an editor. This book handles background knowledge by giving a deliberately over-simple picture first and correcting it step by step; this chapter is where that starts.

By the end of this chapter

You will be able to draw a computer as a simple picture of three parts — a place that calculates, a place that remembers, and something that keeps time. You will learn what a bit, the smallest unit of information, is and why computers use binary in particular. And you will see how a language called C was born in the days of that simple machine.

The questions this chapter answers

Is the gigahertz (GHz) in advertising copy — “four billion times a second” — this clock?
How can games, video and artificial intelligence come out of nothing but “fetch it and do it”, repeated?
Why two states in particular? Would it not be far more efficient to put ten states, 0 through 9, into one switch?
Why eight, of all bundle sizes? Was it eight from the start, and everywhere?
How do we handle large numbers with a byte that has only 256 possible values?
Is it a disadvantage to learn, today, a language fitted to the machines of fifty years ago?

2.1 Drawing a computer as three parts#

A computer is a complicated object. But the first step in understanding anything complicated is always to draw a boldly simple picture. From here we draw the computer as exactly three parts.

First, the CPU (central processing unit). The place that calculates. It adds, compares, and decides what to do next.

Second, memory. The place that remembers. The material for the calculation and the result of the calculation both sit here.

Third, the clock. The thing that keeps time. It ticks at a steady interval like a metronome, and the CPU works one step per tick.

In this picture, what the computer does is this and nothing else: on every tick of the clock, the CPU fetches one thing to do from memory and does it. Endlessly repeated.

Q. Is the gigahertz (GHz) in advertising copy — “four billion times a second” — this clock?

A. It is. 4 GHz means the metronome ticks four billion times a second. The CPU advances one step per tick, so the faster the beat, the more steps in the same time. That said, the number of steps is not the whole story, as chapter 13 will show — doing several things in one step is the real weapon of a modern CPU.

Q. How can games, video and artificial intelligence come out of nothing but “fetch it and do it”, repeated?

A. In the same way that a brick is simple but you can build a castle out of bricks. Even simple steps, taken billions of times a second and organised in layers — small jobs into functions, functions into programs, programs into an operating system — can build anything however complicated. This “stacking in layers” is abstraction, the heart of computing, and this whole book is the story of climbing that staircase.

What the CPU fetches as “the next thing to do” is called an instruction. An instruction is nothing grand. “Add this number to that one”, “put this value in that slot”, “if the last result was zero, jump somewhere else” — brutally simple directions at about that level. A program is a list of such instructions in order, and programming is the work of writing that list in a way a human can bear.

This picture still has no outside in it — no keyboard, no screen, no disk. Bring the outside in and two questions come with it: what wires connect it, and who decides when the outside speaks. The first is answered in chapter 9, the second in chapter 11.

2.2 The bit — the smallest unit of information#

Memory, we said, is the place that remembers. What does it remember, and in what shape?

What an electronic circuit does best is distinguish two states. The voltage is high, or it is low. The switch is on, or it is off. The smallest unit of storage, holding one of those two, is called a bit. We give the two states the names 0 and 1.

A common misconception. “Somewhere inside the computer, 0s and 1s are written down like letters”

It is a plausible thought — every book and every screen paints computers as full of ones and zeros. But there are no digit-shaped characters inside the machine. What is actually there is nothing but physical state: a high or low voltage, a charge present or absent. 0 and 1 are names we attach to those physical states so we can read them — an interpretation. This distinction is not idle pedantry. Separating “what is stored” from “how it is to be read” is a theme this book returns to again and again, and it is why the same string of bits can later be read as a number or as a character (chapters 7–8).

Q. Why two states in particular? Would it not be far more efficient to put ten states, 0 through 9, into one switch?

A. Decimal computers were in fact built early on. But distinguishing ten voltage levels means narrowing the gaps between them, and narrow gaps slip into a neighbouring level under noise or a change in temperature — that is, they are easy to get wrong. Two states give the widest possible gap, so the circuits are cheap, fast and robust against noise. Binary won not because the mathematics is elegant but because it is easy to build and hard to get wrong.

2.2.1 Is binary the right answer mathematically, too?#

Having just said “not because the mathematics is elegant”, we should weigh that phrase. ★ On mathematics alone, binary is not optimal. Ternary is.

The mathematics. Radix economy

Writing a number $𝑁$ in radix $𝑏$ needs ${log}_{𝑏} 𝑁$ digits. Each position has to distinguish $𝑏$ possibilities, so take the cost of a position to be proportional to $𝑏$ . The total cost is then

𝐸 (𝑏, 𝑁) = 𝑏 \cdot {log}_{𝑏} 𝑁 = \frac{𝑏}{ln 𝑏} \cdot ln 𝑁

and since $ln 𝑁$ does not depend on $𝑏$ , everything turns on $𝑏 / ln 𝑏$ . Differentiate it and the minimum is at $(ln 𝑏 - 1) / {(ln 𝑏)}^{2} = 0$ , that is at $ln 𝑏 = 1$ :

𝑏 = 𝑒 \approx 2.718

A radix must be a whole number, so compare the three nearest, with 10 alongside.

Radix $𝑏$	$𝑏 / ln 𝑏$
2	2.8854
3	2.7307 — the minimum
4	2.8854
10	4.3429

Table 2.1 — The representation efficiency of whole-number bases

★ Two things stand out. First, 2 and 4 are exactly equal — because $4 = 2^{2}$ , so $4 / ln 4 = 4 / (2 ln 2) = 2 / ln 2$ . Second, three beats two by a mere 5.7%.

Work it out and even that 5.7% does not always show. Digit counts round up, so for small numbers the result can flip.

Number to represent	Binary	Ternary	Winner
$10^{3}$	10 digits × 2 = 20	7 digits × 3 = 21	binary
$10^{6}$	20 digits × 2 = 40	13 digits × 3 = 39	ternary
$10^{9}$	30 digits × 2 = 60	19 digits × 3 = 57	ternary

Table 2.2 — For small values, base 2 sometimes wins

2.2.2 A ternary computer that was actually built — Setun#

This was not merely armchair reasoning. In 1958 a ternary computer called Setun was built at Moscow State University, and between 1959 and 1965 fifty machines were produced, thirty of them installed in universities and colleges.¹

In practice. Setun — the brief moment ternary won

Sergei Sobolev began the design in 1956 and Nikolay Brusentsov led it.

★ The heart of the matter is why ternary was favourable then. The machine built its logic not from transistors but from ferrite cores and diodes. A core has two directions of magnetisation, so “magnetised negative / not magnetised / magnetised positive” gives three states naturally. Ternary was not being imitated; the parts were simply shaped that way. The Russian Virtual Computer Museum’s record states the result plainly — compared with binary counterparts they gave “more speed and reliability, require less equipment and power”.

Numbers were held in balanced ternary: the digits are not 0, 1, 2 but –1, 0, +1. Six of them (trits) made one “tryte”, about 9.5 bits.

This computer disappeared for administrative reasons, not technical ones. Production stopped in 1965 despite unmet demand, and the museum’s record is dry about it — officials took a dim view of this “unplanned and unusual fruit of university fantasy”, and it was replaced by a binary machine of the same performance that was “more than 2.5 times more expensive”.

Balanced ternary is a lovely thing in its own right. The computer scientist Knuth called it “perhaps the prettiest number system of all”.² Several reasons for the prettiness:

There is no separate sign bit. The sign of the leading non-zero digit is the sign of the number.
Negation is flipping the sign of every digit. $13 = 111$ and $- 13 = TTT$ (where T is –1) — simpler than the “invert and add one” of chapter 6′s negative-number representation.
Rounding is truncation. Drop the tail and what remains is the nearest value.

2.2.3 So why did binary win?#

The mathematics points at three, a real machine was built, and the world is binary. The reason is that the cost model was wrong.

The calculation above assumed “the cost of a position is proportional to $𝑏$ ”. That models a device where each of the $𝑏$ states needs its own part — a $𝑏$ -way switch, say. A ferrite core was close to that. But what fixes the cost of a transistor circuit is not the part count; it is how surely voltage levels can be told apart.

Radix	Gap between adjacent levels	What it means
2	100% of the supply	switch fully on or fully off
3	50%	an intermediate level must be held precisely
4	33%
10	11%

Table 2.3 — Voltage levels crowd together as the radix grows

★ The gap shrinks as $1 / (𝑏 - 1)$ , and that gap is the noise margin. Binary runs transistors in saturation — fully on or fully off, hardly any time spent in between, with the whole supply voltage as margin. Ternary must hold a middle level in an analogue way, halving the margin, and manufacturing spread eats into that half.

So, summarised:

What you count	The answer
digits × radix (part count)	ternary — but only by 5.7%
noise margin, speed, manufacturing spread	★ binary — overwhelmingly

Table 2.4 — Which radix is ‘most efficient’ depends on what you count

And the 5.7% that ternary saves was not worth halving the noise margin. Count what came with binary as well — the mature theory of Boolean algebra, error-correcting codes, communication protocols, half a century of design assets — and the gap widens much further.

A common misconception. “Ternary is mathematically optimal, so one day computers will switch to it”

“Mathematically optimal” holds under one particular cost model, and that model does not fit today’s semiconductors. An optimisation problem changes its answer when the objective changes, and here it was the objective that was wrong.

★ The research is not dead, though. In devices whose threshold voltage can be set per device — carbon nanotube transistors (CNTFETs), for instance — ternary logic is being examined again, and in 2024 a device that switches reliably among three states was reported.³ What the researchers are after is not fewer digits but fewer wires and less power: sending more information down one wire reduces the costliest resource on a chip, its interconnect.

So the accurate statement is this — change the cost model and the answer can change. For today’s semiconductors (CMOS), binary is right; for a different device, the question must be asked again.

★ There is a reason for telling this at length. It is a pattern this book meets again and again — the answer a clean theory points at is not the answer you get when building the thing. Many of C’s decisions were made that way: there was a theoretically better option, and the machines of the day could not carry it, or the code already written would not allow it. Binary is that pattern’s oldest and most successful case.

One bit distinguishes two things. Bundle several bits and the number of distinguishable cases grows multiplicatively. Two bits give four (00, 01, 10, 11), three give eight. A bundle of eight has a name — the byte — and one byte distinguishes 256 cases.

Q. Why eight, of all bundle sizes? Was it eight from the start, and everywhere?

A. No — the size of a byte has never been fixed at 8 bits. Originally “byte” meant the bundle that holds one character, and its size differed from machine to machine. Early computers really did have 6-bit, 7-bit and 9-bit bytes, and some machines had 36-bit words that they cut into six 6-bit bytes. Eight became dominant when IBM’s mainframes of the 1960s (System/360) adopted it and the industry followed. That is why communication specifications, where precision is everything, still say octet (exactly 8 bits) instead of byte — a trace of the history in which the word “byte” alone guaranteed no size.

And this is not only an old story. Some signal-processing chips (DSPs) still have a smallest storage unit of 16 or 32 bits, so in the C running on them a byte is 16 or 32 bits. On the machines you are likely to meet, a byte is 8 bits in practice, but “a byte is always 8 bits” is custom, not promise.

The definition in the C standard (C23) is correspondingly careful. In C23 a byte is an “addressable unit of data storage large enough to hold any member of the basic character set of the execution environment” (§3.7), and the number of bits in it is published under the name CHAR_BIT — pinned down only as at least 8, not exactly 8. This book, following the common machines, will proceed with byte = 8 bits, but records here that this is the practice rather than the standard’s guarantee. (The committee is discussing fixing it at 8 outright in a future standard — half a century of custom being promoted to a promise.)

The mathematics. Bundle size and number of cases

The number of states a bundle of $𝑛$ bits can distinguish is, since each position independently takes two values,

2 \times 2 \times \dots \times 2 = 2^{𝑛}

So $2^{8} = 256$ , $2^{16} = 65536$ , $2^{32} \approx 4.3 \times 10^{9}$ . $2^{𝑛}$ keeps appearing in this book — the size of storage, the range of representable numbers and the count of addresses are all of this form.

Representing a number with a bundle works on the same principle as the decimal notation we use: positional notation. Just as the decimal number $304 = 3 \cdot 10^{2} + 0 \cdot 10^{1} + 4 \cdot 10^{0}$ , the binary number $101_{2} = 1 \cdot 2^{2} + 0 \cdot 2^{1} + 1 \cdot 2^{0} = 5$ . Each position simply carries a power of 2 instead of a power of 10.

Q. How do we handle large numbers with a byte that has only 256 possible values?

A. Just as in decimal you add digits when one is not enough, bytes are joined together to hold larger numbers. How many bytes it makes sense to join depends on the machine — and that “natural bundle” is the word, the subject of the next chapter.

2.3 C was born in the days of the simple three-part machine#

The three-part picture drawn so far is far too simple for today’s computers (that is the story of chapters 12–13). But for a computer of the early 1970s the picture was very nearly the literal truth. The clock ticked a few hundred thousand times a second, the CPU really did take one step per tick, and memory really was a row of lockers.

C was born in exactly those days, on exactly that simple machine — not out of nothing, though, but at the end of a short and distinct lineage. Knowing that lineage explains several features of C’s appearance at a stroke, so it is summarised here.

The starting point was an ambitious British language of the 1960s called CPL — so ambitious that machines of the day struggled to implement it, until Martin Richards at Cambridge distilled its essence into a small, practical language called BCPL (1967). BCPL’s radical simplicity was this: there is only one type. Every value is just one word-sized slot, and whether to use it as a number or as an address is decided by the operation. It pushed “what is in the slot is only bits, and interpretation decides” — the lesson of the next chapter — across the entire language.

At Bell Labs, Ken Thompson, building early Unix on an ageing PDP-7, made B (around 1969) by trimming BCPL further to his taste — still one type, and the source of terse idioms that survive today (++ among them). Then the labs brought in a new machine, the PDP-11, and B’s premise broke. The PDP-11 addressed memory in bytes rather than words (chapter 3′s corridor is exactly this shape), and data of different sizes — one-byte characters, two-byte integers, and floating point — had to be handled distinctly. A language in which “everything is one word” could not drive this machine properly.

So Dennis Ritchie brought types into B — distinguishing characters from integers, creating pointers that know what they point at, and adding structures. Those modifications accumulated between 1971 and 1973 and earned a new name: C. Put differently, C’s type system was not a philosophical design but a response to the reality of a byte-addressed machine. That C is byte-oriented to the bone (the byte of this chapter, the corridor of chapter 3), that pointers sit at the centre of the language, and that its type system is nonetheless loose (an inheritance from a one-type ancestor) — all are traces of that lineage.

Two footnotes. Idioms that look familiar today were not there from the start — today’s +=, for instance, was written =+ in early C and only took its current shape some years later (because of a confusion: was x=-1 a subtraction or an assignment?). Languages are refined by guarding against the wounds of real use. And in this era C had no standard and no specification document — the definition of the language was effectively “whatever Ritchie’s compiler accepts.” What commotion that looseness grew into, and how it summoned a standard (C89), is picked up in chapter 13.

So early C was a language that plainly showed the machines of its day. One C operation corresponded to one or two machine instructions, and a programmer writing C could see clearly what the machine was going to do. C’s reputation as “a language close to the machine” comes from here — and why that reputation is only half true today is shown in the later chapters of Part II (chapters 12–15).

In practice. The portability revolution — rewriting Unix in C

Around 1973 the heart of Unix was rewritten from assembly into C. It was radical at the time — the common sense being that an operating system had to be written at the machine-code level. The effect was overwhelming. Assembly Unix was tied to the PDP-11, but Unix written in C could be moved to another machine “as long as there is a C compiler.” An operating system had stopped being the property of a particular machine. Today the kernels of Linux, Windows and macOS are all written in C (or its descendants), and the tradition of porting a C compiler first to each new processor began here.

Q. Is it a disadvantage to learn, today, a language fitted to the machines of fifty years ago?

A. Quite the opposite. The skeleton of the machine — memory, addresses, bytes, the sequential execution of instructions — has not changed in fifty years, and C remains the thinnest wrapping around that skeleton. Learning C is therefore less about memorising one language’s grammar than about learning the computer itself. Whatever language you use afterwards, C is almost always underneath it.

To summarise this chapter’s picture: the machine repeatedly fetches an instruction from memory on the beat of the clock and executes it, and memory is made of bits, the two-state minimum unit. C was born when this picture was nearly the truth, and it is this picture put into a language.

The next chapter looks closely at memory, one of the three parts. We walk the locker corridor and read the number attached to each slot — the address — and measure the natural bundle the machine picks up at once — the word — and inspect the two orders in which a multi-byte number can be put into the lockers — endianness. C’s famous notion of the pointer was born in this corridor.

Notes

Development of ternary computers at Moscow State University. Russian Virtual Computer Museum. computer-museum.ru/english/setun.htm ↩
Donald E. Knuth. 1997. The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, Reading, MA. §4.1. ↩
A study in Science Advances. science.org/doi/10.1126/sciadv.adt1909 — a research result, not a product. ↩

← PrevContentsNext →