R0KernelPath
module 002 / 262

Boolean Logic & Logic Gates

Two values, a handful of operations, and a universe of computation — Boolean logic is the language your CPU speaks at the deepest level.

~12h focused study10 concepts

Overview

Boolean logic is the mathematical bedrock of every computer ever built. Before a single line of C runs, before a kernel boots, before a transistor switches — there is Boolean algebra: a universe of just two values, 0 and 1, true and false, high and low voltage. Everything your CPU does — adds numbers, compares memory addresses, decides which branch to take — ultimately reduces to a cascade of logical operations on bits.

This module takes you from first principles. You will learn why mathematicians and engineers care about a two-valued algebra, how basic logical operations (AND, OR, NOT, and friends) work, how those operations are physically realized as logic gates in silicon, and how gates snap together like LEGO bricks to build circuits that can add numbers, choose between inputs, and even remember state. By the end, you will be able to trace the path from a high-level a + b in C all the way down to the individual gates that do the work.

What makes this beautiful is the radical simplicity at the bottom. You do not need three values or ten values — just two. And yet from those two values and a handful of operations, you can represent any number, any instruction, any piece of data, and build any computation imaginable. The founders of the field — George Boole, Claude Shannon, John von Neumann — built the entire digital revolution on this insight.

Along the way you will discover some elegant surprises: that NAND alone is sufficient to build any circuit in existence, that a pair of cross-coupled gates can remember a bit forever, and that the same algebraic identities you use to simplify logical expressions also help compilers optimize your code. These are not curiosities — they are the living heart of systems programming.

why this matters for the kernel

Kernel contributors and systems programmers speak in bits constantly. Interrupt masks, permission flags in page table entries, CPU feature bits in CPUID, network packet headers, file permission bits in inode.i_mode — all of these are bit fields manipulated with bitwise AND, OR, XOR, and NOT. If you do not have an intuitive feel for what flags &= ~(1 << BIT) does, reading even a simple kernel patch is painful.

More deeply, understanding logic gates and how they compose into arithmetic circuits gives you a mental model for what the CPU is actually doing. When you learn about carry-lookahead adders, you understand why addition on modern CPUs is O(log n) gate delays instead of O(n). When you see a multiplexer, you recognize it in the hardware branch predictor, the register file read port, and the memory bus arbiter. This module is not about memorizing truth tables — it is about building the hardware intuition that makes every higher-level concept (pipelines, caches, virtual memory) click into place rather than feel like magic.

From Gates to a Full Adder

rendering diagram…

A full adder built from two half adders and an OR gate. Each half adder is an XOR (sum) plus AND (carry). Chaining 32 full adders with carry connections gives a 32-bit ripple-carry adder.

The concepts

01Boolean Algebra: The Two-Value Universe

In 1854, George Boole published An Investigation of the Laws of Thought, proposing an algebra where variables take only two values — which we now call 0 (false) and 1 (true). This seems impoverished compared to ordinary algebra over the real numbers, but it turns out to be exactly what you need to describe switching circuits.

The core insight, made precise by Claude Shannon in his 1937 master's thesis, is that an electrical switch has exactly two meaningful states: open (no current flows = 0) and closed (current flows = 1). Shannon showed that any network of switches can be analysed and optimised using Boolean algebra. That paper literally invented digital circuit design.

Boolean algebra has three primary operations:

  • AND (written · or ∧ or &): output is 1 only when both inputs are 1.
  • OR (written + or ∨ or |): output is 1 when at least one input is 1.
  • NOT (written ¬ or ~ or overbar): flips the value — NOT 0 = 1, NOT 1 = 0.

These obey familiar-looking but subtly different laws compared to ordinary algebra:

  • Identity: A AND 1 = A, A OR 0 = A
  • Annihilator: A AND 0 = 0, A OR 1 = 1
  • Idempotence: A AND A = A, A OR A = A
  • Complement: A AND NOT(A) = 0, A OR NOT(A) = 1
  • Commutativity, Associativity, Distributivity: work as you'd expect.

Notice A AND A = A — this is very different from ordinary multiplication! Boolean algebra has a dual nature: every law has a dual obtained by swapping AND↔OR and 0↔1.

