Basic gates: everything from NAND

CHIP Not {
  IN in;
  OUT out;
  PARTS:
  Nand(a=in, b=in, out=out);
}

Both inputs of one NAND are tied together: Nand(a=in, b=in). Inversion needs no extra part.

CHIP And {
  IN a, b;
  OUT out;
  PARTS:
  Nand(a=a, b=b, out=n);
  Not(in=n, out=out);
}

NAND first, then invert. The inversion is itself a NAND — two in total.

CHIP Or {
  IN a, b;
  OUT out;
  PARTS:
  Not(in=a, out=na);
  Not(in=b, out=nb);
  Nand(a=na, b=nb, out=out);
}

Invert both inputs, then combine with NAND: ¬(¬a ∧ ¬b) = a ∨ b.

CHIP Xor {
  IN a, b;
  OUT out;
  PARTS:
  Nand(a=a, b=b, out=n1);
  Nand(a=a, b=n1, out=n2);
  Nand(a=b, b=n1, out=n3);
  Nand(a=n2, b=n3, out=out);
}

Four NANDs: n1 = ¬(a∧b), n2 = ¬(a∧n1), n3 = ¬(b∧n1), out = ¬(n2∧n3).

CHIP Not16 {
  IN in[16];
  OUT out[16];
  PARTS:
  Not(in=in[0], out=out[0]);
  Not(in=in[1], out=out[1]);
  Not(in=in[2], out=out[2]);
  Not(in=in[3], out=out[3]);
  Not(in=in[4], out=out[4]);
  Not(in=in[5], out=out[5]);
  Not(in=in[6], out=out[6]);
  Not(in=in[7], out=out[7]);
  Not(in=in[8], out=out[8]);
  Not(in=in[9], out=out[9]);
  Not(in=in[10], out=out[10]);
  Not(in=in[11], out=out[11]);
  Not(in=in[12], out=out[12]);
  Not(in=in[13], out=out[13]);
  Not(in=in[14], out=out[14]);
  Not(in=in[15], out=out[15]);
}

Sixteen Not gates: gate i touches only in[i] and out[i]; none affects another.

CHIP And16 {
  IN a[16], b[16];
  OUT out[16];
  PARTS:
  And(a=a[0], b=b[0], out=out[0]);
  And(a=a[1], b=b[1], out=out[1]);
  And(a=a[2], b=b[2], out=out[2]);
  And(a=a[3], b=b[3], out=out[3]);
  And(a=a[4], b=b[4], out=out[4]);
  And(a=a[5], b=b[5], out=out[5]);
  And(a=a[6], b=b[6], out=out[6]);
  And(a=a[7], b=b[7], out=out[7]);
  And(a=a[8], b=b[8], out=out[8]);
  And(a=a[9], b=b[9], out=out[9]);
  And(a=a[10], b=b[10], out=out[10]);
  And(a=a[11], b=b[11], out=out[11]);
  And(a=a[12], b=b[12], out=out[12]);
  And(a=a[13], b=b[13], out=out[13]);
  And(a=a[14], b=b[14], out=out[14]);
  And(a=a[15], b=b[15], out=out[15]);
}

Sixteen And gates: no carry, no shared state, each bit on its own.

CHIP Or16 {
  IN a[16], b[16];
  OUT out[16];
  PARTS:
  Or(a=a[0], b=b[0], out=out[0]);
  Or(a=a[1], b=b[1], out=out[1]);
  Or(a=a[2], b=b[2], out=out[2]);
  Or(a=a[3], b=b[3], out=out[3]);
  Or(a=a[4], b=b[4], out=out[4]);
  Or(a=a[5], b=b[5], out=out[5]);
  Or(a=a[6], b=b[6], out=out[6]);
  Or(a=a[7], b=b[7], out=out[7]);
  Or(a=a[8], b=b[8], out=out[8]);
  Or(a=a[9], b=b[9], out=out[9]);
  Or(a=a[10], b=b[10], out=out[10]);
  Or(a=a[11], b=b[11], out=out[11]);
  Or(a=a[12], b=b[12], out=out[12]);
  Or(a=a[13], b=b[13], out=out[13]);
  Or(a=a[14], b=b[14], out=out[14]);
  Or(a=a[15], b=b[15], out=out[15]);
}

