Joseph Mosby
@josephmosby

## hey, what's up, hello

• Python engineer at National Journal
• Aspiring operating system writer

## 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

# 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[1], carry1 = full_adder(a[1], b[1], carry0)
sum[2], carry2 = full_adder(a[2], b[2], carry1)
sum[3], carry3 = full_adder(a[3], b[3], carry2)
sum[4], carry4 = full_adder(a[4], b[4], carry3)
sum[5], carry5 = full_adder(a[5], b[5], carry4)
sum[6], carry6 = full_adder(a[6], b[6], carry5)
sum[7], carry7 = full_adder(a[7], b[7], carry6)
sum[8], carry8 = full_adder(a[8], b[8], carry7)
sum[9], carry9 = full_adder(a[9], b[9], carry8)
sum[10], carry10 = full_adder(a[10], b[10], carry9)
sum[11], carry11 = full_adder(a[11], b[11], carry10)
sum[12], carry12 = full_adder(a[12], b[12], carry11)
sum[13], carry13 = full_adder(a[13], b[13], carry12)
sum[14], carry14 = full_adder(a[14], b[14], carry13)
sum[15], carry15 = full_adder(a[15], b[15], 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[15]
```
```
```				```
def alu(x16, y16, zx, nx, zy, ny, f, no):
...
### determine if output is zero
### out16 == all_zeroes
c1 = single_bit_or(out16[0], out16[1])
c2 = single_bit_or(out16[2], out16[3])
c3 = single_bit_or(out16[4], out16[5])
c4 = single_bit_or(out16[6], out16[7])
c5 = single_bit_or(out16[8], out16[9])
c6 = single_bit_or(out16[10], out16[11])
c7 = single_bit_or(out16[12], out16[13])
c8 = single_bit_or(out16[14], out16[15])

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

/

#