In a computer, Boolean algebra is not abstract — it is physical. A wire carrying 0–0.8 V is logic 0; a wire carrying 2.0–3.3 V is logic 1. The entire digital world lives in these two voltage bands.

// Boolean operations in C — these are the bitwise operators
// They operate on every bit of an integer in parallel
#include <stdio.h>

int main(void) {
    unsigned int a = 0b1010;  // 10 decimal
    unsigned int b = 0b1100;  // 12 decimal

    printf("a AND b = %04b\n", a & b);   // 1000 = 8
    printf("a OR  b = %04b\n", a | b);   // 1110 = 14
    printf("NOT a   = %04b\n", (~a) & 0xF); // 0101 = 5  (masked to 4 bits)
    printf("a XOR b = %04b\n", a ^ b);   // 0110 = 6
    return 0;
}

02Truth Tables: Precise Definitions of Operations

A truth table exhaustively lists the output of a Boolean function for every possible combination of inputs. For n inputs, there are 2^n rows. Truth tables are the gold standard for defining and verifying Boolean functions — they leave no ambiguity.

Here are the six fundamental operations with their truth tables:

AND — both must be 1:

A  B | A·B
0  0 |  0
0  1 |  0
1  0 |  0
1  1 |  1

OR — at least one must be 1:

A  B | A+B
0  0 |  0
0  1 |  1
1  0 |  1
1  1 |  1

NOT — inversion:

A | ¬A
0 |  1
1 |  0

XOR (exclusive-or) — exactly one must be 1:

A  B | A⊕B
0  0 |  0
0  1 |  1
1  0 |  1
1  1 |  0

XOR is programmers' best friend for toggling bits: x ^ 1 flips bit 0 of x. It is also the basis of parity checking, CRC error detection, and the add step in AES encryption.

NAND — NOT AND:

A  B | NAND
0  0 |  1
0  1 |  1
1  0 |  1
1  1 |  0

NOR — NOT OR:

A  B | NOR
0  0 |  1
0  1 |  0
1  0 |  0
1  1 |  0

A key insight: there are 2^(2^n) possible Boolean functions of n inputs. For 2 inputs, that is 2^4 = 16 possible functions. AND, OR, XOR, NAND, NOR, XNOR, and a few trivial functions (always-0, always-1, pass-through) account for the interesting ones. Truth tables let you enumerate all of them, which is how engineers prove correctness exhaustively for small circuits.

// Generate a truth table for any 2-input function in C
#include <stdio.h>

typedef int (*BoolFn)(int, int);

int fn_and(int a, int b) { return a & b; }
int fn_xor(int a, int b) { return a ^ b; }
int fn_nand(int a, int b) { return !(a & b); }

void print_truth_table(const char *name, BoolFn f) {
    printf("\n%s:\nA B | out\n---------\n", name);
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 1; b++)
            printf("%d %d |  %d\n", a, b, f(a, b));
}

int main(void) {
    print_truth_table("AND",  fn_and);
    print_truth_table("XOR",  fn_xor);
    print_truth_table("NAND", fn_nand);
    return 0;
}

03De Morgan's Laws: The Duality Principle in Action

De Morgan's laws are two identities that let you push a NOT through an AND or OR gate, swapping the operation in the process:

  1. NOT(A AND B) = (NOT A) OR (NOT B)
  2. NOT(A OR B) = (NOT A) AND (NOT B)

In symbolic notation: ¬(A · B) = ¬A + ¬B and ¬(A + B) = ¬A · ¬B.

A vivid analogy: "I need coffee and breakfast" — the negation is "I do not need coffee or I do not need breakfast." You do not need both anymore if even one is absent.

Why this matters enormously:

  1. Circuit simplification. Real chip designs try to minimize gate count. De Morgan's lets you transform circuits algebraically to find cheaper equivalents.
  2. NAND/NOR completeness. NAND(A,B) = NOT(A AND B) = (NOT A) OR (NOT B). This means NAND naturally is De Morgan's law! And since you can build NOT, AND, and OR from NAND alone (see the next concept), De Morgan's is the algebraic key that unlocks universality.
  3. Programming practice. When you write if (!(a && b)), De Morgan's tells you it is equivalent to if (!a || !b). Compilers use this transformation constantly. So do kernel developers simplifying interrupt-mask logic.

Proof of Law 1 by truth table:

