When you write y = (a - b) / (c + d * e); in C, the processor never sees that line. The compiler turns it into a list of machine instructions, each a fixed pattern of bits stored in memory. The CPU then reads those bit patterns one by one and does what each one says.
Two questions sit at the heart of this process, and they are the subject of this chapter:
Instruction format: how is an instruction laid out in bits? Which bits say "add", and which bits say "add what"?
Instruction cycle: what steps does the CPU go through, over and over, to fetch an instruction and carry it out?
An instruction format is the layout of the bits of an instruction, dividing them into fields such as the operation code (opcode), addressing mode bits and operand (address or register) fields.
The instruction cycle is the sequence of steps the CPU performs for every instruction: fetch it from memory, decode it, obtain its operands, execute it, and (if enabled) check for interrupts, then repeat.
We will describe steps using the register transfer notation from Register Transfer & Micro-operations (for example IR ← M[AR]).
The Fields of an Instruction
Every instruction must tell the CPU two things: what to do and what to do it with. So an instruction is split into fields:
+----------+--------+-------------------+-------------------+
| Opcode | Mode | Operand field 1 | Operand field 2 | ...
+----------+--------+-------------------+-------------------+
Field | Purpose | Size rule |
|---|---|---|
Opcode (operation code) | Which operation: ADD, LOAD, JUMP, ... | To support N distinct operations you need at least ⌈log2N⌉ bits |
Mode (addressing mode) | How to interpret the operand field (a value, a register, a memory address, an address of an address, ...) | ⌈log2(number of modes)⌉ bits; sometimes just 1 bit (direct/indirect) |
Register field | Names a CPU register | With R registers: ⌈log2R⌉ bits |
Address field | A memory address (or part of one) | To reach 2m locations directly: m bits |
Immediate field | A constant value inside the instruction | k bits give 0 to 2k − 1 unsigned, or −2k−1 to 2k−1 − 1 signed |
The different ways of interpreting the operand field are the topic of the next chapter, Addressing Modes. Here we focus on how many fields there are and how big they are.
An Example Format
A classic teaching computer (from Morris Mano's textbook) uses 16-bit instructions and a 4096-word memory:
15 14 13 12 11 0
+----+-----------+--------------------------------------+
| I | Opcode | Address |
+----+-----------+--------------------------------------+
1 bit 3 bits 12 bits
I = 0 : direct (the address field is the operand's address)
I = 1 : indirect (the address field points to a word that holds the operand's address)
12 address bits reach 212 = 4096 words, and 3 opcode bits give 8 codes. That design uses opcode 111 as an escape code to define many more register-reference and I/O instructions that need no address, which is a simple form of the expanding opcode idea discussed later.
Classifying Instructions by Number of Addresses
A binary operation like X ← A op B naturally involves three things: two sources and a destination. Instruction sets differ in how many of these are written explicitly in the instruction. Fewer explicit addresses mean shorter instructions, but more instructions per program.
Three-Address Instructions
All three operands are explicit: ADD X, A, B means X ← A + B. Programs are short, but each instruction is long because it carries three addresses.
Two-Address Instructions
One operand is both a source and the destination: ADD R1, B means R1 ← R1 + B. The original value of R1 is overwritten, so we sometimes need an extra MOV to keep a copy. This is the most common style in commercial CISC processors such as x86.
One-Address Instructions
An implied register, the accumulator (AC), is always one source and the destination: ADD B means AC ← AC + M[B]. Only one address is written. Values move in and out of AC with LOAD and STORE.
Zero-Address Instructions
Operands are taken from a stack: ADD pops the top two values, adds them and pushes the result. Only PUSH X and POP X carry an address. The expression must be written in postfix (reverse Polish) notation. The Java Virtual Machine and Python's bytecode use this stack style.
These styles relate directly to how the CPU is organised (accumulator-based, general-register, or stack-based), covered in CPU Organization: Accumulator, General Register & Stack.
Worked Example: One Expression, Four Styles
Problem. Write programs to evaluate Y = (A − B) / (C + D × E) using three-, two-, one- and zero-address instructions. A to E and Y are memory locations; T, T1, T2 are temporary memory locations; R1, R2 are registers. For SUB and DIV, the order is "first − second" and "first / second".
Three-Address
SUB T1, A, B ; T1 ← A − B
MUL T2, D, E ; T2 ← D × E
ADD T2, C, T2 ; T2 ← C + T2
DIV Y, T1, T2 ; Y ← T1 / T2
4 instructions.
Two-Address
MOV R1, A ; R1 ← A
SUB R1, B ; R1 ← R1 − B
MOV R2, D ; R2 ← D
MUL R2, E ; R2 ← R2 × E
ADD R2, C ; R2 ← R2 + C
DIV R1, R2 ; R1 ← R1 / R2
MOV Y, R1 ; Y ← R1
7 instructions.
One-Address (Accumulator)
Compute the denominator first and park it in T, because the accumulator can hold only one value at a time:
LOAD D ; AC ← D
MUL E ; AC ← AC × E
ADD C ; AC ← AC + C
STORE T ; T ← AC (denominator saved)
LOAD A ; AC ← A
SUB B ; AC ← AC − B
DIV T ; AC ← AC / T
STORE Y ; Y ← AC
8 instructions.
Zero-Address (Stack)
The postfix form of (A − B) / (C + D × E) is A B − C D E × + /.
Instruction Stack after (top on the right)
PUSH A A
PUSH B A, B
SUB (A−B)
PUSH C (A−B), C
PUSH D (A−B), C, D
PUSH E (A−B), C, D, E
MUL (A−B), C, (D×E)
ADD (A−B), (C+D×E)
DIV (A−B)/(C+D×E)
POP Y (empty) Y ← result
10 instructions. For example, with A = 20, B = 8, C = 2, D = 2, E = 2 every program gives Y = 12 / 6 = 2. (All four programs were checked by simulating them on many random inputs.)
Count Is Not the Whole Story
Fewer instructions does not mean a smaller program, because each instruction is a different length. Assume an 8-bit opcode, 16-bit memory addresses and 3-bit register fields:
Style | Instructions | Bits per instruction | Total program bits |
|---|---|---|---|
Three-address (memory) | 4 | 8 + 3 × 16 = 56 | 224 |
Two-address (register + memory) | 7 | 27 (reg + mem), 14 (reg + reg) | 6 × 27 + 14 = 176 |
One-address | 8 | 8 + 16 = 24 | 192 |
Zero-address | 10 | 24 (PUSH/POP), 8 (operations) | 6 × 24 + 4 × 8 = 176 |
Style | Advantage | Disadvantage |
|---|---|---|
Three-address | Shortest programs, no need to destroy operands | Long instructions (if operands are memory addresses) |
Two-address | Good balance; common in CISC | One source is overwritten |
One-address | Short instructions, simple hardware | Many LOAD/STORE instructions; accumulator is a bottleneck |
Zero-address | Shortest arithmetic instructions; easy code generation from postfix | Most instructions; every operand passes through the stack |
Note that load-store RISC machines (see Instruction Set Architecture: RISC vs CISC) use three-address instructions where all three operands are registers. Register fields are only 5 bits each, so three of them fit comfortably in a 32-bit instruction.
Fixed-Length vs Variable-Length Instructions
Aspect | Fixed length | Variable length |
|---|---|---|
Example | RISC-V, ARM A64, MIPS: every instruction is 32 bits | x86: 1 to 15 bytes per instruction |
Decoding | Easy and fast; the next instruction's location is known (PC + 4) | Harder: must decode part of an instruction to know where the next one starts |
Code density | Wastes bits on simple instructions | Compact: common instructions can be short |
Pipelining | Easy | Harder |
Many fixed-length designs add a compressed option to recover density: RISC-V's "C" extension and ARM's Thumb provide 16-bit forms of common instructions.
Worked Problems on Instruction Formats
Problem 1: Size of an Immediate Field
A processor has 50 distinct instructions and 32 general-purpose registers. Each instruction is 32 bits and contains an opcode, two register fields and an immediate field. How large is the immediate field, and what range can it hold?
Opcode: ⌈log250⌉ = 6 bits (25 = 32 is too few, 26 = 64 is enough).
Each register field: log232 = 5 bits, two of them = 10 bits.
Immediate: 32 − 6 − 10 = 16 bits.
Range: unsigned 0 to 65,535; signed (2's complement) −32,768 to 32,767.
Problem 2: How Many Operations?
A word-addressable computer has 64 K words of memory and a 24-bit instruction word. A one-address instruction has an indirect bit, an opcode and a direct address field. How many operations can it have?
64 K = 216 words, so the address field is 16 bits.
Opcode = 24 − 1 − 16 = 7 bits, giving 27 = 128 operations.
Problem 3: Expanding Opcodes
When instructions with fewer operands are needed, their unused operand bits can be reused as extra opcode bits. This is called an expanding opcode. The trick is to reserve some codes of the short opcode as "escape" prefixes.
A machine has 16-bit instructions and 6-bit address fields. Two-address instructions use a 4-bit opcode (4 + 6 + 6 = 16). There are 12 two-address instructions.
Maximum one-address instructions? Of the 16 four-bit opcodes, 12 are used, so 4 are free to act as prefixes. Each prefix leaves 6 bits (the old first address field) for further opcode bits: 4 × 26 = 256 one-address instructions.
If only 200 one-address instructions are used, how many zero-address instructions are possible? 256 − 200 = 56 unused one-address codes, each freeing another 6 bits: 56 × 26 = 3584.
Format Count Bit patterns used
[op:4][addr1:6][addr2:6] 12 12 × 2^12 = 49,152
[prefix:4][op:6][addr:6] 200 200 × 2^6 = 12,800
[........ op:16 .........] 3584 3584 × 1 = 3,584
total = 65,536 = 2^16 ✓
A quick check: the patterns used by all formats must add up to at most 216, and here they use exactly all of them.
Problem 4: Expanding Opcodes with Mixed Register Files
A processor has 16 integer registers and 32 floating-point (FP) registers and uses 16-bit instructions. It needs: Type 1, 5 instructions with three integer register operands; Type 2, 20 instructions with two FP register operands; Type 3, 30 instructions with one integer and one FP register; Type 4, N instructions with one FP register. Find the maximum N.
An integer register field is 4 bits; an FP register field is 5 bits. Count how many of the 216 = 65,536 bit patterns each type consumes:
Type 1: operands use 3 × 4 = 12 bits, so each instruction uses 212 patterns: 5 × 4096 = 20,480.
Type 2: 2 × 5 = 10 bits: 20 × 1024 = 20,480.
Type 3: 4 + 5 = 9 bits: 30 × 512 = 15,360.
Used so far: 56,320. Remaining: 65,536 − 56,320 = 9,216.
Type 4 uses 25 = 32 patterns each: N = 9,216 / 32 = 288.
This "count the bit patterns" method works for any expanding-opcode question and avoids drawing the encoding tree.
The Instruction Cycle
Once a program is in memory and the PC holds the address of its first instruction, the CPU repeats the same cycle until it is halted:
+------------------+
+---->| FETCH | IR ← M[PC], PC ← next instruction address
| +--------+---------+
| v
| +------------------+
| | DECODE | decode opcode, identify mode and operands
| +--------+---------+
| v
| +------------------+
| | OPERAND FETCH | compute effective address, read operand(s)
| +--------+---------+
| v
| +------------------+
| | EXECUTE | ALU operation / branch / store result
| +--------+---------+
| v
| interrupt pending and enabled?
| no | | yes
+-------------+ v
| +------------------+
+------| INTERRUPT CYCLE | save PC, jump to interrupt service routine
+------------------+
Some textbooks split this into more steps: instruction address calculation, instruction fetch, decode, operand address calculation, operand fetch, data operation, operand store. The ideas are the same.
1. Fetch
The CPU reads the instruction at the address in PC into the instruction register, and advances PC:
T0: AR ← PC
T1: IR ← M[AR], PC ← PC + 1
Why two steps? Memory takes its address from AR, so PC must first be copied into AR. Incrementing PC in T1, at the same time as the memory read, saves a clock cycle.
The "+1" assumes each instruction is one word and memory is word-addressable. On a byte-addressable machine with 4-byte instructions (like RISC-V or ARM), it is PC ← PC + 4. On x86, the increment depends on the length of the instruction just fetched.
2. Decode
The control unit examines the opcode bits of IR to decide which operation to perform, and which addressing mode applies. In the 16-bit example format above:
T2: D0..D7 ← Decode IR(12-14), AR ← IR(0-11), I ← IR(15)
A 3 × 8 decoder turns the opcode into eight lines D0 to D7, exactly one of which is 1. The address part goes into AR, ready for the next step.
3. Operand Fetch (Effective Address)
The address actually used to reach the operand is the effective address (EA). For a direct address, EA is the address field itself. For an indirect address, one more memory read is needed to get it:
T3: if I = 1: AR ← M[AR] (indirect: read the real address)
if I = 0: nothing (direct: AR already holds EA)
Then the operand itself is read, for example DR ← M[AR].
4. Execute
The ALU performs the operation, or the PC is changed for a branch, or a result is written to memory. For an ADD to the accumulator:
T4: DR ← M[AR]
T5: AC ← AC + DR, SC ← 0 (SC = sequence counter, restarts the cycle at T0)
How the control unit generates these timing signals T0, T1, ... is the subject of Hardwired Control Unit and Microprogrammed Control Unit.
5. Interrupt Check
At the end of each instruction (never in the middle), the CPU checks whether an interrupt is pending and interrupts are enabled. If so, it enters the interrupt cycle:
Save the return address: M[SP] ← PC (or a fixed memory location)
Go to the service routine: PC ← address of interrupt service routine
Prevent nested interrupts: IEN ← 0
The next fetch then comes from the interrupt service routine. When it finishes, a return instruction restores the saved PC and the interrupted program continues as if nothing happened. Why check only between instructions? Because then the CPU state is clean and well-defined: the previous instruction is complete and the next has not started. The details of interrupts are covered in Programmed I/O & Interrupts.
Counting Memory References
A very common exam question asks how many memory accesses an instruction needs. Add them up stage by stage:
Stage | Memory accesses |
|---|---|
Instruction fetch | 1 per instruction word (2 for a two-word instruction) |
Indirect address | 1 extra per level of indirection |
Operand fetch | 1 per memory source operand |
Result store | 1 if the destination is in memory |
Worked Example
Problem. For each instruction, count memory references (instruction fetch included). Instructions are one word unless stated.
ADD R1, R2(registers only): fetch 1 = 1.LOAD R1, X(direct): fetch 1 + operand 1 = 2.ADD R1, @X(memory indirect): fetch 1 + indirect 1 + operand 1 = 3.ADD X, Y(X ← X + Y, both memory, two-word instruction): fetch 2 + read X 1 + read Y 1 + write X 1 = 5.
Worked Example: Instruction Time
Problem. A memory access takes 40 ns, decoding takes 5 ns and an ALU operation takes 15 ns. Ignoring other overheads, how long does ADD R1, @X (memory indirect) take?
Solution. Fetch 40 + decode 5 + indirect address 40 + operand 40 + execute 15 = 140 ns. The same ADD with a register operand would take 40 + 5 + 15 = 60 ns. Memory accesses dominate, which is why register operands and caches matter so much.
Common Mistakes
Using log2N without the ceiling. 50 opcodes need 6 bits, not 5.64 or 5.
Forgetting the mode / indirect bit when computing how many bits remain for the address or opcode.
Always writing PC ← PC + 1. On byte-addressable machines with 4-byte instructions it is PC + 4.
Forgetting the instruction fetch when counting memory references, or counting only one fetch for a two-word instruction.
Mixing up operand order in stack code. For SUB and DIV, the element below the top is the left operand: PUSH A, PUSH B, SUB gives A − B.
Thinking interrupts are serviced mid-instruction. In the basic instruction cycle they are checked only after the current instruction completes.
Assuming fewer instructions means smaller code. Three-address instructions are fewer but longer.
GATE and Interview Questions
A machine has 64 registers, supports 45 instructions, and uses 32-bit instructions with two register operands and an unsigned immediate. What is the largest immediate value?
Opcode ⌈log245⌉ = 6 bits, registers 6 + 6 = 12 bits, immediate 32 − 18 = 14 bits. Maximum = 214 − 1 = 16,383.
Write zero-address code for X = A × (B + C).
Postfix: A B C + ×. Code: PUSH A, PUSH B, PUSH C, ADD, MUL, POP X (6 instructions).
A 12-bit instruction set has 4-bit address fields. If there are 14 two-address instructions, what is the maximum number of one-address instructions?
Two-address format: 4-bit opcode + 4 + 4. 16 − 14 = 2 free opcodes, each followed by 4 extra opcode bits: 2 × 24 = 32 one-address instructions.
Why is the PC incremented during the fetch phase rather than after execution?
So the increment overlaps with the memory read and costs no extra cycle, and so that PC already points to the next instruction during execution. A branch simply overwrites PC with the target. (In many textbook machines, PC-relative addresses are also computed from this updated PC.)
What is the effective address?
The actual memory address from which the operand is read (or to which the result is written), after applying the addressing mode to the address field. For direct mode it is the address field; for indirect mode it is the word stored at that address.
Why does a CPU check for interrupts only at the end of an instruction cycle?
At that point the previous instruction has fully completed and no partial state exists, so saving just the PC (and status) is enough to resume correctly later.
How many memory references does a two-word instruction "ADD @X" (memory indirect, result in accumulator) need?
Fetch 2 (two words) + indirect 1 + operand 1 = 4.
Summary
An instruction is divided into fields: opcode (⌈log2N⌉ bits for N operations), mode, register (⌈log2R⌉ bits), address and immediate fields.
Three-, two-, one- and zero-address instructions trade instruction length against instruction count. The same expression took 4, 7, 8 and 10 instructions.
Fixed-length formats are easy to decode and pipeline; variable-length formats give denser code.
Expanding opcodes reuse unused operand bits as extra opcode bits; count bit patterns to solve such problems.
The instruction cycle: fetch (AR ← PC; IR ← M[AR], PC ← PC + 1), decode, operand fetch (compute EA, possibly via indirect), execute, then interrupt check.
Count memory references stage by stage: instruction words + indirections + memory operands + memory result.
Fetch, decode, execute, repeat: billions of times a second, every program you have ever run is this one loop.