hey, what's up, hello

• Python engineer at National Journal
• Classic computing aficionado
• 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

The Arithmetic Logic Unit!

The Arithmetic Logic Unit!

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

					
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
					
				

					
def half_adder(a, b):
	'''
	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
					
				

					
def full_adder(a, b, right_carry):
	'''
	Outputs:
	sum: right bit of a + b + right_carry
	carry: left bit of a + b + right_carry
	'''

	right_sum, carry1 = half_adder(a, b)
	sum, carry2 = half_adder(right_sum, right_carry)
	carry = single_bit_or(carry1, carry2)
	
	return sum, carry
					
				

					
def full_adder(a, b, right_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

	right_sum, carry1 = half_adder(a, b)
	sum, carry2 = half_adder(right_sum, right_carry)
	carry = single_bit_or(carry1, carry2)
	
	return sum, carry
					
				

					
def sixteen_bit_adder(a16, b16):
	'''
	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[0], carry0 = half_adder(a[0], b[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 = sixteen_bit_adder(a, b)
>>> 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
• A 16-bit adder

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

Gracias!