深入理解计算机系统(CSAPP) 实验1: DataLab

实验前,先做一系列的Linux命令行介绍(以后一定要好好学操作系统😭):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
clear 清空命令行

pwd 显示目录

cat 以文本文件的形式读取,但不能进行编辑

vi 打开一个文本,并进行编辑 按i进入插入模式 按:w 保存 :wq保存并退出


因为写了个脚本,所以使用./run.sh 代替 /btest
脚本里的内容为:
#/bin/bash
make clean
make
./btest
如果不使用脚本,每次更改bits.c内的函数后都要make clean 再make 才能使用./btest

实验平台:我好朋友推荐我使用了腾讯云的服务器,40一年,很便宜也很好用,强烈推荐(也可以使用Docker装虚拟机,但是我有轻度系统洁癖,不太想在MacOS里装其他操作系统)

1
购买链接:https://cloud.tencent.com/product/lighthouse

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/202203122152431.png

Lab 1 Data Lab

1.使用./btest跑一系列的data set来验证正确性

1
2
3
4
5
6
7
8
9
  Test all functions for correctness and print out error messages:
  unix> ./btest

  Test all functions in a compact form with no error messages:
  unix> ./btest -g

  Test function foo for correctness:
  unix> ./btest -f foo

2.使用./dlc(date lab check)来检测你的代码操作符等是否符合规定

1
2
./dlc bits.c    看目前使用的操作符是否合法,如果合法不返回任何信息
./dlc -e bits.c 看目前使用的操作符是否合法及目前使用的操作符号个数

这道题目的考点是;

1.异或门的逻辑表示

2.morgen law

1
2
3
int bitXor(int x, int y) {
  return ~((~((~x&y)))&(~(x&(~y))));
}
截屏2022-03-09 下午3.53.51

注意题目要求使用的整形范围在0~225

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

判断x是否为Tmax分为两步:

1.判断x+1+x是否为-1,如果是有且只有两种情况,x==Tmax 或者 x==-1

2.当x为-1时,就一定不是最大值,使用!!(~x),将这种情况排除在外。

1
2
3
int isTmax(int x) {
   return (!(~(x+x+1))) &(!!(~x));
}

x+1+x为什么为-1使用了有符号数加法的特性:

https://raw.githubusercontent.com/Nngxu/ImgHosting/main/202203122138042.png

截屏2022-03-09 下午3.54.37

判断x的奇数位上是否全为1

因为我们使用的int类型的数只能在0~255之间,所以使用对称性的原则生成0xAAAAAAAA

若有一个w=4的补码数,则判断奇数位是否全为1的方法是:

截屏2022-03-09 下午3.59.35
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int allOddBits(int x) {

  int A = 0xA;

  int AA = A<<4 | A;

  int AAAA = AA<<8 | AA;

  int AAAAAAAA = AAAA<<16 |AAAA;

  return !((AAAAAAAA & x)^AAAAAAAA);

}

求任意一个数的非

这是一个很重要的考点,我们之前在做练习的时候也无数次的遇到这个东西,一共用两种方法:

方法一: -x = ~x +1 见课本2.3.3小节

方法二:对最右边的1前面的数求补

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

如果0x30 <= x <= 0x39,就返回1。

解题思路:

1.判断的第一位的高四个字节是否为3

如果为3,返回0,并继续进行2.的判断

如果不为3,说明一定不是0x30~0x39之间的数,返回1,已经没有继续判断的必要

2.现在,判断低四位即可,我们知道0~9之间的数有以下特点:

(1)0~7之间的数第4位一定为0

(2)8、9两个数第2、3位一定为0

1
2
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1110 1111
  0    1    2    3    4    5    6    7    8    9   10   11  12    13

所以如果第4位为0,就判断结束,返回0

否则就判断第2、3两位是否都为0,如果为0返回0 否则返回1

3.我们目前的判断条件都是:0 ——符合条件

​ 1——不符合条件 可能要进行更深的判断

1
2
3
int isAsciiDigit(int x) {
  return !((((x>>4)^0x3))|(((x>>3)&0x1)&(!!(x&0x6))));
}

如果x不为0,就返回y 否则返回z <==> x ? y : z;

解题思路:

1.首先要拿出x是否为0的判断方法

这里我的思路是,当x为0就返回0 当x不为0就返回0xffffffff

当然最简单的是 (!x) - 1但是这题禁用了负号 而且也不能使用负的整形数(-1) 所以只能想其他方法

1
2
3
4
(~(!!x)): 此时x==0得到0xffffffff x!=0得到0xfffffffe
然后将其左移31 再右移31 x==0得到0xffffffff x!=0得到0x0
再取补得到x==0时返回0 x!=0时返回0xffffffff
 mask = ~(((~(!!x))<<31)>>31)

