XOR using NAND gates – Tech Interview Dot Org

⏱ 2 min read

Create an XOR gate using only NAND gates. (BTW, mostly all circuit problems assume you have two inputs plus 0 and 1 also as inputs).

Solution

You may be able to find the solution on the discussion forum.

2026 Update: Logic Gate Design — NAND is Functionally Complete

NAND is a functionally complete gate: you can build any Boolean function using only NAND gates. This is why modern CPUs are built from NAND gates at the transistor level.

Building XOR from NAND: XOR(A,B) = (A NAND (A NAND B)) NAND (B NAND (A NAND B)). This takes 4 NAND gates.

def NAND(a, b):
    return not (a and b)

# NOT using NAND: NOT(A) = NAND(A, A)
def NOT(a):
    return NAND(a, a)

# AND using NAND: AND(A,B) = NOT(NAND(A,B))
def AND(a, b):
    return NOT(NAND(a, b))

# OR using NAND: OR(A,B) = NAND(NOT(A), NOT(B)) [De Morgan's law]
def OR(a, b):
    return NAND(NOT(a), NOT(b))

# XOR using 4 NAND gates
def XOR_via_NAND(a, b):
    nand_ab = NAND(a, b)           # Gate 1
    nand_a_nab = NAND(a, nand_ab)  # Gate 2
    nand_b_nab = NAND(b, nand_ab)  # Gate 3
    return NAND(nand_a_nab, nand_b_nab)  # Gate 4

# Verify truth table
print("A  B  XOR  NAND-based")
for a in [False, True]:
    for b in [False, True]:
        expected = a ^ b
        result = XOR_via_NAND(a, b)
        print(f"{int(a)}  {int(b)}  {int(expected)}    {int(result)}  {'✓' if expected == result else '✗'}")

# Gate count optimization:
# XOR from 4 NANDs  (minimum proven optimal)
# XOR from 5 NORs
# XOR from 7 AND/OR/NOT gates without restriction

# Real-world: NAND flash memory uses the same principle —
# NAND gates are cheaper to manufacture than AND gates
print("nNAND flash: the same NAND that's functionally complete")
print("is also the dominant storage technology in SSDs and phones")

Interview angle: This question appears in hardware design, FPGA programming, and systems interviews. The deeper question is: “Why is NAND universal?” Answer: because any truth table can be expressed as AND, OR, NOT — and all three can be built from NAND. Connects to computational universality and why a single primitive operation (like NAND or NOR) can compute anything.

💡Strategies for Solving This Problem

Logic Gates and Boolean Algebra

Got this at a systems programming interview. Tests understanding of digital logic and boolean algebra. Important for low-level programming and computer architecture.

The Problem

Implement XOR using only NAND gates. NAND is "universal" - you can build any logic gate from it.

Background

NAND truth table:

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

XOR truth table:

A  B  | XOR
0  0  |  0
0  1  |  1
1  0  |  1
1  1  |  0

Why NAND is Universal

You can build NOT, AND, OR from NAND:

NOT A: NAND(A, A)
AND: NOT(NAND(A, B))
OR: NAND(NOT A, NOT B)

Building XOR

XOR = (A AND NOT B) OR (NOT A AND B)

So we need to express this using only NAND.

The Solution Pattern

XOR can be built with 4 NAND gates:

nand1 = NAND(A, B)
nand2 = NAND(A, nand1)
nand3 = NAND(B, nand1)
result = NAND(nand2, nand3)

Why It Works

Let's trace through:

nand1 = NAND(A, B) = NOT(A AND B)
nand2 = NAND(A, nand1) = NOT(A AND NOT(A AND B)) = NOT A OR B
nand3 = NAND(B, nand1) = NOT(B AND NOT(A AND B)) = NOT B OR A
result = NAND(nand2, nand3) = NOT((NOT A OR B) AND (NOT B OR A))

Through boolean algebra, this reduces to A XOR B.

Alternative: Using 5 NAND Gates

First build NOT, AND, OR, then combine:

NOT A = NAND(A, A)
NOT B = NAND(B, B)
Then use formula: XOR = (A AND NOT B) OR (NOT A AND B)

This uses 5 gates but is easier to understand.

✅Solution

Solution: 4 NAND Gates

function NAND(a, b) {
    return !(a && b);
}

function XOR_from_NAND(a, b) {
    // Gate 1: NAND of inputs
    const nand1 = NAND(a, b);

    // Gate 2: NAND of A and nand1
    const nand2 = NAND(a, nand1);

    // Gate 3: NAND of B and nand1
    const nand3 = NAND(b, nand1);

    // Gate 4: NAND of nand2 and nand3
    const result = NAND(nand2, nand3);

    return result;
}

// Test all combinations
console.log("A  B  | XOR");
console.log("----------");
console.log(`0  0  | ${XOR_from_NAND(0, 0) ? 1 : 0}`);
console.log(`0  1  | ${XOR_from_NAND(0, 1) ? 1 : 0}`);
console.log(`1  0  | ${XOR_from_NAND(1, 0) ? 1 : 0}`);
console.log(`1  1  | ${XOR_from_NAND(1, 1) ? 1 : 0}`);

