Joseph Mosby
@josephmosby
credit: buzzfeed, naturally
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 |
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 |
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) # 💯
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 |
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
addxy = sixteen_bit_adder(a16=usex, b16=usey)
andxy = sixteen_bit_and(a16=usex, b16=usey)
posout = sixteen_bit_mux(a16=addxy, b16=addxy, sel=f, out=posout)
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 |
Special thanks and credit to NAND2Tetris for teaching me ALUs and being the inspiration for much of this talk
/
#