A  B | A AND B | NOT(A AND B) | NOT A | NOT B | NOT A OR NOT B
0  0 |    0    |      1       |   1   |   1   |       1
0  1 |    0    |      1       |   1   |   0   |       1
1  0 |    0    |      1       |   0   |   1   |       1
1  1 |    1    |      0       |   0   |   0   |       0

Columns 4 and 7 are identical — the law holds for all inputs, so it holds universally.

// Demonstrating De Morgan's in C — a practical kernel-style flag check
#include <stdio.h>
#include <assert.h>

// Suppose these are CPU feature flags (like in arch/x86/include/asm/cpufeatures.h)
#define FLAG_SSE   (1 << 0)
#define FLAG_AVX   (1 << 1)

int has_sse_and_avx(unsigned flags) {
    return (flags & FLAG_SSE) && (flags & FLAG_AVX);
}

// De Morgan: NOT(A AND B) == NOT A OR NOT B
int missing_sse_or_avx(unsigned flags) {
    return !(flags & FLAG_SSE) || !(flags & FLAG_AVX);
}

int main(void) {
    for (unsigned f = 0; f < 4; f++) {
        // Both forms must agree
        assert(!has_sse_and_avx(f) == missing_sse_or_avx(f));
    }
    printf("De Morgan verified for all 4 combinations.\n");
    return 0;
}

04Universal Gates: NAND and NOR

A gate is called functionally complete (or universal) if you can build any Boolean function using only copies of that one gate type. Remarkably, both NAND and NOR are universal — meaning a factory that can stamp out only one type of gate can build any digital circuit.

Building everything from NAND:

  • NOT A: NAND(A, A) — feed the same input to both ports.
    • Truth check: NAND(0,0)=1, NAND(1,1)=0. Correct.
  • A AND B: NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))
  • A OR B: By De Morgan's, A OR B = NOT(NOT A AND NOT B) = NAND(NOT A, NOT B) = NAND(NAND(A,A), NAND(B,B))

So with 3 NAND gates you get AND, with 1 you get NOT, and with 3 you get OR. Every logic function decomposes into these three, so NAND is sufficient.

Why does the industry care? In CMOS chip manufacturing, NAND gates are cheaper and faster than AND gates. This is because NAND is directly implemented as a pull-down network of two transistors in series plus a pull-up network — no extra inverter needed. The entire CMOS standard cell library is dominated by NAND and NOR variants. When you look at actual synthesized netlist output from tools like Yosys or Synopsys Design Compiler, nearly every gate is a NAND.

The NOR gate is similarly universal (NOR(A,A)=NOT A; you can derive AND and OR). Historically, the first integrated circuit computers (like early TTL designs) and some Soviet-era computers were built entirely from NOR gates.

The philosophical punch: Universality means complexity is emergent. You do not need a zoo of different components. One primitive, applied recursively, generates all computation. This mirrors Turing completeness at the software level — a minimal set of primitives suffices.

/* Simulate NAND-only logic in C to prove universality */
#include <stdio.h>

static inline int nand(int a, int b) { return !(a & b); }

// Build primitives from NAND only
static inline int not_gate(int a)        { return nand(a, a); }
static inline int and_gate(int a, int b) { return not_gate(nand(a, b)); }
static inline int or_gate(int a, int b)  { return nand(not_gate(a), not_gate(b)); }
static inline int xor_gate(int a, int b) {
    int n = nand(a, b);
    return nand(nand(a, n), nand(b, n));
}

int main(void) {
    printf("XOR (NAND-only):\nA B | out\n");
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 1; b++)
            printf("%d %d |  %d\n", a, b, xor_gate(a, b));
    return 0;
}

05Logic Gates as Physical Devices

A logic gate is a physical electronic device that implements a Boolean operation. In modern computers, gates are built from MOSFET transistors — voltage-controlled switches. A CMOS (Complementary Metal-Oxide-Semiconductor) inverter (NOT gate) uses exactly two transistors: one PMOS (on when input is LOW) and one NMOS (on when input is HIGH). They are always in opposite states, so the output is always driven to a definite voltage — no floating.

A CMOS NAND gate uses four transistors: two PMOS in parallel (pull-up), two NMOS in series (pull-down). Output is LOW only when both inputs are HIGH, because only then are both NMOS transistors ON simultaneously. This maps perfectly to the NAND truth table.