2.接下来就是如何使用mask来进行比较了

当x!=0时mask为0xffffffff,然后和y相与

当x==0时mask为0x0,取补然后和z相与

1
2
3
4
int conditional(int x, int y, int z) {
    int mask = ~(((~(!!x))<<31)>>31);
    return (mask&y)|((~(mask))&z);
}

解题思路:

主要思想:因为两个数(A、B)的比较有四种情况:(A、B都大于0)、(A、B都小于0)、(A大于0B小于0)、(A小于0B大于0)而后两种情况是可以直接知道它们之间的大小关系的,所以我的整体思路是先判断后两种情况,再去讨论前两种情况

(A大于0B小于0)、(A小于0B大于0):

(1)首先计算出X和Y符号位的掩码

1
2
    int mask_x = x>>31;
    int mask_y = y>>31;

(2)使用异或的方法判断两个数是否异号

若异号 返回1 若同好返回0

1
    int sign_judge = !(mask_x ^ (~mask_y));

(3)如果X、Y异号,看X的正负 若X为正说明Y一定为负 此时不满足情况返回0

​ 若X为负说明Y一定为正 此时满足X<=Y的情况返回1

如果X、Y同号,下式中的(sign_judge)直接让diff_sign为0

1
 int diff_sign = (sign_judge)&(x>>31 & 0x1);

(4)如果X、Y同号,看Y- X的正负,若为Y- X的符号位为0 说明Y>=X

(其实不用担心溢出的情况,因为当X、Y都大于0时,是不存在溢出情况都

当X、Y都小于0时,可能存在溢出情况,当X为TMin,但是此时Y无论为何值,都是满足条件的,且Y- TMin一定溢出且大于等于0)

如果X、Y异号,下式中的~(sign_judge)直接让same_sign为0

1
 int same_sign =(!(((y+(~x+1))>>31)&0x1))&(~(sign_judge));

(5)最后将两种情况|起来就ok啦

1
2
3
4
5
6
7
8
int isLessOrEqual(int x, int y) {
    int mask_x = x>>31;
    int mask_y = y>>31;
    int sign_judge = !(mask_x ^ (~mask_y));
    int diff_sign = (sign_judge)&(x>>31 & 0x1);
    int same_sign =(!(((y+(~x+1))>>31)&0x1))&(~(sign_judge));
    return    (diff_sign)|(same_sign);
}

使用简单的运算代替!

(1)使用之前学到的取某个数负数的方法 得到x的负数

1
int ne_x = ~x +1;

(2)如果x不为0 那么ne_x|x在第32位的位置上一定为1(包括x==TMin在内)

(3)然后将最高位的1挪到第一位 如果x为0 则挪动后为0 否则挪动后为0xffffffff

1
(ne_x|x)>>31)

(4)如果x为0 挪动后为0 加1 为1 否则0xffffffff 加1为0

1
2
3
4
int logicalNeg(int x) {
      int ne_x = ~x +1;
    return ((ne_x|x)>>31) +1;
}

解题思路:

(1)零

零毫无疑问,只需要一位即可表示

(2)正数

正数的补码表示只需要最高位的1 + 1位即可

1
2
3
比如:
0111 需要四位 因为补码中最高位为1表示负数
01   需要两位

(3) 负数

1
2
3
在2.2.6扩展一个位数时我们学过,补码的扩展有:
1111111100001  == 100001
因此,对于1111111100001需要6位在能表示

所以负数的表示需要找到最高位的0,然后在+1位即可。

为了统一正数和负数查找最高位的方法一致,我们将负数求补码,然后再查找最高位的1即可

1
1111111100001 = 0000000011110 需要5+1 6位才能表示

由此,我们使用下式来统一正数和负数

当x为正数时,flag == 0 、~flag = 0xffffffff : ((~flag)&x) == x 、(flag&(~x)) = 0

当x为负数时,flag == 0xffffffff、~flag = 0 : ((~flag)&x) == 0 、(flag&(~x)) = ~x

所以当x为正数时 x = x

​ 当x为负数时 x = ~x

1
2
int flag = x>>31;
x = ((~flag)&x) | (flag&(~x))

2.统一思想

通过对1的讨论,我们可以将x分为两类

当x为0的时候就返回1

当x不为0的时候就返回expr(expr为一个求x不为0时,x需要的补码位数的表达式)

1
	return (!!x) | expr

expr为一个(求x不为0时,x需要的补码位数)的表达式

(1)我们已经在上一步骤中将负数求最高位0转化为求正数最高位1来表示

1
2
int flag = x>>31;
x = ((~flag)&x) | (flag&(~x))

(2)求最高位1

求最高位1的方法理解比较困难,具体介绍入下所示,我尽量用简单的语言来表述此过程。

