VLSI DV Interview Puzzles · All levels

Minimum NAND Gates for XOR

Implement XOR using only 2-input NAND gates. What is the minimum number of NAND gates and one valid construction?

Puzzle

Difficulty: Medium · Puzzle 3 of 6 · Topic: Digital Logic Puzzles

Implement XOR using only 2-input NAND gates. What is the minimum number of NAND gates and one valid construction?

Code

systemverilog

n1 = ~(A & B);
n2 = ~(A & n1);
n3 = ~(B & n1);
Y  = ~(n2 & n3); // XOR

Hint

Use the canonical 4-NAND XOR network.

Step-by-step solution

diagram

1) Create n1 = NAND(A,B) = ~(A&B).
2) Create n2 = NAND(A,n1) and n3 = NAND(B,n1).
3) Final output Y = NAND(n2,n3).
4) Substituting shows Y = A^B.
5) This uses 4 NAND gates, which is the known minimum for XOR with 2-input NAND-only logic.

Answer

Answer: Minimum is 4 NAND gates.

Why candidates get it wrong

Claiming 3 NANDs works; it cannot realize full XOR truth table.

Interviewer follow-up

What is the minimum NAND count for XNOR?

Navigate