Gate characteristics that matter for hardware design:

  • Propagation delay (t_pd): Time from input change to output reaching valid level. Measured in picoseconds for modern gates. A chain of 50 gates may take ~1 ns total — a 1 GHz clock allows only 1 ns per cycle, so you cannot have arbitrarily deep logic paths.
  • Fan-out: How many gate inputs can one output drive? Exceeding fan-out degrades signal voltage. Buffers/drivers are inserted to restore it.
  • Fan-in: How many inputs can one gate have? NAND4 (4-input NAND) is slower than NAND2 because the series NMOS chain is longer.
  • Power dissipation: Dynamic power scales as C·V²·f (capacitance × voltage² × frequency). This is why CPUs throttle frequency and voltage together.

You interact with gate-level reality whenever you read kernel code dealing with hardware. For example, CPU feature detection (/proc/cpuinfo, CPUID instruction) directly reflects the transistor budget engineers had. The flag CONFIG_X86_64 in the Linux kernel was born from a gate-level architectural decision about how many bits the ALU should be wide.

/* Reading CPU feature flags — gate-level decisions exposed to software */
#include <stdio.h>

/* On x86, CPUID leaf 1 returns feature flags in ECX/EDX.
   These bits reflect whether specific gate arrays were included on die. */
static void cpuid(unsigned leaf,
                  unsigned *eax, unsigned *ebx,
                  unsigned *ecx, unsigned *edx) {
    __asm__ volatile ("cpuid"
        : "=a"(*eax), "=b"(*ebx), "=c"(*ecx), "=d"(*edx)
        : "a"(leaf), "c"(0));
}

int main(void) {
    unsigned eax, ebx, ecx, edx;
    cpuid(1, &eax, &ebx, &ecx, &edx);
    /* EDX bit 25 = SSE, bit 26 = SSE2 */
    printf("SSE  supported: %s\n", (edx >> 25) & 1 ? "yes" : "no");
    printf("SSE2 supported: %s\n", (edx >> 26) & 1 ? "yes" : "no");
    return 0;
}

06Combining Gates: The Half Adder and Full Adder

Gates become interesting when composed. The first non-trivial circuit most engineers build is an adder — a circuit that adds two binary digits.

Half Adder: Adds two 1-bit numbers A and B, producing a 1-bit Sum and a 1-bit Carry.

  • Sum = A XOR B
  • Carry = A AND B

Why XOR for sum? 0+0=0, 0+1=1, 1+0=1 — all match XOR. But 1+1=10 in binary (decimal 2): sum bit is 0 (XOR), carry bit is 1 (AND). Two gates, and you can add bits.

Full Adder: Adds three bits — A, B, and a carry-in (Cin). This is the building block you chain together to add multi-bit numbers.

  • Sum = A XOR B XOR Cin
  • Cout = (A AND B) OR (B AND Cin) OR (A AND Cin)

Alternatively, a full adder is two half adders plus an OR gate:

  1. Half-add A and B → Sum1, Carry1
  2. Half-add Sum1 and Cin → FinalSum, Carry2
  3. Cout = Carry1 OR Carry2

Ripple-Carry Adder: Chain 32 full adders in a row, feeding each Cout into the next Cin. You get a 32-bit adder! The problem: to compute the final sum, the carry must ripple through all 32 stages. With 32 × 2 gate delays per stage, total delay is O(n). This is the naive approach — it works but is slow.

Carry-Lookahead Adder: Uses Boolean algebra to compute all carries in O(log n) gate delays by evaluating carry expressions in parallel. Modern CPUs use this or more advanced variants (Kogge-Stone, Brent-Kung). Your a + b in C completes in ~1 clock cycle partly because of this gate-level optimization.

This progression — half adder → full adder → ripple carry → lookahead — is a masterclass in how gate-level thinking drives algorithm design. The same principle (parallelism via Boolean algebra) appears throughout CPU design.

/* Simulate a ripple-carry adder in C to see the carry propagation */
#include <stdio.h>

typedef struct { int sum, cout; } FAOut;

