NAND-only Full Adder
The NAND gate is functionally complete, meaning any Boolean function can be expressed using only NAND gates. This is not just a theoretical curiosity — in CMOS silicon, NAND gates are the preferred primitive because they are faster and smaller than AND or OR gates. Every foundational logic block you see in real chips, from adders to ALUs, can be decomposed into NAND networks. Companies like Intel and AMD interview candidates on exactly this decomposition.
Your task is to implement a 1-bit full adder using only NAND2 gates. A full adder takes three single-bit inputs — A, B, and a carry-in Cin — and produces two outputs: Sum (the XOR of all three) and Cout (the carry-out, which is 1 when at least two of the three inputs are 1). The complete truth table is shown below.
| A | B | Cin | Sum | Cout | |---|---|-----|-----|------| | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | | 0 | 1 | 0 | 1 | 0 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 1 | 1 |
The canonical NAND-only full adder requires exactly 9 NAND2 gates. Achieving fewer is not possible within the constraints. Think carefully about how to share intermediate NAND outputs — the key insight is that the intermediate signal NAND(A, B) appears in both the Sum and Cout paths, and reusing it is what brings the gate count to 9.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | First addend bit | | B | input | 1 | Second addend bit | | Cin | input | 1 | Carry-in from a less significant stage | | Sum | output | 1 | A XOR B XOR Cin | | Cout | output | 1 | Carry-out, 1 when two or more inputs are 1 |
Constraints
- Only NAND2 gates are allowed. No AND, OR, NOT, XOR, or any other gate type.
- The optimal solution uses exactly 9 NAND2 gates — solutions using more are accepted but will not earn the efficiency bonus.
- Both Sum and Cout must be derived from the same NAND network (no separate sub-circuits for each).
- Intermediate NAND outputs may be reused by multiple downstream gates.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.