[Question]
  [
*Note: This challenge was inspired by [Joe Z's](https://codegolf.stackexchange.com/users/7110/joe-z) 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]
# ~~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!](https://tio.run/##hVRda9swFH33r7gwgqyghjjJOgjNoLDHkcLYQ8GYoNhKK3AkI8tZP397dq@sJmmXspdYOvec@600j/7emulF89g87stati381F45Wc8TgEptYLXSRvvVKm1VvRFg5FZxsgEQMKI7LAIcBWon6056FQV4a6PAKd85E5D8IC6SpI@7vF7@@CRorTZegNN39/40NsEYmz5HMLAQDd//piSRefA1OvACIxDWb4Tg7xwjVpVdyOE6SSjc8uZ3@hACRBuVlj6IB97b6SbF@h0DJcsehzWPvJtf/9CIQlzJRdAcuLcnZCp/@Rbko5h@vEB9PB09XN@SQJRn8zr5ieHXlAIBpQDJTy7oEV1q03S@xUzyItlYBxq0ASfNnUovQ4S4OUwPKjbQCNS2xKamPA9rgaa4iWnYOST0LkeyaZSpenRv9JiGsAiZ6jFPjM5OgIwnle3WNUWi9PRYGALtFHoWgehDBPZXTNxOouVYce9BoDkWSQJqOLXMTtEg0KfQMyrcZp/qZ2f1EzT0@mnQjz/VT8/qMzT0@gnq91@gdAo3FLxEUT/aSpXvF7Lttunu6kpDmIzY0WyU6bbYbtxtp3bKtapCDSXU@bdJbph91q8MPsxzxoukcdr4lAEbfhMw7CeVT@aFYC/AxDA64ZHHcT1a79DnczoWYz5n2pRM4DnDM6aL5yzgfe3hSqYn5Sx7TfS2sc4D7Ye3tm7Dhjn7h3I6gKPG2aorfZqj20I41WBfFrUyaZ8eDx3BzHZUG73s1PLjC680Sp90E9kC3WM7Qu2W4sSSCvQRix9ctrjJVFiO5Hw@KQrsBR2pEcBeGF4pHp7hBQaTCi6@04fBAFIaUuTinOlGVHpYrWoWDICFN7ABWdcHYv8vFpu6/ws "Python 3 (PyPy) – 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]
# 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!](https://tio.run/##fVRLa9tAEL7rVyyUNhJVw74fhgQKveSQCEoPheAUPRuXeGVkl6qX/vV09mVbSamM7J2Zb@abmZ3x7vfhcbTsuesHdPfx7lNel6gpVhmCZ@oPPyeLiOZcKs6xYgobIYgk4iGv3zVFlnm36kteL11SpDpCvlaffeASWfixieBNxO9RjR5QE3W/HvupByC6Qn/qqKttB25O07ziSWQQtgwaz1MA9w143EvCtSFcGkKZFERRLMoMMakN41oTrjgxBDPKQEuwFgRTYahQhAgM9YJWEaUUJZwaLrSRXkedJ5aaaKy11zizkYoasc4qR0woNUpTw5SR2ChKtcYuGlNaCWYog0cTyajTUqIgB8@vNVdUM@ry4UwaJihhlFNIQuJ16Oihbp76/KZEVeylK/XmfrX6QNZedhlUZ/KTyygch3FC39DGoqm23/tc8hjCwy7r3a63XX5xcflj3Nh8f5jyzVtaeK@N8wIWui7Qe3QBH/j@D5CuIvDq@hV2TNjRYSu4rpSDv7XN9TU5C7U@Wn1rx2QNzqe69k5@CnWfqtpNG3vI9zARftC3NeQQiw5j2ZaoK1FfosG1MfMWP4FhuIPcRLmJchvlNspdlLso91HuozxEeSgCwewJFiPcpxF2e9LHnszNAtcscM0Zrl3g2gWuDTgPHHHM5Ehlh2S7XZhcR5LFzqkhc50CkQXjrdv4RDiUfu3nuPdz2NCzYKeywDbHpiY1sHhIIqIviZrXRHO4SBtOtl2SnboT7HN7Ypzbc05nCazsJWv7L9Y5TI9NZ9sdmeP/1P2IS2gWvBRetn6uthA5jGEWhhPGGhZ2C36n1d4Wz38B "Python 3 – 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]
# 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.
[![Curcuit](https://i.stack.imgur.com/sIM6i.png)](https://i.stack.imgur.com/sIM6i.png)
[Answer]
#  ~~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](https://tio.run/##7Zlvb9s2EMbf71MEeuOt8NQ7Hv@66IssSYcAhjcs7VAg8Asv1jJvjmTYSpoiyGfPaIlyk5aypVFeByxAEDnI3aPjQ1r8Uffn5GayuljOFvn3N/rh5YuH29d3vdEknf44uUoGR9erPLs6yq4WWZqk@YB6g95d9FfyMRpEFPWj1AbZj4fT6Xv71yxdXOeraHB@Fy1maflhPvktmdsQ@@8Ps2n@RzTA@/F9v4OIcT/KrvP6Ox7tFnzzD@45nU0ul5OraHAXpdk0KaPzj4u1D6PD0bFNuI0GTJp@ZF0i4rFQkpEGMkpr4tamqQ2FaH07Tx4UeSh1TJIhoDRaAxrh8rAmD6jIYxJjEqAVlyTBsCqN@dOIyzJNFGVKwRlJQsmVy6OaPM2LPAk8BmGkYkzROtWl8Zo0U7rCEWLDkRDsj9KiqlLUpBEWaQIgFsCYvRMHZIhVldKfx3WVp2MNilCBtcXevJoE5c/TqjRFmRiM4UyD5ExgNTj9OOt09GuZJKQoZ86YuBqPidYr5iJL0@Qin2Vuaa2y6@VFUi2g03Vg8c2JNqHZ8rSatCifLC@T/Ek0fBFpV9O6Jo@y8MU2VMVaVdZYFVvUSgGq9bW285a1qBca18ta1NtclfayDijY2zpl3qJevzI2Vq6vWTauV7SoVwWoduWvbFEvD1DFDlTV3taC2ku92h@5yGapAxC7ByAYty1CiRNBX2/dYiDNl59pYbxurFqSWAtpDJWu98KEStu9wU7ffa9fD8LsEQizTyDMOLeodsCaw7BsQLJfhm@D0LOfh6dvUToEErpckQJ94ElllBIlBnLyYuaGcQwwFwexlyydnkRwnMd9HPn@p1@q6kpqtTS30ePeSHJ0RY/oSnhrRBAlvlmW3YQ@AcQN51n8FBWP@ojw7GR4cvTWAbbgDu@UDwMfh5Iyn4WaulDBygIKfC@NB/@oyDlvgXszR@gdlZTllKPWVeCTOfrh3eh4eFItEIJy6tUmmMKgFTqAVg@KYgd86ZHlHQCmR1Y0lmVdyLL9eEthstQBYGIAtraylnXArBRAwtjFhIm9AKDYT7EybHWJDsBSBuBqKw@CqJJxt0uRqaVKanzAbUOVIoBVWRf@mGb@OHrhWOsPNvbHtPCHGh9KzH78QWhnEKs1qPkBAiHo@Y3NZbuxqA0hYPP9BttsuixEFjs4nyF5t7zgE5RPl@rthSBhXi/MgoRFvTB1cQT@7DA5TG6S@Wrw5t1weHh8XJwkt7QSSLl39BJiVMiIaSXX1x2tBNKulQAmNoQCpObFVW1vJRBzeVrFEiUnTWJ95dtbCZyqAxKLAUkaLcledzQSpOuTCGmztAF7EjPCXsX2RoLUpSfERYxuWMXwdnQSJKsOsBjrykd73dFIUNylcWulFEoQt89UsZ6YbX2EotFQWAKfzoxf@2z13BBo5@1zQyC8IYB7awiw54bAFn//Xw0B9vUbAv/qO///@tv58bY36CuLPefFY5Cice/@1e/Z8tvZwSw9uP1unl1M5mdWaXKZnM/Gr2/tr1ffPLx4@fA3) in console of nandgame.com and refresh
[Answer]
# ~~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)))
```
]