ALU — Arithmetic Logic Unit

The ALU (Arithmetic Logic Unit) is the circuit that performs all computation in the CPU. Every ADD, SUB, AND, OR, NOT, compare, shift — everything — is done by the ALU. It is combinational logic (no memory) — output is the result of the current operation.

ALU Inputs:
- A — first operand (from register file)
- B — second operand (from register file or immediate value)
- Operation code (ALU_op) — a few bits that select which operation to perform

ALU Outputs:
- Result — the computed value (goes back to register file or memory)
- Status flags — bits that record properties of the result:
  - Z (Zero flag): Result == 0
  - N (Negative flag): Result < 0 (MSB is 1 in two's complement)
  - C (Carry flag): Unsigned overflow occurred
  - V (Overflow flag): Signed overflow occurred
  - These flags drive conditional branches (JZ, JNZ, JGT, JLT...)

Two's Complement — how CPUs represent signed integers:
- N-bit two's complement represents values from -2^(N-1) to 2^(N-1)-1
- Positive numbers: same as unsigned (MSB=0)
- Negative numbers: flip all bits + 1
- -1 in 8-bit: 11111111 (flip 00000001 → 11111110, add 1 → 11111111)
- -128 in 8-bit: 10000000
- The magic: addition and subtraction work the same circuit! A-B = A + (-B) = A + (~B + 1)
- Overflow detection: carry into MSB ≠ carry out of MSB

Shifter — fast multiplication/division by powers of 2:
- Logical shift left (LSL): shift bits left, fill with 0. LSL by 1 = multiply by 2
- Logical shift right (LSR): shift bits right, fill with 0. LSR by 1 = divide by 2 (unsigned)
- Arithmetic shift right (ASR): shift right, fill with sign bit. Preserves sign for signed division

Barrel shifter: shifts by N positions in ONE clock cycle (not N separate shifts). Uses MUXes to select the correct shifted version.

Multiplication: NOT done by the adder directly. Repeated addition is too slow. CPUs use Booth's algorithm (reduces partial products) or Wallace tree (parallel compression of partial products). Result is 2N bits for N×N multiplication (important for overflow).

Division: even harder. Done by long division algorithm in hardware (many cycles) or by multiply-by-reciprocal approximation. Division is ~20-40× slower than addition on modern CPUs — avoid in hot loops.

1# Build a complete 8-bit ALU from scratch
2
3class ALU:
4    # Operation codes
5    ADD  = 0b000
6    SUB  = 0b001
7    AND  = 0b010
8    OR   = 0b011
9    XOR  = 0b100
10    NOT  = 0b101
11    SHL  = 0b110   # shift left
12    SHR  = 0b111   # shift right
13
14    def __init__(self, width=8):
15        self.width = width
16        self.mask  = (1 << width) - 1
17        self.sign_bit = 1 << (width - 1)
18
19    def to_signed(self, val):
20        val &= self.mask
21        if val & self.sign_bit:
22            return val - (1 << self.width)
23        return val
24
25    def compute(self, A, B, op):
26        A &= self.mask
27        B &= self.mask
28        carry = overflow = False
29
30        if op == self.ADD:
31            raw = A + B
32            result = raw & self.mask
33            carry    = raw > self.mask
34            overflow = ((A ^ result) & (B ^ result) & self.sign_bit) != 0
35
36        elif op == self.SUB:
37            # A - B = A + (~B + 1) in two's complement
38            neg_B = ((~B) + 1) & self.mask
39            raw = A + neg_B
40            result = raw & self.mask
41            carry    = raw > self.mask
42            overflow = ((A ^ B) & (A ^ result) & self.sign_bit) != 0
43
44        elif op == self.AND: result = A & B
45        elif op == self.OR:  result = A | B
46        elif op == self.XOR: result = A ^ B
47        elif op == self.NOT: result = (~A) & self.mask
48        elif op == self.SHL: result = (A << (B & 7)) & self.mask
49        elif op == self.SHR: result = (A >> (B & 7)) & self.mask
50        else: raise ValueError(f"Unknown op: {op}")
51
52        # Compute flags
53        Z = result == 0
54        N = bool(result & self.sign_bit)
55        C = carry
56        V = overflow
57
58        return result, {"Z": int(Z), "N": int(N), "C": int(C), "V": int(V)}
59
60alu = ALU(width=8)
61
62print("8-bit ALU Operations:")
63print(f"{'Op':<6} {'A':>4} {'B':>4} {'Result':>8} {'Binary':>10}  Flags")
64print("─" * 60)
65
66tests = [
67    ("ADD",  10,  20, ALU.ADD),
68    ("ADD",  200, 100, ALU.ADD),   # unsigned overflow
69    ("ADD",  127, 1,   ALU.ADD),   # signed overflow
70    ("SUB",  20,  10,  ALU.SUB),
71    ("SUB",  5,   10,  ALU.SUB),   # negative result
72    ("AND",  0b11001010, 0b11110000, ALU.AND),
73    ("OR",   0b11001010, 0b00110011, ALU.OR),
74    ("XOR",  0b11001010, 0b11110000, ALU.XOR),
75    ("SHL",  0b00000001, 3,          ALU.SHL),   # 1 << 3 = 8
76    ("SHR",  0b10000000, 3,          ALU.SHR),   # 128 >> 3 = 16
77]
78
79for op_name, A, B, op in tests:
80    result, flags = alu.compute(A, B, op)
81    signed_r = alu.to_signed(result)
82    flag_str = " ".join(f"{k}={v}" for k, v in flags.items() if v)
83    print(f"{op_name:<6} {A:>4} {B:>4} {signed_r:>8}  {result:08b}  {flag_str}")