Introduction to Computer Science
Homework 05
1. 关于期末大作业
团队成员
李纪远 / 席萱赫 / 祖家琪 / 刘立威
游戏想法
游戏名：西风哗哗？大赢家！
游戏类型： 大富翁like 棋牌类游戏
具体内容请参见『西风哗哗？大赢家！』用户文档.pdf
2. 进制计算练习
ID%2 == 1
2.3.1
- 假设下面的二进制数是无符号整数，求运算结果：
111101012 + 001011012 = 1001000102
10112 * 11012 = 100011112
111100010110102 / 10102 = 11000010012
2.3.2
- 把2.3.1中各个数转为十进制再计算：
24510 + 4510 = 29010 正确
1110 * 1310 = 14310 正确
1545010 / 1010 = 1154510 正确
2.3.4
- 八位带符号整数中 -12410的补码：
10000100
2.3.7
- 计算无符号二进制整数乘法 100011012 * 10112：
4次移位操作
12次加法操作
2.3.9
- 8位2进制CPU中存放110.12：
110.12 = 1.1012 * 22
| 符号位 | 指数 | ------ | ------ | 尾数 | ------ | ------ | ------ |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
2.3.11
- 8位2进制CPU中以浮点数格式存放110000112，对应十进制是多少：
1 100 0011 → 1.0011 * 212 = 10.0112 = 2.37510
3. 浅谈逻辑运算
2.4.2
- 基本的三种逻辑运算：
AND 与 OR 或 NOT 非
>
- 三种逻辑运算的真值表：
| A | B | NOT A | AND | OR |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
2.4.3
3个输入：23 = 8 个输出
n个输入：2n 个输出
2.4.4
A = 0 ； B = 1 ； C = 1
S = A ∨ B ∨ C = 0
S = A ∧ ￢ B ∨ C = 1
S = ￢ ( A ∧ B ) ∧ ￢ C = 0
2.4.6
0110 = ￢ 1001
1111 = ￢ 1001 ∨ 1001
4. 计算机中的存储
2.5.2
5 GB = 5*1024*1024 KB = 5242880 KB
2.5.4
1TB 数量级：1012
1EB 数量级：1018
2.5.6
沙行勉：\u6c99\u884c\u52c9
2.5.8
'0' = 048
'1' = 049
'0' + '1' = 097 = 'W'
5. Py. 全加器与八位加法运算
全加器
def adder(a,b,c):
carry = (a and b) or (b and c) or (a and c)
sum = (a and b and c) or (a and (not b) and (not c))\
or ((not a) and b and (not c))\
or ((not a) and (not b) and c)
return int(carry), int(sum)
print(adder(1,1,1))
print(adder(0,1,1))
print(adder(1,0,0))
print(adder(0,0,1))
print(adder(0,0,0))
———————————————————————————————————————
#Programming Result:
(1, 1)
(1, 0)
(0, 1)
(0, 1)
(0, 0)
八位加法运算
def adder(a,b,c): #全加器
carry = (a and b) or (b and c) or (a and c)
sum = (a and b and c) or (a and (not b) and (not c))\
or ((not a) and b and (not c))\
or ((not a) and (not b) and c)
return int(carry), int(sum)
def cplm(num): #转为补码，返回列表
n = 8 #长度为八位
r = 0
Rs = []
if num < 0:
num = 2**n+num
while num != 0:
r = num % 2
num //= 2
Rs = [r] + Rs
ans = (n-len(Rs))*[0] + Rs
return ans
def add_8bit(X,Y): #八位加法
L = [];
carry = 0;
for i in range(len(X) - 1, -1, -1):
carry, sum = adder(X[i], Y[i], carry)
L = [sum] + L
return [carry, L]
def bin_2_dec(L): #二进制转为十进制
weight = 1
sum = 0
for i in range(len(L) - 1, -1, -1):
sum += L[i] * weight
weight *= 2
return sum
def solution(x, y):
#x, y = input("Enter 2 Numbers:\n").split(" ")
#x = eval(x)
#y = eval(y)
print("(%d)+(%d):" % (x,y))
X = cplm(x)
Y = cplm(y)
#print(X,Y)
Ans = add_8bit(X,Y)
#print(Ans)
#判断溢出
WA = 0
if x * y > 0: #正溢出/负溢出
if x > 0 and Ans[1][0] == 1:
print("Overflow!\n")
WA = 1
elif x < 0 and Ans[1][0] == 0:
print("Overflow!\n")
WA = 1
if WA == 0:
ans = bin_2_dec(Ans[1])
print(ans,"\n")
solution(100,10)
solution(63,65)
solution(100,-128)
solution(10,-100)
solution(-30,-100)
solution(-1,10)
solution(-12,127)
———————————————————————————————————————
#Programming Result:
(100)+(10):
110
(63)+(65):
Overflow!
(100)+(-128):
228
(10)+(-100):
166
(-30)+(-100):
Overflow!
(-1)+(10):
9
(-12)+(127):
115
6. Py. 十二位乘法运算
def scale(num,N): # 检查可表示范围，num为数，N为CPU位数
max = 2**(N-1)-1
min = - max - 1
if (num > max) or (num < min):
return False
else:
return True
def cplm(num,N): # 转为补码，返回含N个元素列表
n = N
r = 0
Rs = []
if num < 0:
num = 2**n+num
while num != 0:
r = num % 2
num //= 2
Rs = [r] + Rs
ans = (n-len(Rs))*[0] + Rs
return ans
def bin(num,N): # 转为补位二进制，返回含N个元素的列表
r = 0
Rs = []
while(num != 0):
r = num % 2
num //= 2
Rs = [r] + Rs
Rs = (N - len(Rs))*[0] + Rs
return Rs
#print(bin(10,8))
def adder(a,b,c): # 全加器
carry = (a and b) or (b and c) or (a and c)
sum = (a and b and c) or (a and (not b) and (not c))\
or ((not a) and b and (not c))\
or ((not a) and (not b) and c)
return int(carry), int(sum)
def add(X,Y): # 加法器
while len(X) < len(Y): X = [0] + X
while len(X) > len(Y): Y = [0] + Y
L = [];
carry = 0;
for i in range(len(X) - 1, -1, -1):
carry, sum = adder(X[i], Y[i], carry)
L = [sum] + L
return (carry, L)
def Mult(A,B,N): # A、B为列表化的补位二进制
S = []
for i in range(len(B)-1, -1, -1):
if B[i] == 1:
C, S = add(S,A)
if C == 1:
S = [C] + S
A = A + [0]
Ch = S[0:len(S)-N]
Rs = S[len(S)-N:len(S)]
return Rs
#N = 12
#A = bin(4,N)
#B = bin(512,N)
#print(A,'\n',B,'\n',Mult(A,B,N))
def bin_2_dec(L): # 二进制转为十进制
weight = 1
sum = 0
for i in range(len(L) - 1, -1, -1):
sum += L[i] * weight
weight *= 2
return sum
def solution(x,y,N):
A = bin(abs(x),N)
B = bin(abs(y),N)
M = Mult(A,B,N)
#print(M)
if not scale(x*y,N):
print("Overflow!")
else:
print((x*y)//(abs(x)*abs(y))*bin_2_dec(M))
solution(-12,100,12)
solution(-30,-10,12)
solution(4,-512,12)
solution(4,512,12)
solution(40,-80,12)
———————————————————————————————————————
#Programming Result:
-1200
300
-2048
Overflow!
Overflow!
# 1 8 23 / 符号位 指数 尾数
def dec2float(x):
print(x)
# 判断符号位
if x >= 0:
Si = [0]
else:
Si = [1]
x = abs(x)
# 分离小数部分和整数部分
integer = int(x)
decimal = x - integer
# print(integer, decimal)
# 算整数部分 存入In (Integer)
r = 0
In = []
while integer != 0:
r = integer % 2
integer //= 2
In = [r] + In
# 算小数部分 存入De (Decimal)
De = []
while decimal != 0:
decimal *= 2
De.append(1 if decimal >= 1. else 0)
decimal -= int(decimal)
if decimal == 0:
De.append(0)
# print(Si, In, De)
# 算指数部分 存入Ex (Exponent)
if 1 in In: # 当In中有元素，表示数字包含整数部分，指数为len(In)-1
exp = len(In) - 1
else: # 当In中无元素，表示数字不包含整数部分，指数为从De的第一个元素数起、直到出现1时的元素数目取相反数
for i in range(len(De)):
if De[i] != 0:
break
exp = -(i + 1)
De = De[i:] # 去掉De前导0
ex = exp
exp += 127 # 指数的偏移量
Ex = []
while exp != 0:
rr = exp % 2
exp //= 2
Ex = [rr] + Ex
if len(Ex) < 8:
Ex = (8-len(Ex)) * [0] + Ex
# 算尾数部分 存入Ma (Mantissa)
if len(In) - 1 > 23: # 尾数23位后直接舍去
Ma = In[1:24]
else:
if len(In) - 1 + len(De) < 23:
Ma = In[1:len(In)] + De + (23 - (len(In) - 1 + len(De))) * [0]
else:
Ma = In[1:len(In)] + De[:23 - len(In) - len(De)]
Ma = Ma + (23-len(Ma)) * [0]
# 对0特殊处理
if x == 0:
Si = [0]
Ex = 8 * [0]
Ma = 23 * [0]
# print(Si, ex, Ex, Ma)
Ans = Si + Ex + Ma
for i in range(0, len(Ans)):
print(Ans[i], end="")
print("\n")
dec2float(1)
dec2float(1.0)
dec2float(0)
dec2float(-1000.1)
dec2float(65535.125)
dec2float(65535.0125)
dec2float(0.000005)
dec2float(-0.00000000006)
dec2float(1234567)
dec2float(1234567890)
dec2float(1.000006)
dec2float(1.00000006)
———————————————————————————————————————
#Programming Result:
1
00111111100000000000000000000000
1.0
00111111100000000000000000000000
0
00000000000000000000000000000000
-1000.1
11000100011110100000011001100110
65535.125
01000111011111111111111100100000
65535.0125
01000111011111111111111100000010
5e-06
00110110110100111110001011010110
-6e-11
10101110110000011111100001111111
1234567
01001001100101101011010000111000
1234567890
01001110100100110010110000000101
1.000006
00111111100000000000000000110010
1.00000006
00111111100000000000000000000000
7. Py. IEEE 754 浮点数转化
32位
# 1 8 23 / 符号位 指数 尾数
def float2dec(x):
# 字符串转列表
X = list(x)
for i in range (len(X)):
X[i] = int(X[i])
# print(X)
# 分成 符号位Si - 指数Ex - 尾数De 三个部分
Si = X[0]
Ex = X[1:9]
De = X[9:]
# print(Si, Ex, De)
# 处理符号位
sign = 1
if Si == 1:
sign = -1
# 指数部分转十进制
weight = 1
ep_10 = 0
for i in range(len(Ex) - 1, -1, -1):
ep_10 += Ex[i] * weight
weight *= 2
ep_10 -= 127
# print(ep_10)
# 尾数部分转十进制
weight = 0.5
de_10 = 0
for j in range(len(De)):
de_10 += De[j] * weight
weight /= 2
# print(de_10)
ans = sign * (1 + de_10) * 2 ** ep_10
print(ans)
64位
# 1 11 52 / 符号位 指数 尾数
def dec2float(x):
print(x)
# 判断符号位
if x >= 0:
Si = [0]
else:
Si = [1]
x = abs(x)
# 分离小数部分和整数部分
integer = int(x)
decimal = x - integer
# print(integer, decimal)
# 算整数部分 存入In (Integer)
r = 0
In = []
while integer != 0:
r = integer % 2
integer //= 2
In = [r] + In
# 算小数部分 存入De (Decimal)
De = []
while decimal != 0:
decimal *= 2
De.append(1 if decimal >= 1. else 0)
decimal -= int(decimal)
if decimal == 0:
De.append(0)
# print(Si, In, De)
# 算指数部分 存入Ex (Exponent)
if 1 in In: # 当In中有元素，表示数字包含整数部分，指数为len(In)-1
exp = len(In) - 1
else: # 当In中无元素，表示数字不包含整数部分，指数为从De的第一个元素数起、直到出现1时的元素数目取相反数
for i in range(len(De)):
if De[i] != 0:
break
exp = -(i + 1)
De = De[i:] # 去掉De前导0
ex = exp
exp += 1023 # 指数的偏移量
Ex = []
while exp != 0:
rr = exp % 2
exp //= 2
Ex = [rr] + Ex
if len(Ex) < 11:
Ex = (11-len(Ex)) * [0] + Ex
# 算尾数部分 存入Ma (Mantissa)
if len(In) - 1 > 52: # 尾数52位后直接舍去
Ma = In[1:53]
else:
if len(In) - 1 + len(De) < 52:
Ma = In[1:len(In)] + De + (52 - (len(In) - 1 + len(De))) * [0]
else:
Ma = In[1:len(In)] + De[:52 - len(In) - len(De)]
Ma = Ma + (52-len(Ma)) * [0]
# 对0特殊处理
if x == 0:
Si = [0]
Ex = 11 * [0]
Ma = 52 * [0]
# print(Si, ex, Ex, Ma)
Ans = Si + Ex + Ma
for i in range(0, len(Ans)):
print(Ans[i], end="")
print("\n")
dec2float(65535.125)
———————————————————————————————————————
#Programming Result:
65535.125
0100000011101111111111111110010000000000000000000000000000000000
def float2dec(x):
# 字符串转列表
X = list(x)
for i in range (len(X)):
X[i] = int(X[i])
# print(X)
# 分成 符号位Si - 指数Ex - 尾数De 三个部分
Si = X[0]
Ex = X[1:12]
De = X[12:]
# print(Si, Ex, De)
# 处理符号位
sign = 1
if Si == 1:
sign = -1
# 指数部分转十进制
weight = 1
ep_10 = 0
for i in range(len(Ex) - 1, -1, -1):
ep_10 += Ex[i] * weight
weight *= 2
ep_10 -= 1023
# print(ep_10)
# 尾数部分转十进制
weight = 0.5
de_10 = 0
for j in range(len(De)):
de_10 += De[j] * weight
weight /= 2
# print(de_10)
ans = sign * (1 + de_10) * 2 ** ep_10
print(ans)