--- title: Bits, Bytes, and Words module: Foundations moduleNumber: 0 lessonNumber: 1 order: 1 summary: > Everything a machine stores is a string of bits grouped into bytes. We set out binary and hexadecimal, the byte as the unit of addressing, the word as the machine's natural integer size, and byte ordering — why the same four bytes read as 0x01234567 on one machine and 0x67452301 on another. topics: [Foundations] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §2.1 Information Storage" - book: Bistriceanu ref: "Computer Architecture Notes — §2 Basic Organization of a Computer" --- 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. $$ % caption: A byte is eight bits. Bit i carries weight 2^i, so reading % caption: right-to-left the pattern 0110 1001 sums to 105, written 0x69 in hex. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\w in {0/128, 1/64, 2/32, 3/16, 4/8, 5/4, 6/2, 7/1} \node at (\i,0.95) {\w}; \foreach \i in {0,3,5,6} \node[bit] at (\i,0) {0}; \foreach \i in {1,2,4,7} \node[bit, draw=acc, thick, text=acc] at (\i,0) {1}; \node[anchor=west] at (8.4,0) {$=\ 64+32+8+1\ =\ 105\ =\ \mathtt{0x69}$}; \end{tikzpicture} $$ 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. $$ % caption: Four bits make a nibble, and a nibble is exactly one hex digit. Two % caption: nibbles pack into a byte, so any byte is precisely two hex digits. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\v in {0/0, 1/1, 2/1, 3/0} \node[bit] at (\i*0.8,0) {\v}; \foreach \i/\v in {0/1, 1/0, 2/0, 3/1} \node[bit] at (\i*0.8+3.8,0) {\v}; \node at (1.2,-0.9) {high nibble}; \node at (5.0,-0.9) {low nibble}; \node[text=acc] at (1.2,0.9) {$\mathtt{6}$}; \node[text=acc] at (5.0,0.9) {$\mathtt{9}$}; \node[anchor=west] at (7.0,0) {=> $\mathtt{0x69}$}; \end{tikzpicture} $$ 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. | Hex | Bits | Dec | Hex | Bits | Dec | | --- | --- | --- | --- | --- | --- | | `0` | `0000` | 0 | `8` | `1000` | 8 | | `1` | `0001` | 1 | `9` | `1001` | 9 | | `2` | `0010` | 2 | `a` | `1010` | 10 | | `3` | `0011` | 3 | `b` | `1011` | 11 | | `4` | `0100` | 4 | `c` | `1100` | 12 | | `5` | `0101` | 5 | `d` | `1101` | 13 | | `6` | `0110` | 6 | `e` | `1110` | 14 | | `7` | `0111` | 7 | `f` | `1111` | 15 | 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: $\mathtt{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. > **Definition (Byte).** The smallest block of memory a machine gives its own > address. A byte is eight bits and so holds one of $256$ values, written as two > hexadecimal digits, `0x00` through `0xff`. 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. $$ % caption: The byte 0xB4 in all three notations. The high nibble 1011 is hex b, % caption: the low nibble 0100 is hex 4; the set bits at weights 128, 32, 16, 4 % caption: sum to decimal 180. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\w in {0/128, 1/64, 2/32, 3/16, 4/8, 5/4, 6/2, 7/1} \node[black] at (\i,0.95) {\w}; \foreach \i in {1,4,5} \node[bit] at (\i,0) {0}; \foreach \i in {0,2,3,6} \node[bit, draw=acc, thick, text=acc] at (\i,0) {1}; \node[bit] at (7,0) {0}; \draw[acc] (-0.45,-0.5) rectangle (3.45,-1.0); \node[text=acc] at (1.5,-0.75) {high nibble b}; \draw[acc] (3.55,-0.5) rectangle (7.45,-1.0); \node[text=acc] at (5.5,-0.75) {low nibble 4}; \node[anchor=west] at (8.4,0) {$=\ 128+32+16+4\ =\ 180\ =\ \mathtt{0xB4}$}; \end{tikzpicture} $$ ## 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 "64-bit." 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. $$ % caption: Memory as a byte array. A char occupies one address, an int four % caption: consecutive addresses, and a pointer eight. Each object's address is % caption: the lowest byte it occupies; the next object starts where the last ended. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, minimum width=8mm, minimum height=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\a in {0/{0x100}, 1/{0x101}, 2/{0x102}, 3/{0x103}, 4/{0x104}, 5/{0x105}, 6/{0x106}, 7/{0x107}, 8/{0x108}, 9/{0x109}, 10/{0x10a}, 11/{0x10b}, 12/{0x10c}} \node[black, rotate=90, anchor=west, font=\scriptsize] at (\i*0.85,0.55) {$\mathtt{\a}$}; \node[by, fill=acc!8] at (0,0) {}; \foreach \i in {1,2,3,4} \node[by] at (\i*0.85,0) {}; \foreach \i in {5,6,7,8,9,10,11,12} \node[by, fill=acc!18] at (\i*0.85,0) {}; \draw[black] (-0.4,-0.55) -- (0.4,-0.55) (-0.4,-0.5) -- (-0.4,-0.6) (0.4,-0.5) -- (0.4,-0.6); \node[anchor=north, font=\scriptsize] at (0,-0.7) {char c}; \draw[black] (0.45,-0.55) -- (3.85,-0.55) (0.45,-0.5) -- (0.45,-0.6) (3.85,-0.5) -- (3.85,-0.6); \node[anchor=north, font=\scriptsize] at (2.15,-0.7) {int n (4 bytes)}; \draw[black] (3.9,-0.55) -- (10.65,-0.55) (3.9,-0.5) -- (3.9,-0.6) (10.65,-0.5) -- (10.65,-0.6); \node[anchor=north, font=\scriptsize] at (7.25,-0.7) {pointer p (8 bytes)}; \end{tikzpicture} $$ 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. | Width | Bytes | C type (x86-64) | Assembly suffix | | --- | --- | --- | --- | | Byte | 1 | `char` | `b` | | Word | 2 | `short` | `w` | | Double word | 4 | `int` | `l` | | Quad word | 8 | `long`, pointer | `q` | 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. $$ % caption: One byte, 0x41 = 0100 0001, read three ways. The unsigned rule sums the % caption: weights to 65; the ASCII rule maps 65 to the letter A; an instruction % caption: decoder reads the same bits as an opcode or immediate byte. \begin{tikzpicture}[font=\footnotesize, >=stealth, bit/.style={draw, minimum size=7mm, inner sep=0pt}, meaning/.style={draw, minimum width=30mm, minimum height=8mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\v in {0/0,1/1,2/0,3/0,4/0,5/0,6/0,7/1} \node[bit] at (\i*0.7,2.4) {\v}; \node[anchor=west] at (5.2,2.4) {$=\ \mathtt{0x41}$}; \node[meaning, fill=acc!8] (u) at (-0.6,0.7) {as unsigned int:\\65}; \node[meaning, fill=acc!8] (c) at (3.4,0.7) {as ASCII char:\\`A'}; \node[meaning, fill=acc!8] (i) at (7.4,0.7) {as instruction byte:\\opcode / immediate}; \draw[->, black] (2.1,2.1) -- (u.north); \draw[->, black] (2.1,2.1) -- (c.north); \draw[->, black] (2.1,2.1) -- (i.north); \end{tikzpicture} $$ 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. $$ % caption: The 4-byte value 0x01234567 laid out from address 0x100. Big-endian % caption: puts the most significant byte (01) at the lowest address; little-endian % caption: puts the least significant byte (67) first, which is x86-64's order. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, minimum width=11mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\a in {0/{0x100}, 1/{0x101}, 2/{0x102}, 3/{0x103}} \node at (\i*1.4,1.55) {$\mathtt{\a}$}; \node[anchor=east] at (-1.05,0.8) {big-endian}; \foreach \i/\v in {0/01, 1/23, 2/45, 3/67} \node[by] at (\i*1.4,0.8) {$\mathtt{\v}$}; \node[anchor=east] at (-1.05,-0.4) {little-endian}; \foreach \i/\v in {0/67, 1/45, 2/23, 3/01} \node[by] at (\i*1.4,-0.4) {$\mathtt{\v}$}; \node[text=acc, anchor=west] at (4.7,0.8) {$\gets$ MSB f\/irst}; \node[text=acc, anchor=west] at (4.7,-0.4) {$\gets$ LSB f\/irst}; \end{tikzpicture} $$ 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. ```c [show_bytes.c] #include /* 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](/computer-architecture/machine-level-x86-64/the-machines-view). ```asm [store.s] 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 $\mathtt{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. $$ % caption: The integer 1 written big-endian (00 00 00 01) and read back on a % caption: little-endian machine. The reader assigns the first byte the lowest % caption: weight, so the same four bytes decode to 0x01000000 = 16777216. \begin{tikzpicture}[font=\footnotesize, >=stealth, by/.style={draw, minimum width=11mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.4,1.3) {on disk}; \foreach \i/\v in {0/00, 1/00, 2/00, 3/01} \node[by] at (\i*1.4,1.3) {$\mathtt{\v}$}; \node[anchor=west, black] at (5.7,1.3) {written big-endian as int 1}; \foreach \i in {0,1,2,3} \draw[->, acc] (\i*1.4,0.9) -- (\i*1.4,0.15); \node[anchor=east] at (-0.4,-0.25) {read LE}; \foreach \i/\v/\w in {0/00/{$2^0$}, 1/00/{$2^8$}, 2/00/{$2^{16}$}, 3/01/{$2^{24}$}} \node[by, fill=acc!8] at (\i*1.4,-0.25) {$\mathtt{\v}$}; \foreach \i/\w in {0/{low byte}, 3/{high byte}} \node[text=acc, font=\scriptsize, anchor=north] at (\i*1.4,-0.65) {\w}; \node[anchor=west, text=acc] at (5.7,-0.25) {decodes to $\mathtt{0x01000000} = 16{,}777{,}216$}; \end{tikzpicture} $$ ## 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.[^biendian] 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$.[^iec] 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. > **Takeaway.** A bit is a choice between two values; a byte is eight of them and > the unit of addressing; a word is the machine's natural integer width. Hex is > binary you can read. And a multi-byte value has an _order_ in memory — most > machines you touch are little-endian, and that only matters when you look at the > bytes directly. 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](/computer-architecture/foundations/integer-representation). [^biendian]: The bi-endian support in ARM, Power, and MIPS is documented in each architecture's reference manual; the choice is exposed to system software as a mode bit rather than fixed in the instruction encoding. Cocke and Markstein's history of the RISC line (IBM J. Res. Dev., 2000) traces why the flexibility mattered as one instruction set spread across product families with different legacy byte orders. [^iec]: **IEC 60027-2** (1998, revised in **IEC 80000-13**, 2008) defines the binary prefixes kibi, mebi, gibi, and tebi for powers of $1024$, reserving the SI prefixes for powers of $1000$; the standard was adopted to end the long-standing 1000-versus-1024 conflation in memory and storage sizes.