// Expected output:
// A  B  | XOR
// ----------
// 0  0  | 0
// 0  1  | 1
// 1  0  | 1
// 1  1  | 0

Step-by-Step Trace

For A=1, B=0:

nand1 = NAND(1, 0) = !(1 && 0) = !0 = 1

nand2 = NAND(1, 1) = !(1 && 1) = !1 = 0

nand3 = NAND(0, 1) = !(0 && 1) = !0 = 1

result = NAND(0, 1) = !(0 && 1) = !0 = 1 ✓

For A=1, B=1:

nand1 = NAND(1, 1) = !(1 && 1) = !1 = 0

nand2 = NAND(1, 0) = !(1 && 0) = !0 = 1

nand3 = NAND(1, 0) = !(1 && 0) = !0 = 1

result = NAND(1, 1) = !(1 && 1) = !1 = 0 ✓

Building Other Gates from NAND

function NOT_from_NAND(a) {
    return NAND(a, a);
}

function AND_from_NAND(a, b) {
    const nand = NAND(a, b);
    return NOT_from_NAND(nand);
}

function OR_from_NAND(a, b) {
    const notA = NOT_from_NAND(a);
    const notB = NOT_from_NAND(b);
    return NAND(notA, notB);
}

function NOR_from_NAND(a, b) {
    const or = OR_from_NAND(a, b);
    return NOT_from_NAND(or);
}

function XNOR_from_NAND(a, b) {
    const xor = XOR_from_NAND(a, b);
    return NOT_from_NAND(xor);
}

// Test
console.log("NOT 1:", NOT_from_NAND(1));      // 0
console.log("AND(1,0):", AND_from_NAND(1,0)); // 0
console.log("OR(1,0):", OR_from_NAND(1,0));   // 1
console.log("XOR(1,0):", XOR_from_NAND(1,0)); // 1

Circuit Diagram (ASCII)

A ----+----[NAND]---- nand1 ----+---- [NAND]---- nand2 ----+
      |       |                  |                          |
B ----+-------+                  |                          |
      |                          |                          |
      +----[NAND]---- nand3 -----+---- [NAND]-------------- XOR
           |
           +----------------------+

Alternative: 5 NAND Implementation

function XOR_5gates(a, b) {
    // XOR = (A AND NOT B) OR (NOT A AND B)

    // Build NOT gates
    const notA = NAND(a, a);
    const notB = NAND(b, b);

    // Build AND gates using NAND
    const aAndNotB = NAND(NAND(a, notB), NAND(a, notB));
    const notAAndB = NAND(NAND(notA, b), NAND(notA, b));

    // Build OR using NAND
    const result = NAND(NAND(aAndNotB, aAndNotB), NAND(notAAndB, notAAndB));

    return result;
}

// This uses more gates but follows the logical formula directly

Truth Table Verification

function verifyXOR() {
    const inputs = [[0,0], [0,1], [1,0], [1,1]];
    const expected = [0, 1, 1, 0];

    console.log("Verification:");
    for (let i = 0; i < inputs.length; i++) {
        const [a, b] = inputs[i];
        const result = XOR_from_NAND(a, b) ? 1 : 0;
        const match = result === expected[i] ? "✓" : "✗";
        console.log(`XOR(${a}, ${b}) = ${result} ${match}`);
    }
}

verifyXOR();

Why NAND is Universal

Functional completeness: Any boolean function can be expressed using only NAND.

Practical importance: NAND gates are easy to manufacture in hardware (transistor implementation is simple).

NOR is also universal: Same properties, different implementation.

Complexity

Gates needed for XOR: 4 (optimal)
Alternative methods: 5 gates (easier to understand)
Time complexity: O(1) - constant number of operations
Space complexity: O(1)

Real-World Applications

CPU design: All logic gates in processors
Error detection: Parity bits use XOR
Cryptography: XOR for encryption
Memory: XOR for error correction codes

Common Mistakes

Wrong gate count: Using more than 4 NAND gates
Incorrect wiring: Wrong connections between gates
Not testing all cases: Must verify all 4 input combinations
Confusing XOR with OR: XOR is exclusive OR (not both)

Follow-Up Questions

Q: Build half adder using NAND?
A: Sum = XOR, Carry = AND (both from NAND)

Q: Build full adder?
A: Use two half adders and an OR gate

Q: Why not use NOR instead?
A: NOR is also universal, choice depends on manufacturing

Solution

2026 Update: Logic Gate Design — NAND is Functionally Complete

💡Strategies for Solving This Problem

Logic Gates and Boolean Algebra

The Problem

Background

Why NAND is Universal

Building XOR

The Solution Pattern

Why It Works

Alternative: Using 5 NAND Gates

✅Solution

Solution: 4 NAND Gates

Step-by-Step Trace

Building Other Gates from NAND

Circuit Diagram (ASCII)

Alternative: 5 NAND Implementation

Truth Table Verification

Why NAND is Universal

Complexity

Real-World Applications

Common Mistakes

Follow-Up Questions

Related Problems