FAOut full_adder(int a, int b, int cin) {
    FAOut r;
    r.sum  = a ^ b ^ cin;
    r.cout = (a & b) | (b & cin) | (a & cin);
    return r;
}

/* 4-bit ripple-carry adder */
unsigned int ripple_add(unsigned a, unsigned b) {
    int carry = 0;
    unsigned result = 0;
    for (int i = 0; i < 4; i++) {
        int ai = (a >> i) & 1;
        int bi = (b >> i) & 1;
        FAOut fa = full_adder(ai, bi, carry);
        result |= (fa.sum << i);
        carry   = fa.cout;
    }
    if (carry) printf("  (overflow!)\n");
    return result;
}

int main(void) {
    printf("5 + 3 = %u\n", ripple_add(5, 3));   // 8
    printf("7 + 9 = %u\n", ripple_add(7, 9));   // 16 -> overflow in 4-bit
    return 0;
}

07Multiplexers: Selecting Among Inputs

A multiplexer (MUX) is a circuit that selects one of N input lines and routes it to a single output, based on a set of select lines. A 2-to-1 MUX has 2 data inputs (D0, D1), 1 select input (S), and 1 output (Y):

  • When S=0: Y = D0
  • When S=1: Y = D1

Boolean expression: Y = (NOT S AND D0) OR (S AND D1)

Gate implementation: two AND gates, one OR gate, one NOT gate — four gates total.

Why multiplexers matter so much:

  1. Routing in CPUs: The register file read ports are multiplexers — you select which register number to output. The ALU input mux selects between a register value and an immediate from the instruction.
  2. Cache controllers: When multiple cache lines could satisfy a request (direct-mapped vs. set-associative), multiplexers route the right one.
  3. Bus systems: I2C, SPI, PCIe — all involve multiplexing. The kernel's device driver model exists partly because hardware multiplexers create shared buses.
  4. Universal computation: Any Boolean function of n variables can be implemented by a 2^n-to-1 MUX by wiring the function's truth table values to the data inputs. This is used in FPGAs (Field-Programmable Gate Arrays): an FPGA LUT (Look-Up Table) is literally a multiplexer with truth-table values stored in SRAM.

An FPGA LUT-6 has 6 select inputs (for any 6-input Boolean function) driving a 64-to-1 MUX with the desired truth table stored in 64 SRAM bits. This is how a programmable chip works at the gate level — you program the truth tables.

A demultiplexer (DEMUX) does the reverse: routes one input to one of N outputs based on select lines. Together, MUX and DEMUX are fundamental to all switching and routing in hardware.

/* MUX in C, then as an x86 intrinsic to show hardware reality */
#include <stdio.h>

/* Software 2-to-1 MUX */
int mux2(int d0, int d1, int sel) {
    return (!sel & d0) | (sel & d1);
    /* Equivalently: return sel ? d1 : d0;
       A ternary IS a multiplexer conceptually */
}

/* 4-to-1 MUX using 2-to-1 building blocks */
int mux4(int d0, int d1, int d2, int d3, int s1, int s0) {
    int low  = mux2(d0, d1, s0);  // select among first pair
    int high = mux2(d2, d3, s0);  // select among second pair
    return mux2(low, high, s1);   // select the pair
}

int main(void) {
    /* Select input 2 (d2=42) with s1=1, s0=0 */
    printf("%d\n", mux4(10, 20, 42, 80, 1, 0));  // 42
    return 0;
}

08Latches and Flip-Flops: Gates That Remember

All the circuits so far are combinational — the output depends only on the current inputs. Memory requires sequential circuits, where the output depends on current inputs and past state. The simplest memory element is the SR latch (Set-Reset latch).

The SR latch is built from two cross-coupled NOR gates (or NAND gates):

Q  = NOR(R, Q_bar)
Q_bar = NOR(S, Q)

Where Q and Q_bar feed back into each other — this is the feedback that creates memory.

SR NOR Latch truth table:

S  R | Q (next) | Notes
0  0 | Q (hold) | No change — memory!
0  1 |    0     | Reset: Q goes to 0
1  0 |    1     | Set: Q goes to 1
1  1 | invalid  | Forbidden: both outputs try to be 1

When S=R=0, the circuit holds its previous state indefinitely (as long as power is on). This is a positive-feedback loop: Q being 1 reinforces Q_bar being 0, which reinforces Q being 1. The latch is bistable — it has two stable states.

