CMU 15-213 Lab1 Data Lab

课程主页:http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料:https://github.com/EugeneLiu/translationCSAPP

课程视频:https://www.bilibili.com/video/av31289365/

这一部分回顾CSAPP的Data Lab。

bitXor

$x$ $y$ $x\text{^}y$
1 1 0
1 0 1
0 1 1
0 0 0

不难看出

代码如下

1
2
3
int bitXor(int x, int y) {
return ~((~((~x) & y)) & (~((~y) & x)));
}

tmin

代码如下

1
2
3
4
int tmin(void) {
int x = (1 << 31);
return x;
}

isTmax

首先给出如下结论,只有当且仅当

才成立

证明:

假设

那么

另一方面

所以

等价于(其中$k\in \mathbb Z$)

利用二进制数表示的唯一性可得

有了如下结论,可以先利用如下代码判断x是否为-1或$\text{Tmax}$:

1
2
3
4
//判断是否为xffffffff或Tmax,如果成立,则y3为0
int y1 = x + 1;
int y2 = ~x;
int y3 = (y1 ^ y2);

接着要排除-1的情形,这一点只要利用-1的表示为全1即可

1
2
3
4
//判断是否为0xffffffff,如果成立,则z2为1
//如果x为0xffffffff,则z1为0
int z1 = ~x;
int z2 = !z1;

最后进行简单的操作即可,完整的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int isTmax(int x) {
//判断是否为xffffffff或Tmax,如果成立,则y3为0
int y1 = x + 1;
int y2 = ~x;
int y3 = (y1 ^ y2);

//判断是否为0xffffffff,如果成立,则z2为1
//如果x为0xffffffff,则z1为0
int z1 = ~x;
int z2 = !z1;

//生成结果,如果x为Tmax则r=False,所以要取非
int r = (z2 | y3);
r = !r;

return r;
}

allOddBits

设置mask:0101,0101,…,0101,然后将x与其做异或运算,最后取非即可,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int allOddBits(int x) {
//0101,0101
int y1 = 170;
//0101,0101,0101,0101
int y2 = (y1 << 8) + y1;
//0101,0101,0101,0101,0101,0101,0101,0101
int y3 = (y2 << 16) + y2;
//取交集
int y4 = (x & y3);
//判断是否相同
int y5 = (y4 ^ y3);

return !y5;
}

negate

利用第三讲的内容可知

代码如下

1
2
3
int negate(int x) {
return (~x) + 1;
}

isAsciiDigit

分为两部分,第一部分判断4到7位(从右往左数)是否为0011,只要利用移位运算和异或运算即可:

1
int y1 = !((x >> 4) ^ 3);

第二部分判断0到3位,注意第0位是没有影响的,所以只要判断其他几位是否为1即可:

1
2
3
4
5
6
7
//判断末4位范围
//判断第3位是否为1
int y2 = (x & 8) >> 3;
//判断第2位是否为1
int y3 = (x & 4) >> 2;
//判断第1位是否为1
int y4 = (x & 2) >> 1;

另外不难发现如果第3位为1,则1,2位应该必然为0;如果第3位为0,则其他位置可取任意值,所以初步的代码为

1
2
3
int z1 = y1 & (!y2);
int z2 = y1 & y2 & (!y3) & (!y4);
int z3 = z1 | z2;

但是这样会超过运算数限制,所以要对上述操作进行优化,首先不难看出y1可以提取出来,另一方面,

所以

最终得到如下代码

1
2
3
int z1 = (!y3) & (!y4);
int z2 = !y2;
int z3 = y1 & (z1 | z2);

完整的部分如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int isAsciiDigit(int x) {
//范围为0011,0000到0011,1001
//判断0011部分是否相同
int y1 = !((x >> 4) ^ 3);
//判断第3位是否为1
int y2 = (x & 8) >> 3;
//判断第2位是否为1
int y3 = (x & 4) >> 2;
//判断第1位是否为1
int y4 = (x & 2) >> 1;
//如下代码会超过运算数限制
//int z1 = y1 & (!y2);
//int z2 = y1 & y2 & (!y3) & (!y4);
//int z3 = z1 | z2;
int z1 = (!y3) & (!y4);
int z2 = !y2;
int z3 = y1 & (z1 | z2);

return z3;
}

conditional

首先考虑一比特的情形,不难发现输出结果可以用如下操作完成:

多个比特的情形类似,只要构造mask即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int conditional(int x, int y, int z) {
//声明变量
int flag, notflag, a, b, c;
//将x转换为0或1,x为0的时候转换为1,其余情形为0
flag = (!x);
//取反转换为1110,1111,x为0的时候转换为1110,其余情形为1111
flag = ~flag;
//加1转换为1111,0000,x为0的时候转换为1111,其余情形为0000
flag = flag + 1;
//取反
notflag = ~flag;
//生成结果
a = notflag & y;
b = flag & z;
c = (a | b);

return c;
}