1.查看x的32位中,高16位中是否有1

我们知道int类型的数是由32位二进制数表示的,我们先查看高16位中是否存在1:

如果存在1,说明低16不用判断了,将高16位移动到低16位方便接下来的判断 并将16这个数字记下,表示目前x可能的位数+16

如果不存在1,说明高16位中没有1,那么判断低16位即可,将目前x可能的位数设置为0(因为高16位中没有1)

2.查看x的低16位的高8位是否有1

上一步骤中,如果高16位中有1,我们已经将它挪动到了低16位,如果没有直接判断低16位 的高8位 即可:

如果存在1,说明低8不用判断了,将高8位移动到低8位方便接下来的判断 并将8这个数字记下,表示目前x可能的位数+8

如果不存在1,说明高8位中没有1,那么判断低8位即可,将目前x可能的位数设置为0(因为高8位中没有1)

3.查看x的低8位的高4位是否有1

上一步骤中,如果高8位中有1,我们已经将它挪动到了低8位,如果没有直接判断低8位 的高4位 即可:

如果存在1,说明低4不用判断了,将高4位移动到低4位方便接下来的判断 并将4这个数字记下,表示目前x可能的位数+4

如果不存在1,说明高4位中没有1,那么判断低4位即可,将目前x可能的位数设置为0(因为高4位中没有1)

4.查看x的低4位的高2位是否有1

上一步骤中,如果高4位中有1,我们已经将它挪动到了低4位,如果没有直接判断低4位 的高2位 即可:

如果存在1,说明低2不用判断了,将高2位移动到低2位方便接下来的判断 并将2这个数字记下,表示目前x可能的位数+2

如果不存在1,说明高2位中没有1,那么判断低2位即可,将目前x可能的位数设置为0(因为高2位中没有1)

5.查看x的低2位的高1位是否有1

上一步骤中,如果高2位中有1,我们已经将它挪动到了低2位,如果没有直接判断低2位 的高1位 即可:

如果存在1,说明低1不用判断了,将高1位移动到低1位方便接下来的判断 并将1这个数字记下,表示目前x可能的位数+1

如果不存在1,说明高1位中没有1,那么判断低1位即可,将目前x可能的位数设置为0(因为高1位中没有1)

最后,看最后一位中是否有1,如果有1,将x可能的位数直接+1, 如果没有1,直接+0即可。

 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
int howManyBits(int x) {
    int flag = x>>31;

    x = (flag&(~x))|((~flag)&x);

    //判断32位中的高16位
    int bits_16 = (!!(x>>16))<<4;
    x = x>>bits_16;

    //判断低16位中的高8位
    int bits_8 = (!!(x>>8))<<3;
    x = x>>bits_8;

    //判断低8位中的高4位
    int bits_4 = (!!(x>>4))<<2;
    x = x>> bits_4;

    //判断低4位中的高2位
    int bits_2 = (!!(x>>2))<<1;
    x = x>> bits_2;

    //判断低2位中的高1位
    int bits_1 = (!!(x>>1));
    x = x>>bits_1;
    //当上一步骤为01时 bits_1为0 此时需要再进行判断最低为是否为1还是0
    //当上一步骤为11时,bits_1为1 表示此时低1位不用判断 因为第2位为1了 还需要再判断
    int bits_0 = x;
    int expr = bits_16+bits_8+bits_4+bits_2+bits_1+bits_0 + 1;
    printf("%d",expr);
    return expr;
}

当x为0时,下式为0;

0经过2.expr步骤后算出expr也为1,所以x为1的情况不需要单独考虑。

1
x = ((~flag)&x) | (flag&(~x))

其实这道题和课本上习题2.94一模一样,大家有空可以去看我博客第二章习题的解释。

唯一要提醒的两个点就是:

1.frac也是一个32位的类型 所以当f_-1位为1 且 此时uf为一个Denormalized的时候 左移一位真的很巧妙 一箭双雕

让Denormalized变为了Normalized 还从uf –> 2uf

2.求uf放大两倍的时候 在Denormalized 到 Normalized的过渡是平滑过渡

求uf一半到时候 从Normalized 到 Denormalized的过渡要rounding to even (具体看我第二章homework的讲解_2.95)

 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