D Latch: Fixes the forbidden state by connecting S and NOT(S) to the SR inputs through a clock (enable) signal. When Enable=1, Q follows D. When Enable=0, Q holds its last value.

D Flip-Flop: The workhorse of digital design. Samples its D input only on the rising edge of a clock. Two D latches in a master-slave configuration. This is how CPU registers work — the register file is an array of flip-flops, clocked by the CPU clock.

Why this matters for the kernel: Every CPU register, every cache line tag, every branch predictor entry, every TLB entry — all stored in flip-flops. When the kernel saves and restores registers in a context switch (switch_to() in arch/x86/include/asm/switch_to.h), it is orchestrating the loading and storing of flip-flop values.

/* Simulate an SR latch in software to see the memory behaviour */
#include <stdio.h>
#include <assert.h>

typedef struct { int Q, Qbar; } SRLatch;

SRLatch sr_nor_tick(SRLatch prev, int S, int R) {
    assert(!(S == 1 && R == 1)); /* forbidden state */
    SRLatch next;
    /* NOR: output is 1 only when both inputs are 0 */
    next.Q    = !(R || prev.Qbar);  /* NOR(R, Qbar) */
    next.Qbar = !(S || prev.Q);     /* NOR(S, Q) */
    return next;
}

int main(void) {
    SRLatch latch = {0, 1}; /* initial state: Q=0 */

    latch = sr_nor_tick(latch, 1, 0); /* SET */
    printf("After SET:   Q=%d\n", latch.Q);   /* 1 */

    latch = sr_nor_tick(latch, 0, 0); /* HOLD */
    printf("After HOLD:  Q=%d\n", latch.Q);   /* still 1 */

    latch = sr_nor_tick(latch, 0, 1); /* RESET */
    printf("After RESET: Q=%d\n", latch.Q);   /* 0 */

    latch = sr_nor_tick(latch, 0, 0); /* HOLD */
    printf("After HOLD:  Q=%d\n", latch.Q);   /* still 0 */
    return 0;
}

09Boolean Simplification and Karnaugh Maps

A Boolean expression derived directly from a truth table (as a sum of minterms) is often redundant — it has more gates than necessary. Simplification reduces gate count, which reduces chip area, power, and propagation delay. There are two main approaches:

Algebraic simplification uses Boolean identities:

  • Absorption: A + AB = A, A(A+B) = A
  • Consensus: AB + AC + BC = AB + AC
  • De Morgan's, distribution, complement, etc.

This requires cleverness and practice — there is no mechanical algorithm.

Karnaugh Maps (K-maps) provide a visual, mechanical simplification method for up to 4-6 variables. You fill the truth table into a grid arranged so that adjacent cells differ in exactly one variable (Gray code ordering). Then you circle the largest possible groups of 1s (groups must be powers of 2: 1, 2, 4, 8...), and each circle gives one product term.

For a 2-variable K-map of F(A,B):

      B=0  B=1
 A=0 [ 1 ][ 1 ]
 A=1 [ 0 ][ 1 ]

Top row (A=0): both cells are 1 → group covers ¬A (regardless of B) Right column (B=1): both cells are 1 → group covers B (regardless of A) Simplified: F = ¬A + B (two terms, not four)

Connection to compilers and CPUs: Modern synthesis tools (Yosys, ABC) and CPU design tools perform multi-level Boolean minimization far more powerful than K-maps — Quine-McCluskey, ESPRESSO, BDD-based methods. When GCC emits a bt (bit test) instruction instead of a compare, it found a simpler Boolean expression for your condition. When the kernel's __builtin_expect and branch prediction hints interact with the hardware predictor, the predictor is essentially doing runtime Boolean simplification of branch history patterns.

Understanding minimization gives you intuition for why some C code compiles to fewer instructions than you expect, and why bit manipulation tricks (like x & (x-1) to clear the lowest set bit) appear throughout the Linux kernel source.

// K-map result verified: F = ~A | B for the 2-var example above
#include <stdio.h>
#include <assert.h>

// Full (un-simplified) expression from truth table:
// F = (~A & ~B) | (~A & B) | (A & B)  [three minterms]
int f_full(int a, int b) {
    return (!a && !b) || (!a && b) || (a && b);
}

