Implement a very simple ALU using only NAND gates

Question

Note: This challenge was inspired by Joe Z's many excellent questions surrounding NAND golfing.

Description

Your goal in this challenge, should you choose to accept it, is to implement a very simple ALU using just NAND gates. The ALU can only perform the the following four operations:

1. 00, meaning increment (wrapping at 15).
2. 01, meaning decrement (wrapping at 0).
3. 10, meaning logical left shift.
4. 11, meaning return zero.

Your circuit should take six inputs and give four outputs. Inputs I0 and I1 denote the operation. Inputs I2 through I5 denote the value to be operated on. Outputs O0 through O3 denote the output value.

Scoring

Your score is the number of gates you utilize to create this circuit. Lower is better.

Test cases

I0-I1	I2-I5	O0-O3
00	0001	0010
01	0000	1111
10	0100	1000
10	0011	0110
11	1100	0000

Answer 1

71 64 49 gates

First define a few additional boolean operations in terms of NAND:

NOT(x)     := NAND(x,x)                           # 1 NAND
AND(a,b)   := NOT(NAND(a,b))                      # 2 NANDs
XOR(a,b)   := NAND(NAND(t=NAND(a,b),a),NAND(t,b)) # 4 NANDs

# AND(XOR(a,b), XOR(c,b)) in 7 NANDs:
XAX(a,b,c) := NOT(NAND(NAND(NAND(NOT(a), b), NAND(c, a)), NAND(c, b)))

Then we can define the ALU with these operations:

ni0    = NOT(i0)
ni1    = NOT(i1)
double = AND(i0,ni1)
o3     = AND(ni0,NOT(i5))
o2     = NAND(NAND(double,i5), NAND(ni0,XOR(XAX(o3,i5,i1),i4)))
o1     = NAND(NAND(double,i4), NAND(ni0,XOR(XAX(o2,i4,i1),i3)))
o0     = NAND(NAND(double,i3), NAND(ni0,XOR(XAX(o1,i3,i1),i2)))

Try it online!

This uses 9 NANDs, 3 NOTs, 2 ANDs, 3 XORs and 3 XAXs for a total of 49 NAND gates.

There is one gate that could be saved by removing some of the abstraction (we could get NOT(o3) for free and use that in the first XAX), but until I find some larger improvement I'd like to keep it simple.

The logic for the three higher bits might seem a bit intimidating, but with some transformations it is actually not bad:
NAND(NAND(...), NAND(...)) is equivalent to OR(AND(...), AND(...)). The left AND reads "operation is double and the bit to right in the input is set", and the right one flips the bit if XAX(new value of bit to the right, old value of bit to the right, decrement) evaluates to 1. And XAX(a,b,c) is equivalent to a>b if c else a<b.

Answer 2

42 gates

a, b, c, d, e, f = I

na = NOT(a)
nb = NOT(b)
nc = NOT(c)
nd = NOT(d)
ne = NOT(e)
nf = NOT(f)

xa = NAND(NAND(a, ne), NAND(na, e))
xb = NAND(NAND(b, ne), NAND(nb, e))
xc = NAND(NAND(c, ne), NAND(nc, e))

o0 = NOT(NAND(na, nf))

M = NOT(NAND(ne, f))

nxa = NOT(xa)

o1 = NAND(NAND(M, a), NAND(nf, XOR(xa, b, nxa, nb)))

nxaxb = NAND(xa,xb)
xaxb = NOT(nxaxb)

o2 = NAND(NAND(M, b), NAND(nf, XOR(xaxb, c, nxaxb, nc)))

nxaxbxc = NAND(xaxb, xc)
xaxbxc = NOT(nxaxbxc)

o3 = NAND(NAND(M, c), NAND(nf, XOR(xaxbxc, d, nxaxbxc, nd)))

Try it online!

11 NOT's, 22 NAND's, 3 XOR's (XOR(a,b) is defined as NAND(NAND(NOT(a), b),NAND(a, NOT(b))) except we pass in NOT(a) and NOT(b)).

Answer 3

88 NAND Gates

This is just the first thing i could think of, given the challenge specification... some obvious things might become apparent later.

Here shown decrementing 6.

Answer 4

46 44 gates

input a[4]
input c[2]
tmp s[4] = a + {1,c[0],c[0],c[0]} // 1+9+9+8=27
tmp !c[1] // 1
tmp t[4] = {0,c[0]<s[0],c[0]<s[1],c[0]<s[2]} // 3+2
out {s[0]&!c[1],c[1]?t[1]:s[1],c[1]?t[2]:s[2],c[1]?t[3]:s[3]} // 11

Maybe we need a checker

s[0]: t+1 = t(!t), costing 1

c[0]>=s[0] is found when making s

out: a?b:c = (a nand b) nand (!a nand c)

