Lesson 1: From Logic Gates to the ALU

Introduction: from grains of silicon to a digital brain

Why is it that a computer — a machine able to simulate quantum physics, render gorgeous 3D graphics and run enormous AI models — fundamentally understands only two states: on (1) and off (0)? Every programmer knows this, but very few can actually picture how those crude on-off currents manage to add two numbers, compare them, or decide which way a branch should go.

This lesson takes you down to the deepest layer of computer hardware: from the foundations of Boolean algebra, through wiring AND/OR/XOR gates into a half adder (Half Adder) and a full adder (Full Adder), and on to building a complete 4-bit ALU . Finally you will drive an interactive ALU simulator yourself and watch how a CPU computes and sets the Zero, Sign and Overflow.

1. Boolean algebra & the basic logic gates

In the middle of the 19th century the mathematician George Boole invented an algebra in which variables take only two values: True (represented by 1) and False (represented by 0). That is the theoretical foundation of every binary computer today. As current passes through transistors, they act as extremely fast switches that carry out exactly these basic logic operations.

Four basic logic gates build up the entire machine:

• The NOT gate (inversion): The output is always the opposite of the input. If \(A = 1\) then \(Y = \neg A = 0\).
• The AND gate: The output is 1 only when every input is 1. Formula: \(Y = A \land B\).
• The OR gate: The output is 1 when at least one input is 1. Formula: \(Y = A \lor B\).
• The XOR gate (exclusive or): The output is 1 when the two inputs differ. Formula: \(Y = A \oplus B = (A \land \neg B) \lor (\neg A \land B)\).

The C below shows bitwise operators doing logic at bit level, and how a bit mask lets you read or toggle one specific bit:

#include <stdio.h>

int main() {
    unsigned char a = 5;  // binary: 0000 0101
    unsigned char b = 3;  // binary: 0000 0011
    
    // 1. Bitwise AND
    printf("a & b (bitwise AND)  = %d\n", a & b);   // result: 1 (0000 0001)
    
    // 2. Logical AND
    printf("a && b (logical AND) = %d\n", a && b);  // result: 1 (true && true)
    
    // 3. Use a bit mask to test bit 2 (counting from 0)
    unsigned char mask = 0x04; // binary: 0000 0100
    if ((a & mask) != 0) {
        printf("Bit index 2 of A is set (1)\n");
    }
    
    // 4. XOR is how you toggle a bit
    a = a ^ mask; // toggle bit index 2 of a (becomes 0000 0001)
    printf("A after toggling bit 2: %d\n", a); // result: 1
    
    return 0;
}

2. Half adders & full adders

Given the basic logic gates, how do we perform arithmetic — adding two binary numbers? The answer lies in combining those gates cleverly to build adder circuits in hardware.

The half adder

A half adder takes 2 bits \(A\) and \(B\) and produces 2 outputs: the sum bit \(Sum\) (\(S\)) and the carry bit \(Carry-out\) (\(C\)). Reading the binary truth table: \(Sum\) is 1 only when exactly one of the two bits is 1 — that is precisely XOR: \(S = A \oplus B\). \(Carry-out\) is 1 only when both bits are 1 — that is precisely AND: \(C = A \land B\).

It is called "half" because it has no input for a carry coming in from the previous column.

module half_adder (
    input a,
    input b,
    output sum,
    output carry
);
    assign sum = a ^ b;      // XOR gate
    assign carry = a & b;    // AND gate
endmodule

The full adder

To add numbers of more than one bit, the adder must handle the carry coming in from the previous column. That is why the full adder exists. It takes 3 inputs: \(A\), \(B\), and the incoming carry \(C_{in}\). Its logic works out as: \[S = A \oplus B \oplus C_{in}\] \[C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))\]

module full_adder (
    input a,
    input b,
    input cin,
    output sum,
    output cout
);
    wire s1, c1, c2;
    
    // Two half adders chained together make one full adder
    assign s1 = a ^ b;
    assign c1 = a & b;
    
    assign sum = s1 ^ cin;
    assign c2 = s1 & cin;
    
    // Combine the two sources that can produce a carry-out
    assign cout = c1 | c2;