// Simplified by K-map: F = ~A | B
int f_simple(int a, int b) {
    return !a || b;
}

int main(void) {
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 1; b++)
            assert(f_full(a,b) == f_simple(a,b));
    printf("Both expressions are equivalent.\n");
    return 0;
}

10Bit Manipulation in C and the Kernel

All the Boolean theory becomes immediately practical in C's bitwise operators, which the Linux kernel uses pervasively. Every bitwise operation in C directly compiles to a single machine instruction on modern CPUs.

The six C bitwise operators and their Boolean meanings:

  • & (AND): used to test or clear specific bits
  • | (OR): used to set specific bits
  • ^ (XOR): used to toggle bits, swap without temp, compute parity
  • ~ (NOT): used to invert all bits (bitwise complement)
  • << (left shift): multiply by 2^n; also used to position bits
  • >> (right shift): divide by 2^n (logical or arithmetic depending on type)

Canonical kernel patterns you will see in include/linux/ and arch/:

/* Set bit n */      flags |= (1UL << n);
/* Clear bit n */    flags &= ~(1UL << n);
/* Toggle bit n */   flags ^= (1UL << n);
/* Test bit n */     if (flags & (1UL << n)) ...
/* Extract field */  val = (reg >> SHIFT) & MASK;
/* Insert field */   reg = (reg & ~(MASK << SHIFT)) | ((val & MASK) << SHIFT);

The Linux kernel's include/linux/bits.h defines BIT(n) as (1UL << (n)) and GENMASK(h,l) for multi-bit masks. These macros appear thousands of times in the source — every time a driver touches a hardware register, it uses Boolean operations.

A particularly elegant XOR trick: you can swap two integers without a temporary variable using a ^= b; b ^= a; a ^= b;. This works because XOR is its own inverse: (a^b)^b = a. The Linux kernel actually has this pattern in a few sorting routines.

Understanding this layer means when you open a driver like drivers/gpu/drm/i915/ or a network driver like drivers/net/ethernet/intel/igb/, the register manipulations are immediately readable rather than opaque.

/* Kernel-style bit manipulation patterns in C */
#include <stdio.h>
#include <stdint.h>

#define BIT(n)         (1UL << (n))
#define GENMASK(h, l)  (((1UL << ((h)-(l)+1)) - 1) << (l))

/* Simulated hardware status register */
#define FLAG_READY     BIT(0)
#define FLAG_ERROR     BIT(3)
#define SPEED_SHIFT    8
#define SPEED_MASK     GENMASK(11, 8)  /* bits 11:8, 4-bit field */

int main(void) {
    uint32_t reg = 0;

    reg |= FLAG_READY;                  /* set READY */
    printf("Set READY:  0x%08X\n", reg);

    /* Insert speed=7 into bits 11:8 */
    reg = (reg & ~SPEED_MASK) | ((7UL << SPEED_SHIFT) & SPEED_MASK);
    printf("Set speed:  0x%08X\n", reg);

    /* Read back speed field */
    uint32_t speed = (reg & SPEED_MASK) >> SPEED_SHIFT;
    printf("Speed read: %u\n", speed);  /* 7 */

    reg |= FLAG_ERROR;                  /* set ERROR */
    reg &= ~FLAG_READY;                 /* clear READY */
    printf("Error only: 0x%08X\n", reg);

    return 0;
}

Key insights

  • ✦Two voltage levels model all computation because physical switches are bistable — they are either open or closed, never half-open.
  • ✦NAND (and NOR) are functionally complete — every possible Boolean function, and therefore every possible digital circuit, can be built from copies of a single gate type.
  • ✦De Morgan's laws are not just algebraic curiosities; they are the identity that makes NAND universal, and they appear every time you simplify a conditional in code.
  • ✦A latch's memory emerges from feedback — the output feeding back to the input creates a stable loop that resists change, which is exactly what storage requires.
  • ✦The half adder and full adder show that arithmetic is Boolean logic; the fact that your CPU adds two 64-bit numbers in one cycle is a consequence of carry-lookahead reducing O(n) gate delays to O(log n).
  • ✦Every `flags &= ~BIT(n)` in the Linux kernel is a direct application of Boolean AND and NOT — there is no abstraction layer between this theory and that code.
  • ✦A 2^n-to-1 MUX can implement any n-input Boolean function by wiring the truth table to its data inputs — this is literally how FPGA lookup tables work.

