RC12. Building an ALU
Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023
Here’s an ALU.
Looks confusing. And, well, it sort of is, at least at first. The ALU is the arithmetic logic unit, and it does all sorts of cool things. This one takes as its input two 16bit numbers, x
and y
, as well as six 1bit flags:
zx
: if this is 1, zero thex
input, otherwise leavex
as isnx
: if this is 1, negate thex
input, otherwise leave as iszy
: if this is 1, zero they
input, otherwise leavey
as isny
: if this is 1, negate they
input, otherwise leavey
as isf
: function selector – if 1, then returnx + y
, otherwise returnx & y
no
: if this is 1, negate the output
This ALU also has three outputs:
 `f(x, y): this is the 16bit integer that is the result of all of the above operations
ng
: this is a flag that indicates whether the resulting output is a negative number – 1 means yes, 0 means nozr
: this is a flag that indicates whether the resulting output is 0 – 1 means yes, 0 means no
As a result of the 6 input flags, an amazing number of operations can be performed on the incoming x
and y
integers. Here’s an abbreviated truth table that shows the various functions and outputs that can be toggled by turning on and off specific input flags:
zx  nx  zy  ny  f  no  out 

1  0  1  0  1  0  0 
1  1  1  1  1  1  1 
1  1  1  0  1  0  1 
0  0  1  1  0  0  x 
1  1  0  0  0  0  y 
0  0  1  1  0  1  !x 
1  1  0  0  0  1  !y 
0  0  1  1  1  1  x 
1  1  0  0  1  1  y 
0  1  1  1  1  1  x+1 
1  1  0  1  1  1  y+1 
0  0  1  1  1  0  x1 
1  1  0  0  1  0  y1 
0  0  0  0  1  0  x+y 
0  1  0  0  1  1  xy 
0  0  0  1  1  1  yx 
0  0  0  0  0  0  x&y 
0  1  0  1  0  1  xy 
What wasn’t immediately obvious to me until after implementing this is that the input integers x
and y
are fed through a kind of pipeline, zeroing them out and/or negating them per the nx
, zx
, ny
, and zy
flags, and then operated on according to the f
flag, and then negated or not depending on the no
flag, and then output in three different ways. As a diagram this flow of information is easier to follow:
Effectively what’s happening in the first few steps is that I’m using a series of Mux16s as almost conditional statements that choose between one of two inputs.
 The first, leftmost Mux16s, for instance, each take in an input integer (
x
ory
) as one of their inputs and 0 as their other, so that ifzx
/zy
is toggled off, thex
/y
input is selected, otherwise the0
s are selected.  The next Mux16 pair is responsible for negating the input if needed, so each has the result of the previous Mux16 as one input and its negation for the other, and these are selected using the
nx
/ny
bit.  The results of the
x>zx>nx
andy>zy>ny
operations are both added together andAND
ed together, and these two results are fed into yet another Mux 16, which is toggled by thef
selector bit. Iff
is True/1, then the result of the adder is selected, otherwise the result of the And16 is selected.  Finally, we pass the result of the above Mux16 and its negation to one final Mux16, which is toggled with the
no
bit and is responsible for selecting the negated or nonnegated output.
At this point it’s just a matter of segmenting the output in a few ways: we output the 16bit result (out
) as well as flags to indicate whether the result is negative (ng
) or zero (zr
).
 To determine whether the result is zero, we simpy have to
OR
all 16 bits together, which here I am using an Or16Way to accomplish. If any of the bits is 1, the result of this Or16Way will also be 1. Only if all the bits are zero (and thus the integer that they represent is also zero) will the result of this Or16Way be 0. Becausezr
is 1 if all the bits are 0, we have to negate the result.  As for the
ng
flag, we simply need to return the most significant bit, which is the sign indicator here. If the most significant bit is 1, that means we’re dealing with a negative number andng
too should be set to 1. Otherwise, the output is positive andng
will be 0.
Simulated Examples
Because following the diagram can be a bit tricky, I wrote a little simulator that shows the various transformations that are happening to the inputs. Let’s look at a few examples.
Example 1: f(x, y) = y  x
According to the chart, we should expect f(x, y)
in this case to be y  x
:
ALU_sim(x='10010111', y='00001010', zx=0, nx=0, zy=0, ny=1, f=1, no=1)
x y
INPUT: 10010111 => 105 00001010 => 10
 
zx=0 10010111 => 105 
 
nx=0 10010111 => 105 
 
zy=0  00001010 => 10
 
ny=1  11110101 => 11
 



f: + 10001100 => 116

no=1 01110011 => 115


OUTPUT:   
ng 0  
 
zr 0 

f(x, y) 01110011 => 115
Example 2: f(x, y) = x  y
ALU_sim(x='11001011', y='00100011', zx=0, nx=1, zy=0, ny=0, f=1, no=1)
x y
INPUT: 11001011 => 53 00100011 => 35
 
zx=0 11001011 => 53 
 
nx=1 00110100 => 52 
 
zy=0  00100011 => 35
 
ny=0  00100011 => 35
 



f: + 01010111 => 87

no=1 10101000 => 88


OUTPUT:   
ng 1  
 
zr 0 

f(x, y) 10101000 => 88
Example 3: f(x, y) = y + 1
ALU_sim(x='11001011', y='00100011', zx=1, nx=1, zy=0, ny=1, f=1, no=1)
x y
INPUT: 11001011 => 53 00100011 => 35
 
zx=1 00000000 => 0 
 
nx=1 11111111 => 1 
 
zy=0  00100011 => 35
 
ny=1  11011100 => 36
 



f: + 11011011 => 37

no=1 00100100 => 36


OUTPUT:   
ng 0  
 
zr 0 

f(x, y) 00100100 => 36
Example 4: ` f(x, y) = x`
ALU_sim(x='11000010', y='10011100', zx=0, nx=0, zy=1, ny=1, f=1, no=1)
x y
INPUT: 11000010 => 62 10011100 => 100
 
zx=0 11000010 => 62 
 
nx=0 11000010 => 62 
 
zy=1  00000000 => 0
 
ny=1  11111111 => 1
 



f: + 11000001 => 63

no=1 00111110 => 62


OUTPUT:   
ng 0  
 
zr 0 

f(x, y) 00111110 => 62
Example 5: f(x, y) = x  y
ALU_sim(x='11000010', y='10011100', zx=0, nx=1, zy=0, ny=1, f=0, no=1)
x y
INPUT: 11000010 => 62 10011100 => 100
 
zx=0 11000010 => 62 
 
nx=1 00111101 => 61 
 
zy=0  10011100 => 100
 
ny=1  01100011 => 99
 



f: & 00100001 => 33

no=1 11011110 => 34


OUTPUT:   
ng 1  
 
zr 0 

f(x, y) 11011110 => 34
There ya go! An ALU in action.
Etc.
Here’s what else went down today:
 excellent coffee chats
 compared ALUs in nand2tetris group
 made some fun leaps in Vim and CLI thanks to some tips from other recursers. Now I know about the ctrlz / fg window toggling thing in vim. I also installed
just
, the projectspecific command manager, which led to installingvimplug
for a vim plugin manager which I am now using to managevimjust
, my new syntax highlighter. Alsoripgrep
which seems useful.