深入理解计算机系统（CSAPP）实验1： DataLab

Ningxu included in category CSAPP

2022-03-12 2022-03-12 6147 words 13 minutes

Contents

实验前，先做一系列的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

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.BitXor

这道题目的考点是；

1.异或门的逻辑表示

2.morgen law

1
2
3


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

2.tmi

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

1
2
3


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

3.isTmax

判断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使用了有符号数加法的特性：

4.allOddbits

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

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

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

 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);

}

5.negate

求任意一个数的非

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

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

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

1
2
3


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

6. isAsciiDigit

如果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))));
}

7.conditional

如果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);
}

8.isLessOrEqual

解题思路：

主要思想：因为两个数（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);
}

9.logicalNeg

使用简单的运算代替！

（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;
}

10.howManyBits

解题思路：

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

2.求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;
}

3.0的情况再考虑

当x为0时，下式为0；

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

1

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

11.floatScale2

其实这道题和课本上习题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;
}

12.floatFloat2Int

 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;
}

13.floatPower2

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

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

1
2
3


ERROR: Test floatPower2 failed.
  Timed out after 10 secs (probably infinite loop)
Total points: 32/36

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

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

实现代码为：（详细过程看我第二章的习题解答）

 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

Contents

深入理解计算机系统（CSAPP） 实验1： DataLab

Lab 1 Data Lab

1.BitXor

2.tmi

3.isTmax

4.allOddbits

5.negate

6. isAsciiDigit

7.conditional

8.isLessOrEqual

9.logicalNeg

10.howManyBits

1.分清楚正数、负数和零在补码表示时的不同而产出的位数的不同

2.求expr

3.0的情况再考虑

11.floatScale2

12.floatFloat2Int

13.floatPower2

深入理解计算机系统（CSAPP）实验1： DataLab