Bits, Bytes, and Words

At the lowest level a computer stores only bits, each a single device that is either on or off, charged or not, conducting or not. Everything else is interpretation. The same eight bits are an integer to one instruction, a character to another, and part of a machine instruction to a third; what they mean is decided entirely by the code that reads them. This first lesson fixes the vocabulary the rest of the course is written in: how bits are grouped, how we write them down, and the order bytes sit in memory.

Bits and the two notations

A single bit carries one of two values, written $0$ and $1$. Group $n$ bits and you can name $2^n$ distinct patterns, so the count of representable values doubles with every bit added. Eight bits, a byte, give $2^8=256$ patterns; thirty-two bits give about four billion; sixty-four give more than $10^{19}$.

We read a byte as a base-2 numeral: the rightmost bit carries weight $2^0=1$, the next $2^1=2$, and bit $i$ carries weight $2^i$. The value is the sum of the weights of the bits that are set.

Binary is hard for humans to read: a 32-bit value is thirty-two ones and zeros that no one can parse at a glance. To address this, we write values in hexadecimal: base 16, with digits 0–9 then a–f for ten through fifteen. Hex works because $16=2^4$: every group of four bits (a nibble) is exactly one hex digit, so a byte is always two hex digits and the translation is a lookup, not arithmetic.

By convention a hex literal is written with a 0x prefix (0x69), a binary one sometimes with 0b (0b01101001), and a plain numeral is decimal. The sixteen nibble patterns are worth memorizing once; they come up constantly when reading memory dumps.

Converting in either direction is now mechanical. To read 0x3b8 in binary, expand each digit: 3 is 0011, b is 1011, 8 is 1000, so 0x3b8 = 0011 1011 1000. Going the other way, group the bits into nibbles from the right (padding the top with zeros if the count is not a multiple of four) and look up each group. To go from hex to decimal, weight each digit by its power of sixteen: $0x3b8=3\cdot 16^2+11\cdot 16+8=768+176+8=952$. Small cases are worth doing by hand; anything larger belongs in a calculator. Hex exists to make the bits readable, not to ease decimal conversion.

A worked conversion ties the three notations together. The byte 0xB4 decodes as follows: split into nibbles b and 4, giving bits 1011 0100; sum the set positions $128+32+16+4=180$; and confirm against hex arithmetic $11\cdot 16+4=176+4=180$. All three agree, because they are three ways of writing the same eight-bit pattern.

Words, addresses, and the memory model

Programs see memory as one enormous array of bytes, virtual memory, and every byte has an integer address, its index into that array. The set of all possible addresses is the address space. A machine with 64-bit addresses can in principle name $2^{64}$ bytes; no machine has that much memory, but the address is that wide, and that width is what we mean when we call a processor

A multi-byte value occupies a run of consecutive addresses, and every object has a natural size. A char is one byte, so it sits at a single address; an int is four bytes and spans four consecutive addresses; a pointer on a 64-bit machine is eight bytes and spans eight. Placing three objects in memory shows how addresses grow with size.

The word size is the machine's natural unit of integer and address arithmetic: the width of its general-purpose registers and of a pointer. On a 64-bit machine the word is 8 bytes, and that single number determines how much memory a pointer can reach, how wide the adder in the datapath must be, and the default size of a C long. Data still comes in several widths, and it helps to keep the names straight.

The terminology has one historical inconsistency: in Intel's assembly a word is 16 bits, frozen at the size of the original 16-bit 8086, so a modern 64-bit value is a quad word. When this course says word without qualification it means the machine's natural width; when it means Intel's 16-bit unit it will say so.

The address space's width has a practical consequence worth making concrete with real numbers. A 32-bit machine has 32-bit addresses, so its address space is $2^{32}=4,294,967,296$ bytes, exactly 4 GiB. That is the ceiling on how much memory a single 32-bit process can name, and it is why 32-bit systems could never use more than 4 GiB per process no matter how much RAM the board held. A 64-bit machine lifts the ceiling to $2^{64}\approx 1.8\times 10^{19}$ bytes — 16 exbibytes, so far beyond any real memory that current x86-64 hardware only implements 48 of the 64 address bits, naming a still-enormous 256 TiB. The width of the address, not the amount of installed RAM, is what 64-bit measures.

The same bits, three meanings

For example, take the claim that a bit pattern means nothing until code reads it, applied to the single byte 0x41. Read as an unsigned integer it is $65$. Read as an ASCII character it is the capital letter A, because the ASCII table assigns code $65$ to A. Read as part of a machine instruction it might be an opcode byte, or the low byte of a larger immediate. Nothing about the byte itself picks among these; the choice is made entirely by the instruction that loads it.

