The Old techInterview Forum - XOR using NAND gates

XOR using NAND gates

I solved it using 6 NAND gates (might be possible with less).

XOR:
0 0 - 0
0 1 - 1
1 0 - 1
1 1 - 0

NAND:
0 0 - 1
0 1 - 1
1 0 - 1
1 1 - 0

Difficult to describe in text but i'll try.
Call the two inputs A and B.
Connect A to a 1 and call this gate (A1). Same with (B1). The third nand is with A and B, lets call it (AB). Connect (A1) and (B1) and call it ((A1)(B1)). Connecting this to (AB) will give us (((A1)(B1))(AB)).
(((A1)(B1))(AB)):
0 0 - 1
0 1 - 0
1 0 - 0
1 1 - 1
Which is the inverse of XOR. This is fixed by using a 6th nand and connecting it to (((A1)(B1))(AB)) and 1.
((((A1)(B1))(AB))1)

Fredrik Olsson
Monday, January 03, 2005

I've seen it before, so I won't give it away. But a hint: It can be done with four.

Keith Neufeld
Monday, January 03, 2005

Yes 4 gates, and you don't need any constant inputs

Hint: not(AB) = not(A) + not(B)

Cheers.

Will Smith
Thursday, January 06, 2005

Ah, finally solved it. The solution is very symmetrical and pretty. I guess my hint will be:
Remember that you can use the output from one gate as input to two different gates.

Fredrik Olsson
Friday, January 07, 2005

I managed to get it in 5 nand gates and it took a while to whittle it down to 4 nand gates. The solution is very pretty.
Another hint:

not(A) or B = not(A) or (A and B)

the LHS gives a 5 nand gate solution, but the RHS allows a 4 nand gate solution.

WanFactory
Monday, March 21, 2005