unsigned floatScale2(unsigned uf) {
    unsigned frac,exp,sign;
    frac = uf & 0x7fffff;
    //提取exponent field
    exp = uf>>23&0xff;
    //提取符号位
    sign = uf >>31;

    //如果是NaN(exp == 0xff且frac!=0 用位操作表示为) 就直接返回
    if((!(exp^0xFF))&frac)
    {
        return uf;
    }
    //如果为Denormalized exp == 0
    else if(!exp)
    {
        //这里要注意frac可以左移到第23为(从0位开始记数)
        frac= frac<<1;
    }
    //为无穷大时 不做任何处理 但是不能让它进下面的else exp == 0xff
    else if(!(exp^0xff))
    {

    }
    //如果为Normalized
    else
    {
        //如果exp为1111 1110 exp == 0xfe 
        if(!(exp^0xfe))
        {
            frac = 0;
            exp = 0xff;
        }
        //是正常的Normalized
        else
        {
            exp +=1;
        }
    }
        //再组合
    return exp<<23|frac|sign<<31;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/* 
 * floatFloat2Int - Return bit-level equivalent of exprepssion (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  return 2;
}

本题和课本上练习题2.96一摸一样,所以有不懂的可以去看我直接在第二章联系题中的解释,这里就只给出解题的代码。

另外,这题要注意的点如下:

1.对sign fraction为1 E为31时 fraction field为全0的巧妙处理

2.记住在整数补码的表示中,负数永远可以表示的范围比整数大1 因为TMax + 1 = TMin

3.在做这个题的时候,我发现用== !=等判断是没问题的,但是为了统一题目前的要求,我还是将所有的比较运算都使用了位级表示。

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
float u2f(unsigned f)
{
    return *((float *)&f);
}

unsigned f2u(float f)
{
    return *((unsigned*)&f);
}

int floatFloat2Int(unsigned uf) {

    //提取sign filed
    int sign = uf >> 31 & 0x1;
    //如果是负数返回-1 正数返回1 可以使用lab
//    int s = sign == 1 ? -1 : 1;
   int s = (((sign^0x1) -1)& (-1))|((~((sign^0x1)-1))&(1));
    //提取exponent field
    int exp = uf >> 23 & 0xff;
    //提取friction field
    int frac = uf & 0x7fffff;
    int bias = 127;
    int E = exp -bias;

    int F;
//    printf("%d\n",E);
    //如果是无符号数 E一定是-126 rounding to zero后一定为0
    //如果是signed 当E = e -127 <0 时 rounding to zero 后一定为0
    if(E<0)
    {
        return 0;
    }
    //当E>=31时,float类型的正数无法表示 因为当E为31时 1f_-1....f_-2300000000(共32位) int类型的正数无法表示
    //而int类型的负数表示的范围仅仅是比int类型的正数的范围多1 所以0x80000000可以用int类型的负数表示
    //综上所属 我们可以将E>=31时返回的条件都设置为return 0x80000000
    //这样即满足了f不能用int类型表示时返回0x80000000的要求 也满足了当float类型的sign为1 E为31 fraction field为全零时 返回0x80000000的要求
    //E = e -bias >=  31 <==> e >= 158
    //将E >= 31 换为 !((E-30)>>31)
    else if(!((E-30)>>31))
    {
        return 0x80000000;
    }
    //现在E的范围是 0=<E <31
    else
    {
        //F为 1f_-1....f_-23
        F  = (1<<23) + frac ;
        //当E>=23 则不需要rounding
        //将E >=23换为!(E-22)>>31
        if(!(E-22)>>31)
        {
            F = F<<(E - 23);
        }
        //当E<23时 可能需要rounding to zero
        else
        {
            F = F>>(23 -E);
            printf("!!!%d\n",F);
        }
    }
    //如果float是负数 则还要将int转化为负数
    return F*s;
}

本题和课本上练习题 2.90一摸一样,所以就不在这里进行仔细说明。

只是说明一个需要注意的地方,在写完最后一题后,用./btest命令通过数据集对程序进行检查时,可能会报以下错误:

1
2
3
ERROR: Test floatPower2 failed.
  Timed out after 10 secs (probably infinite loop)
Total points: 32/36
截屏2022-03-12 下午7.03.35

一种可能性就是你的程序里存在死循环,但是对于这个题来说,几乎没有人会写出循环,所以最大的可能性时你的电脑性能问题,导致10s内无法检测完数据集,因此报错。

解决方法:使用 vi /btest.c命令进入检测代码,调大检测时间的宏定义,将10s调大。

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/202203122158507.png

实现代码为:(详细过程看我第二章的习题解答)

 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
unsigned floatPower2(int x) {
       int exp;
    int frac;
    if(x<-149)
    {
        return 0;
    }
    else if(x<-126)
    {
        exp = 0 ;
        frac = 1<<(23+(x+126));
        return frac;

    }
    else if(x<128)
    {
        exp = x+127;
        frac = 0 ;
        return exp<<23;
    }
    else
    {
        exp = 0xff;
        frac = 0;
        return exp<<23;
    }
}

参考资料:

1
https://www.bilibili.com/video/BV183411k7VM?from=search&seid=8473774189499121384&spm_id_from=333.337.0.0