Common pitfalls

  • ⚠Confusing logical operators (`&&`, `||`, `!`) with bitwise operators (`&`, `|`, `~`) in C: `a & b` operates on every bit in parallel, `a && b` short-circuits and returns 0 or 1. Mixing them in flag checks is a common kernel bug source.
  • ⚠Forgetting the forbidden state in SR latches (S=R=1 for NOR-based, S=R=0 for NAND-based) — this produces undefined/oscillating output and is the source of metastability bugs in real hardware.
  • ⚠Applying De Morgan's incorrectly by not negating both operands: `!(a && b)` is `!a || !b`, NOT `!a && !b`.
  • ⚠Thinking ripple-carry adders are how modern CPUs add — they are not. Hardware uses carry-lookahead or prefix adder trees. Never estimate CPU performance from ripple-carry models.
  • ⚠Using signed integers for bit manipulation in C without care: right-shifting a negative signed integer is implementation-defined (arithmetic vs logical shift). Always use `unsigned` or `uint32_t`/`uint64_t` for bit fields.
  • ⚠Treating the XOR swap trick as always better than a temp variable — modern compilers optimize temp-variable swaps to register moves, and XOR swap fails silently if a and b alias the same memory location.
  • ⚠Believing that more gates always means more logic — sometimes a NAND-only implementation of a function uses *fewer* gates than a mixed AND/OR/NOT implementation, because NAND is the natural primitive in CMOS.

Practice

  1. 01
    easy

    Build a truth table generator in C that takes the number of input variables n (up to 4) and a target function encoded as an integer bitmask (the truth table rows packed into bits), then prints the full truth table with a column for the function output. Verify it against AND, OR, XOR for n=2.

  2. 02
    medium

    Implement a NAND-only logic library in C with functions: nand2, not1, and2, or2, xor2, half_adder, full_adder. Every function must only call nand2 internally — no &&, ||, or ! operators allowed. Write assertions that verify every function against the truth table.

  3. 03
    medium

    Write a 16-bit ripple-carry adder in C that operates bit-by-bit using your full_adder function. Then write a test that exhaustively checks all 256*256 = 65536 combinations of 8-bit inputs, verifying your result matches the C `+` operator. Measure how many full_adder calls are needed per addition.

  4. 04
    easy

    Explore Godbolt Compiler Explorer (godbolt.org). Write a C function that checks if a number is a power of two (`x != 0 && (x & (x-1)) == 0`). Compare the assembly output with -O0 vs -O2. Then write an equivalent using a loop. Explain in a short paragraph how the compiler's Boolean simplification helps.

  5. 05
    hard

    Simulate a 4-bit D-latch register file with 4 registers in C. Implement clock-edge semantics: a write_register(reg_num, value, clock_edge) function that only updates on clock_edge=1, and a read_register(reg_num) function. Simulate a sequence of register writes and reads across multiple clock cycles and print the register state after each cycle.

  6. 06
    hard

    Find three uses of `BIT()` or `GENMASK()` macros in the Linux kernel source on elixir.bootlin.com (search in a driver you find interesting). For each use, describe in plain English what Boolean operation is being performed and why. Then reproduce each snippet in a standalone C file and verify the operation with printf.

Resources

Checkpoints — you can now…

  • ✓You can write the truth table for AND, OR, NOT, XOR, NAND, and NOR from memory without looking anything up.
  • ✓You can apply De Morgan's laws to simplify a negated compound condition in C code and verify the result is equivalent.
  • ✓You can implement NOT, AND, OR, and XOR using only NAND gates, and explain why this makes NAND a universal gate.
  • ✓You can trace through a 4-bit ripple-carry addition step by step, showing the carry propagation between full adders.
  • ✓You can read and write the canonical kernel bit-manipulation patterns: set, clear, toggle, and test a specific bit using BIT(n) and bitwise operators.
  • ✓You can explain why an SR latch remembers its state when both inputs are 0, using the concept of positive feedback.
  • ✓You can use Godbolt to find the x86 assembly for a simple Boolean expression and identify the AND/OR/XOR instructions.