isLessOrEqual

首先判断符号位,如果符号位不同则可以直接产生结果;如果符号位相同,这时候做减法,注意此时必然不会溢出,所以减法有效,利用之前的negate方法即可完成这一步,最终将两种情形的结果合并即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int isLessOrEqual(int x, int y) {
int minusx, y_x, r, r0, r1, r2, mask, sx, sy;
//判断两数是否相同,相同为1,否则为0
r0 = !(x ^ y);
//模板,1000
mask = (1 << 31);
//符号位,如果为1则为0,否则为1
sx = !(x & mask);
sy = !(y & mask);
//判断符号位是否相同,如果相同返回1,否则返回0
r1 = !(sy ^ sx);
//计算-x
minusx = ~x;
minusx = minusx + 1;
//计算y-x,注意可能溢出
y_x = y + minusx;
//判断符号位是否为1,如果y >= x,则y_x为全0,否则为全1
y_x = y_x >> 31;
//生成结果
r2 = !y_x;
//如果r1=1,则返回r2;否则如果r0=1,则返回r0,其余情况返回sy
r = ((r1) & r2) | ((~r1) & (r0 | ((~r0) & sy)));

return r;
}

logicalNeg

分两种情形讨论,如果$x<0$,则返回$0$;如果$x\ge 0$,则将其转换为$-x$,然后对$-x$使用之前的判断即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int logicalNeg(int x) {
int r1, r2, r, minusx;
//首先判断符号位,生成1000,0000
r1 = x & (1 << 31);
//右移,生成1111,0000
r1 = (r1 >> 31);
//生成1,0,如果x<0则r1=1,否则r1=0
r1 = r1 & 1;

//接着判断x>=0的情形,利用-x<=0
minusx = (~x) + 1;
//和之前一样判断符号位,如果x>0则r2=1,如果x=0则r2=0
r2 = minusx & (1 << 31);
r2 = (r2 >> 31);
r2 = r2 & 1;

//生成结果
r = r1 | r2;
r = r ^ 1;
return r;
}

howManyBits

这题比较难,参考了网上的资料:https://www.cnblogs.com/ustca/p/11740382.html#12%E3%80%81howmanybits

首先考虑何时可以减少比特数,分两种情况讨论:

如果$x<0$,注意到有如下事实

假设

那么可以得到对应的$k+1$位表达

所以只需要$k+1$比特(注意需要额外的符号位)即可,最关键的一步是找到从左往右数第一个$0$的位置。

如果$x\ge 0$,显然只要忽略前导$0$即可,假设

那么同样可以得到对应的$k+1$位表达

所以仍然只需要$k+1$比特(注意需要额外的符号位)即可,最关键的一步是找到从左往右数第一个$0$的位置。

为了方便起见,对于负数$x$,我们考虑$\tilde x $,即对于负数

考虑

这一步可以由如下方式完成:

1
2
3
mask = (x & (1 << 31)) >> 31;
//负数则对其二进制取反,保证x为正数;如果s=1,那么mask=1111,x=~x;
x = ((~mask) & x) | (mask & (~x));

所以后面的讨论中我们均考虑$x\ge0$的情形。

现在我们目标转换为找到$x$的二进制表达式中最靠左侧的$1$的位置$k$(假设下标从$1$开始),最终返回$k+1$即可,注意这里有操作数限制,所以应该使用二分查找。

首先考虑前16位,将$x$右移16位得到$x_1$,然后判断$x_1$的二进制表达式中是否含有$1$,得到$c_1$,如果$c_1=1$,那么我们需要考虑$x$的高16位,所以$x$应该右移$16$位,否则只要考虑$x$的低16位,不要需要右移即可,这一步可以由如下代码完成:

1
2
3
4
5
//判断前16位是否有1
c1 = !(!(x >> 16));
//如果c1=1则m1=16,否则为0
m1 = (c1 << 4);
x = x >> m1;

其余部分同理,完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int howManyBits(int x) {
int mask, m1, m2, m3, m4, m5, m6, c1, c2, c3, c4, c5, c6, res;
mask = (x & (1 << 31)) >> 31;
//负数则对其二进制取反,保证x为正数;如果s=1,那么mask=1111,x=~x;
x = ((~mask) & x) | (mask & (~x));
//利用二分查找找到第一个1的位置
res = 0;
//判断前16位是否有1
c1 = !(!(x >> 16));
//如果c1=1则m1=16,否则为0
m1 = (c1 << 4);
x = x >> m1;
//同理判断剩余部分
c2 = !(!(x >> 8));
m2 = (c2 << 3);
x = x >> m2;

c3 = !(!(x >> 4));
m3 = (c3 << 2);
x = x >> m3;

c4 = !(!(x >> 2));
m4 = (c4 << 1);
x = x >> m4;

c5 = !(!(x >> 1));
m5 = (c5 << 1);
x = x >> m5;

//最后一位特殊处理
c6 = x & 1;
m6 = c6;

//注意要增加1
res = m1 + m2 + m3 + m4 + m5 + m6 + 1;

return res;
}

