Joseph Mosby
@josephmosby

## hey, what's up, hello

• Python engineer at National Journal
• Aspiring operating system writer

## How does a CPU work, anyway? ## How does a CPU work, anyway?

• Clock
A regular heartbeat running through the CPU to trigger instructions.
• Program counter
A marker for which line of the program should be executed
• Fetch
Retrieve the next instruction from the program memory
• Decode
Interpret the instruction into signals that control other parts of the CPU
• Execute
Do the work. Sometimes, that work is math. credit: buzzfeed, naturally

# When the instruction involves math...

## The Arithmetic Logic Unit! ## The Arithmetic Logic Unit! # Okay, so the ALU takes in two binary numbers, and based on the status of certain flags, it computes a function. Got it. I think.

## Let's build one!

Inputs: x, y - two 16-bit binary numbers
Control Bits: zx, nx, zy, ny, f, no
Outputs:
 x + y x - y y - x 0 1 -1 x y -x -y !x !y x + 1 y + 1 x - 1 y - 1 x & y x | y

Outputs: zr if output == 0, ng if output < 0

## Our Parts

• Single-bit OR
• Single-bit NOT
• Single-bit AND
• Single-bit XOR
• 16-bit Multiplexer
• 16-bit bitwise NOT
• 16-bit bitwise AND credit: electrosmash.com

```					```
def single_bit_or(a, b):
'''
a: single bit, 1 or 0
b: single bit, 1 or 0
'''

if a == 1 or b == 1:
return 1
else:
return 0
```
```
```					```
def single_bit_not(a):
'''
a: single bit, 1 or 0
'''

if a == 1:
return 0
elif a == 0:
return 1
```
```
```					```
def single_bit_and(a, b):
'''
a: single bit, 1 or 0
b: single bit, 1 or 0
'''

if a == 1 and b == 1:
return 1
else:
return 0
```
```
```					```
>>> single_bit_and(1, 0)
>>> 0

>>> single_bit_or(1, 0)
>>> 1

>>> single_bit_not(1)
>>> 0

>>> single_bit_and(1, 1)
>>> 1
```
```
```					```
def single_bit_xor(a, b):
'''
a: single bit, 1 or 0
b: single bit, 1 or 0
'''

if a == b:
return 0
else:
return 1
```
```
```					```
def sixteen_bit_not(a16):
'''
a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]

Flip bits of all inputs
'''
return [single_bit_not(bit) for bit in a16]
```
```
```					```
def sixteen_bit_and(a16, b16):
'''
a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]
b16: binary number, formatted as list [1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1]

Binary AND bits of all inputs
'''
out = []
for i, b in enumerate(a16):
out.append(single_bit_and(a16[i], b16[i]))

return out
```
```
```					```
def sixteen_bit_mux(a16, b16, sel):
'''
a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]
b16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]

If selector bit (sel) == 0, return a16
Else return b16
'''

if sel == 0:
return a16
else:
return b16
```
```

 0 1 + 1 1 1 0 0
```					```
'''
Outputs:
sum: right bit of a + b
carry: left bit of a + b
'''
sum = single_bit_xor(a, b)
carry = single_bit_and(a, b)

return sum, carry
```
```
```					```
'''
Outputs:
sum: right bit of a + b + right_carry
carry: left bit of a + b + right_carry
'''

carry = single_bit_or(carry1, carry2)

return sum, carry
```
```
```					```
'''
Outputs:
sum: right bit of a + b + right_carry
carry: left bit of a + b + right_carry
'''
sum = single_bit_xor(a, b)
carry = single_bit_and(a, b)

return sum, carry

carry = single_bit_or(carry1, carry2)

return sum, carry
```
```

# Time for a sixteen-bit adder...

via GIPHY

```					```
'''
Outputs:
sum: a sixteen-bit-sum of two numbers

Discard the most significant carry bit.
'''
sum = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

sum, carry1 = full_adder(a, b, carry0)
sum, carry2 = full_adder(a, b, carry1)
sum, carry3 = full_adder(a, b, carry2)
sum, carry4 = full_adder(a, b, carry3)
sum, carry5 = full_adder(a, b, carry4)
sum, carry6 = full_adder(a, b, carry5)
sum, carry7 = full_adder(a, b, carry6)
sum, carry8 = full_adder(a, b, carry7)
sum, carry9 = full_adder(a, b, carry8)
sum, carry10 = full_adder(a, b, carry9)
sum, carry11 = full_adder(a, b, carry10)
sum, carry12 = full_adder(a, b, carry11)
sum, carry13 = full_adder(a, b, carry12)
sum, carry14 = full_adder(a, b, carry13)
sum, carry15 = full_adder(a, b, carry14)