You can try it by running this code in console of nandgame.com and refresh

Answer 5

59 56 53 52 51 50 gates

I thought I'd create an actual ALU here, even though it ended up taking more gates than @ovs' answer. Edit: A true ALU would actually use identical lanes for all four bits of the form Result = Input + ((Input & Mask) ^ Flip) + Carry. This would provide for eight different operations:

Mask Flip Carry Result
0    0    0     Input
0    0    1     Input + 1
0    1    0     Input - 1
0    1    1     Input
1    0    0     Input * 2
1    0    1     Input * 2 + 1 (c.f. Z80 SLL "instruction")
1    1    0     -1
1    1    1     0

Each lane (except the last, as the carry out is not required) would use 15 gates, and then 5 gates are needed to generate the desired carry in for the four operations, making a total of 64 gates. However my first approach actually special-cased the first lane, so that I could choose between the input and 1 as the RHS of the full adder:

00: IIII -> IIII + 0001
01: IIII -> IIII - 0001
10: IIII -> IIII + IIII
11: IIII -> IIII - IIII

To get the RHS takes 8 gates:

R2 = NAND(NOT(I2), I0)
R3 = NOT(NAND(I3, I0))
R4 = NOT(NAND(I4, I0))
R5 = NOT(NAND(I5, I0))

To select between + and -, I perform 2's complement on the value. 1's complement takes 16 gates:

S2 = XOR(R2, I1)
S3 = XOR(R3, I1)
S4 = XOR(R4, I1)
S5 = XOR(R5, I1)

To achieve 2's complement we simply add I1 as part of the IIII + SSSS operation:

C0, O0 = ADD(I2, S2, I1)
C1, O1 = ADD(I3, S3, C0)
C2, O2 = ADD(I4, S4, C1)
C3, O3 = ADD(I5, S5, C2)

This takes 36 gates for a grand total of 60 gates, except we don't need C3 which saves a gate.

Notes:

• NOT takes 1 gate:

  NOT(X) = NAND(X, X)
  

• XOR takes 4 gates:

  XOR(X, Y) = _XOR2(X, Y, NAND(X, Y))
  _XOR2(X, Y, W) = NAND(NAND(X, W), NAND(Y, W))
  

• ADD takes 9 gates:

  ADD(X, Y, Z) = _ADD2(X, Y, Z, NAND(Y, Z))
  _ADD2(X, Y, Z, W) = _ADD3(X, W, _XOR2(Y, Z, W))
  _ADD3(X, W, V) = _ADD4(X, W, V, NAND(X, V))
  _ADD4(X, W, V, U) = NAND(W, U), _XOR2(X, V, U)
  

Edit: The LSB's adder's inputs have a lot of redundancy:

S2 = XOR(R2, I1)
C0, O0 = ADD(I2, S2, I1)

But this means that XOR(S2, I1) is just R2, so we can write this as:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
O0 = XOR(I2, XOR(S2, I1))
   = XOR(I2, R2)
   = _XOR2(I2, R2, NAND(I2, R2))

This saves three gates.

Edit: Even more redundancy that I overlooked:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
   = NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, R2))

Although this costs a gate, it makes S2 unnecessary which saves four gates for an overall saving of three gates.

Edit: Found another redundant gate:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
   = NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, NAND(NOT(I2), I0)))
   = NAND(NAND(NOT(R2), I1), NOT(I2))

Although this seems to just change a shared NAND to a shared NOT, I computed NOT(I2) as part of the calculation for R2, so that gate can be shared too, thus saving another gate.

Edit: This applies to O2 as well, then further allowing for a further saving of one gate:

O0 = XOR(I2, XOR(S2, I1))
   = XOR(I2, R2)
   = _XOR2(I2, R2, NAND(I2, R2))
   = _XOR2(I2, R2, NAND(I2, NAND(NOT(I2), I0)))
   = _XOR2(I2, R2, NOT(I2))
   = NAND(NAND(I2, NOT(I2)), NAND(R2, NOT(I2)))
   = NOT(NAND(R2, NOT(I2)))

Edit: One final gate can be saved by eliminating R2.

C0 = NAND(NAND(NOT(R2), I1), NOT(I2))
   = NAND(NAND(NOT(NAND(NOT(I2), I0)), I1), NOT(I2))
   = NAND(NAND(AND(NOT(I2), I0), I1), NOT(I2))
   = OR(AND(AND(NOT(I2), I0), I1), I2)
   = OR(AND(I0, I1), I2)
   = NAND(NAND(I0, I1), NOT(I2))
O0 = NOT(NAND(R2, NOT(I2)))
   = NOT(NAND(NAND(NOT(I2), I0), NOT(I2)))
   = NOT(NAND(OR(I2, NOT(I0)), NOT(I2)))
   = NOT(NAND(NOT(I0), NOT(I2)))