floatScale2

回顾浮点数的数值表示:

以及比特形式:

首先提取上述三个部分:

1
2
3
4
5
6
7
8
9
10
11
unsigned r;
int s, exp, frac, mask1, mask2, a;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);

然后根据exp的值分情形判断。

情形1,exp全1,则根据要求输出uf:

1
2
3
4
if (exp == mask1){
//nan,无穷大
r = uf;
}

情形2,exp全0,这种情况为非规格的浮点数,此时要对frac左移1位(乘2),然后判断frac最高位是否为1,如果为$1$,则将exp增加1,注意此时为转变为规格的情形,frac部分解释为1.xxxx2,所以frac部分无需处理,代码如下:

1
2
3
4
5
6
7
8
9
10
else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}

然后判断frac最高位为1的情形相对复杂,需要看一个具体例子,以8位浮点数为例,假设浮点数为

注意此浮点数(非规格情形)为

按照上述代码生成的结果为

注意此时为规格情形,$M=1$,所以该浮点数的值为

情形3,exp不是全0也不是全1,这种情形比较简单,直接让exp加1即可:

1
2
3
4
5
6
7
8
9
10
else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}

完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unsigned floatScale2(unsigned uf) {
unsigned r;
int s, exp, frac, mask1, mask2, a;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);
if (exp == mask1){
//nan,无穷大
r = uf;
}else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}else{
exp = exp + 1;
r = (s << 31) | (exp << 23) | frac;
}

return r;
}

floatFloat2Int

第一步和上一题一样,提取s,exp,frac部分:

1
2
3
4
5
6
7
8
9
10
11
int r, s, exp, E, frac, mask1, mask2, ofr;
ofr = 0x80000000u;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);

然后根据exp的值分情形判断。

情形1,exp全1,输出ofr:

1
2
3
4
if (exp == mask1){
//nan,无穷大
r = ofr;
}

情形2,exp全0,这种情况的结果为$\pm 0.f_1f_2\ldots$,所以无论正负,均舍入到$0$:

1
2
3
4
else if (exp == 0){
//非规格
r = 0;
}

情形3,exp不是全0也不是全1,首先计算$M\times 2^{23}$,注意这里要增加一个前置的1;然后计算实际的E,调整指数即可,这里要考虑溢出的情形;最后根据符号调整结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
else{
//当前结果为M*2^23
//规格情形需要增加前置1
r = (1 << 23) | frac;
//实际结果为M*2^E
E = exp - 127;
if (E > 23){
while (E > 23){
E--;
r = r << 1;
if (r < 0){
r = ofr;
break;
}
}
}else{
while (E < 23){
E++;
r = r >> 1;
}
}
if (s == 1 && r != ofr){
r = -r;
}
}

完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int floatFloat2Int(unsigned uf) {
int r, s, exp, E, frac, mask1, mask2, ofr;
ofr = 0x80000000u;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);
//判断
if (exp == mask1){
//nan,无穷大
r = ofr;
}else if (exp == 0){
//非规格
r = 0;
}else{
//当前结果为M*2^23
//规格情形需要增加前置1
r = (1 << 23) | frac;
//实际结果为M*2^E
E = exp - 127;
if (E > 23){
while (E > 23){
E--;
r = r << 1;
if (r < 0){
r = ofr;
break;
}
}
}else{
while (E < 23){
E++;
r = r >> 1;
}
}
if (s == 1 && r != ofr){
r = -r;
}
}

return r;
}

floatPower2

注意我们只要计算exp部分即可,其余部分全置为$0$,首先计算exp:

1
2
//计算exp
exp = x + 127;

注意exp的范围为0到255,范围之外要特殊处理,完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned floatPower2(int x) {
int exp;
unsigned r;
//计算exp
exp = x + 127;
if (exp < 0){
r = 0;
}else if (exp > 255){
r = 0x7f800000;
}else{
r = exp << 23;
}

return r;
}

本文标题:CMU 15-213 Lab1 Data Lab

文章作者:Doraemonzzz

发布时间:2020年05月14日 - 11:49:00

最后更新:2020年05月14日 - 11:51:26

原始链接:http://doraemonzzz.com/2020/05/14/CMU 15-213 Lab1 Data Lab/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。