The string "A" in C is therefore two bytes in memory: the code for A, 0x41, followed by a zero terminator 0x00. And the number $65$ stored in a char and the character 'A' are, at the level of bits, indistinguishable — C's char type is a small integer, and 'A' == 65 is true. This identity is why you can do arithmetic on letters: 'A' + 1 is 'B' because their ASCII codes are consecutive, and c - '0' converts a digit character to its numeric value by subtracting the code of '0' (which is $48$). The bits carry no type; the type lives in the program.

Byte ordering: the one real surprise

A byte has an address; a multi-byte value occupies several consecutive addresses. That raises a question with no logically forced answer: of the bytes making up a 4-byte integer, which one goes at the lowest address? Two camps settled it two opposite ways, and both are still in service.

• Big-endian stores the most significant byte first, at the lowest address, the order we write numbers in with the most significant digit leftmost. Used by classic network protocols and older RISC machines.
• Little-endian stores the least significant byte first. This is what x86-64 — and therefore almost every laptop and server — actually does.

Most of the time byte order is invisible: it cancels out as long as you only ever load a value the same width you stored it. It becomes visible the instant you cross that abstraction — casting a pointer to look at individual bytes, sending binary over a network, or reading a file written by a different machine. A short C routine makes the layout concrete by printing an object's bytes one at a time.

#include <stdio.h>

/* Print the `len` bytes starting at `start`, low address first. */
void show_bytes(unsigned char *start, size_t len) {
  for (size_t i = 0; i < len; i++)
    printf(" %.2x", start[i]);   /* two hex digits per byte */
  printf("\n");
}

int main(void) {
  int x = 0x01234567;
  show_bytes((unsigned char *) &x, sizeof(int));
  return 0;   /* x86-64 prints: 67 45 23 01 */
}

The cast (unsigned char *) &x tells the compiler to stop treating those four bytes as one int and hand back a pointer to the first byte, which we then walk one address at a time. On any little-endian x86-64 box the output is 67 45 23 01 — the value's least significant byte sitting at the lowest address, exactly as the figure predicts.

Down at the machine level the byte width is not a comment but part of the instruction itself. Each move carries a size suffix, and writing a single byte touches exactly one address while leaving its neighbors untouched. In the assembly below, $ marks a constant, %rdi a register, and (%rdi) the memory at that address, syntax made precise in the machine-level module.

movl    $0x01234567, %eax      # 32-bit value into the low 4 bytes of rax
movl    %eax, (%rdi)           # store all 4 bytes at address in rdi
movb    $0x67, (%rdi)          # overwrite just the byte at that address

Because x86-64 is little-endian, the movl lays 67 45 23 01 into memory from (%rdi) upward, and the following movb writes the same 0x67 the store had already placed at the lowest address, confirming that the size suffix and the byte order are consistent.

The endianness confusion is easiest to see when the same bytes cross a machine boundary. Suppose a big-endian server writes the 32-bit integer $1$ to a file: because it stores the most significant byte first, the four bytes on disk are 00 00 00 01. A little-endian laptop that reads those four bytes back into an int interprets the first byte, 00, as the least significant, and the last byte, 01, as the most significant — reconstructing the value $0x01000000=16,777,216$, not $1$. Nothing is corrupt; each machine followed its own rule faithfully. This is why binary network protocols declare a byte order (network byte order is big-endian) and why file formats either fix an endianness or store a marker so a reader can tell.

Bi-endianness and the units question

CS:APP presents big- and little-endian as two fixed camps, which is how the world looked when the two conventions were tied to processor families. Modern practice is more fluid in two ways worth knowing.

First, several major architectures are now bi-endian: the byte order is a runtime or boot-time choice rather than a property of the silicon. ARM (from the ARMv6 generation) and Power and MIPS all support both orders and let the operating system pick, which is how the same instruction set runs a little-endian phone and a big-endian embedded controller.¹ x86-64 remains resolutely little-endian, and because it dominates servers and desktops, most data you meet is little-endian in practice — but the code that parses a file format or a network packet cannot assume it, which is why portable code reaches for byte-swap intrinsics (bswap on x86, __builtin_bswap32 in GCC and Clang) or the classic htonl/ntohl network-order conversions instead of casting a pointer and hoping.

Second, the how big is a kilobyte ambiguity that has dogged the field was finally given a clean vocabulary. Memory sizes are powers of two, so $2^{10}=1024$ bytes was long called a kilobyte, clashing with the SI meaning of $1000$. Since 1998 the IEC standard reserves the binary prefixes kibi (Ki), mebi (Mi), gibi (Gi), and tebi (Ti) for the powers of $1024$, leaving kilo, mega, giga for exact powers of $1000$.² The distinction matters in practice: a 500 GB disk advertised in decimal gigabytes holds about $465$ GiB when the operating system counts in binary, and the roughly $7\%$ gap grows at each larger prefix. This course writes GiB and TiB when it means powers of two, as when a 64-bit process names $2^{64}$ bytes.

With the units in hand, the next lesson asks what those bit patterns mean as numbers — how a fixed-width byte string encodes both unsigned magnitudes and the negative integers, through two's complement.