return sum
```
```
```					```
>>> a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0] # 36
>>> b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] # 64
>>> a.reverse() # binary numbers go from right to left
>>> b.reverse() # python lists don't
>>> c.reverse()
>>> print(c) # 💯
```
```

## Recap!

• Single-bit OR
• Single-bit NOT
• Single-bit AND
• Single-bit XOR
• 16-bit Multiplexer
• 16-bit bitwise NOT
• 16-bit bitwise AND

## Recap!

Inputs: x, y - two 16-bit binary numbers
Control Bits: zx, nx, zy, ny, f, no
Outputs:
 x + y x - y y - x 0 1 -1 x y -x -y !x !y x + 1 y + 1 x - 1 y - 1 x & y x | y

Outputs: zr if output == 0, ng if output < 0

## all right, let's do this.

• if (zx == 1) set x = 0
• if (nx == 1) set x = !x
• if (zy == 1) set y = 0
• if (ny == 1) set y = !y
• if (f == 1) set out = x + y
• if (f == 0) set out = x & y
• if (no = 1) set out = !out
• if (out == 0) set zr = 1
• if (out < 0) set ng = 1
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
'''
Inputs:

x16, y16,  # 16-bit inputs
zx, # zero the x input?
nx, # negate the x input?
zy, # zero the y input?
ny, # negate the y input?
f,  # compute out = x + y (if 1) or x & y (if 0)
no; # negate the out output?

Outputs:
out16 # 16-bit output
zr # 1 if output is zero
ng # 1 if output is negative
'''

all_zeroes = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
```
```
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
...
### determine the X to use

# zero the x if zx is set, else output incoming x
zerox = sixteen_bit_mux(a16=x16, b16=all_zeroes, sel=zx)

# not the x
notx = sixteen_bit_not(x16)

usex = sixteen_bit_mux(a16=zerox, b16=notx, sel=nx)
```
```
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
...
### determine the Y to use

# zero the y if zy is set, else output incoming y
zeroy = sixteen_bit_mux(a16=y16, b16=all_zeroes, sel=zy)

# not the y
noty = sixteen_bit_not(y16)

usey = sixteen_bit_mux(a16=zeroy, b16=noty, sel=ny)
```
```
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
...
### compute the Fs

andxy = sixteen_bit_and(a16=usex, b16=usey)

negout = sixteen_bit_not(posout)

out16 = sixteen_bit_mux(a16=posout, b16=negout, sel=no)
ng = out16
```
```
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
...
### determine if output is zero
### out16 == all_zeroes
c1 = single_bit_or(out16, out16)
c2 = single_bit_or(out16, out16)
c3 = single_bit_or(out16, out16)
c4 = single_bit_or(out16, out16)
c5 = single_bit_or(out16, out16)
c6 = single_bit_or(out16, out16)
c7 = single_bit_or(out16, out16)
c8 = single_bit_or(out16, out16)

c9 = single_bit_or(c1, c2)
c10 = single_bit_or(c3, c4)
c11 = single_bit_or(c5, c6)
c12 = single_bit_or(c7, c8)
c13 = single_bit_or(c9, c10)
c14 = single_bit_or(c11, c12)
check = single_bit_or(c13, c14)

zr = single_bit_not(check)

return out16, zr, ng
```
```
```				```
>>> a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0] # 36
>>> b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] # 64
>>> a.reverse()
>>> b.reverse()
>>> out, zr, ng = alu(a, b, 0, 0, 0, 0, 1, 0)
>>> print(out) # 💯
>>> print(zr, ng) # 0 0
```
```
zx nx zy ny f no f(x, y)
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
zx nx zy ny f no f(x, y)
1 1 0 0 0 1 !y
0 0 0 0 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 x-1
zx nx zy ny f no f(x, y)
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y

## Gracias!

Special thanks and credit to NAND2Tetris for teaching me ALUs and being the inspiration for much of this talk

/

#