Sixteen Or gates. Same as And16, only the gate changes.

CHIP Mux16 {
  IN a[16], b[16], sel;
  OUT out[16];
  PARTS:
  Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
  Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
  Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
  Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
  Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
  Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
  Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
  Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
  Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
  Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
  Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
  Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
  Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
  Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
  Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
  Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}

Copied bit by bit: bit i depends only on a[i], b[i] and the same sel.

CHIP Mux4Way16 {
  IN a[16], b[16], c[16], d[16], sel[2];
  OUT out[16];
  PARTS:
  Mux16(a=a, b=b, sel=sel[0], out=ab);
  Mux16(a=c, b=d, sel=sel[0], out=cd);
  Mux16(a=ab, b=cd, sel=sel[1], out=out);
}

Two levels of Mux16: sel[0] picks one of (a,b) and one of (c,d), then sel[1] picks between those two results.

CHIP Mux8Way16 {
  IN a[16], b[16], c[16], d[16], e[16], f[16], g[16], h[16], sel[3];
  OUT out[16];
  PARTS:
  Mux16(a=a, b=b, sel=sel[0], out=ab);
  Mux16(a=c, b=d, sel=sel[0], out=cd);
  Mux16(a=e, b=f, sel=sel[0], out=ef);
  Mux16(a=g, b=h, sel=sel[0], out=gh);
  Mux16(a=ab, b=cd, sel=sel[1], out=abcd);
  Mux16(a=ef, b=gh, sel=sel[1], out=efgh);
  Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
}

Three levels of Mux16: 4 → 2 → 1, one sel bit per level.

CHIP DMux4Way {
  IN in, sel[2];
  OUT a, b, c, d;
  PARTS:
  Not(in=sel[0], out=ns0);
  Not(in=sel[1], out=ns1);
  And(a=in, b=ns1, out=t1);
  And(a=t1, b=ns0, out=a);
  And(a=t1, b=sel[0], out=b);
  And(a=in, b=sel[1], out=t2);
  And(a=t2, b=ns0, out=c);
  And(a=t2, b=sel[0], out=d);
}

Split by sel[1] into halves, then by sel[0] into two each; the other outputs are forced to 0 by And gates.

CHIP DMux8Way {
  IN in, sel[3];
  OUT a, b, c, d, e, f, g, h;
  PARTS:
  Not(in=sel[0], out=ns0);
  Not(in=sel[1], out=ns1);
  Not(in=sel[2], out=ns2);
  And(a=in, b=ns2, out=t1);
  And(a=t1, b=ns1, out=t2);
  And(a=t2, b=ns0, out=a);
  And(a=t2, b=sel[0], out=b);
  And(a=t1, b=sel[1], out=t3);
  And(a=t3, b=ns0, out=c);
  And(a=t3, b=sel[0], out=d);
  And(a=in, b=sel[2], out=t4);
  And(a=t4, b=ns1, out=t5);
  And(a=t5, b=ns0, out=e);
  And(a=t5, b=sel[0], out=f);
  And(a=t4, b=sel[1], out=t6);
  And(a=t6, b=ns0, out=g);
  And(a=t6, b=sel[0], out=h);
}

Three levels of DMux4Way: every output is an And gate, decided by all three sel bits.

CHIP Or8Way {
  IN in[8];
  OUT out;
  PARTS:
  Or(a=in[0], b=in[1], out=t1);
  Or(a=t1, b=in[2], out=t2);
  Or(a=t2, b=in[3], out=t3);
  Or(a=t3, b=in[4], out=t4);
  Or(a=t4, b=in[5], out=t5);
  Or(a=t5, b=in[6], out=t6);
  Or(a=t6, b=in[7], out=out);
}

Eight inputs chained into one OR — if any bit is 1, the result is 1.