endmodule

A quick comparison of the two adders we just built:

3. Designing a 4-bit ALU and its status flags

The arithmetic logic unit (ALU) is the computing heart of a CPU. A simple ALU can be built by placing the functional blocks side by side (the adder, an AND block, an OR block, an XOR block) and using a multiplexer (MUX) to decide which operation's result leaves the unit, based on the operation code (opcode).

To let the CPU make branching decisions (an if (a < b)statement, say), the ALU produces status flags from the result it has just computed:

• The Zero flag (Z): 1 when every bit of the result is 0. For a 4-bit result \(R\): \(Z = \neg(R_3 \lor R_2 \lor R_1 \lor R_0)\).
• The Sign flag (S): The sign of the result. In two's complement the most significant bit (MSB) decides it. For 4 bits: \(S = R_3\). If \(S = 1\) the result is negative.
• The Carry-out flag (C): 1 when an unsigned addition overflows (goes past \(15\)), or an unsigned subtraction needs to borrow.
• The Overflow flag (V): 1 when overflow occurs in signed.

The hardware logic for the Overflow flag (V), given the result \(R\) of \(A + B\) or \(A - B\) on \(N\)-bit values (sign bit \(N-1\)):

• For addition: \[V = (A_{N-1} \land B_{N-1} \land \neg R_{N-1}) \lor (\neg A_{N-1} \land \neg B_{N-1} \land R_{N-1})\] (Overflow happens when two same-signed numbers add to a result of the opposite sign.)
• For subtraction: \[V = (A_{N-1} \land \neg B_{N-1} \land \neg R_{N-1}) \lor (\neg A_{N-1} \land B_{N-1} \land R_{N-1})\] (Overflow happens when two differently signed numbers are subtracted and the result takes the opposite sign from the minuend.)

Here is C that simulates, end to end, the algorithm running inside a 4-bit hardware ALU:

#include <stdio.h>
#include <stdbool.h>

typedef struct {
    unsigned char result; // 4-bit result (0-15)
    bool carry;           // Carry-out flag
    bool overflow;        // Overflow flag
    bool zero;            // Zero flag
    bool sign;            // Sign flag
} ALU_Output;

ALU_Output alu_4bit(unsigned char a, unsigned char b, unsigned char opcode) {
    ALU_Output out = {0};
    a &= 0x0F; // clamp the inputs to exactly 4 bits
    b &= 0x0F;
    
    unsigned short temp_res = 0;
    
    switch (opcode) {
        case 0: // ADD
            temp_res = (unsigned short)a + b;
            out.result = temp_res & 0x0F;
            out.carry = (temp_res > 0x0F);
            // Signed overflow: both operands share a sign, the result does not
            out.overflow = (((a >> 3) == (b >> 3)) &&
                            (((a >> 3) ^ (out.result >> 3)) & 1));
            break;
            
        case 1: // SUB
            // A - B is done by adding A to B's two's complement: A + (~B + 1)
            temp_res = (unsigned short)a + ((~b + 1) & 0x0F);
            out.result = temp_res & 0x0F;
            out.carry = (a < b); // for SUB the carry-out acts as a borrow flag
            // Signed overflow for SUB: operands differ in sign, and the result
            // differs in sign from the minuend
            out.overflow = (((a >> 3) != (b >> 3)) &&
                            (((a >> 3) ^ (out.result >> 3)) & 1));
            break;
            
        case 2: // bitwise AND
            out.result = a & b;
            break;
            
        case 3: // bitwise OR
            out.result = a | b;
            break;
            
        case 4: // bitwise XOR
            out.result = a ^ b;
            break;
    }
    
    out.zero = (out.result == 0);
    out.sign = (out.result >> 3) & 1; // the top bit is the sign bit
    
    return out;
}

4. Hands-on: the 4-bit ALU simulator

Below is a visual simulator of a 4-bit ALU. Set the operands \(A\) and \(B\) with the binary toggle buttons, choose an arithmetic or logical operation, and watch the binary and decimal results together with which flags light up. The circuit diagram underneath highlights the path that is active for the operation you picked.

5. Review quiz