csapp---datalab 总结

2024-01-24 10:44:01

1.引言：

  很早就耳闻csapp的大名，这学期刚好学到计组，就连顺着拜读了一下经典的csapp。不得不说，刚读完第二章就不由得感慨，不愧是神书。
  自我感觉，学校学的计组主要侧重于硬件方面，太过于底层，而csapp则是从代码的角度来解释底层的运转，不需要掌握什么三态门、什么选择器等等，更加通俗易懂。不过掌握基本的硬件对以后也是有帮助的，所以计组和csapp双修才是王道（笑）。
   看完第二章就迫不及待的做了datalab，怎么说呢，刚开始的linux环境调试就费了我好大功夫，之前也没接触过，从网上搜了好多教程。怎么说呢，反正就是用linux终端的时候，终端显示错误，说你没有下载什么什么的时候，一般就跟着那个提示用install adp-get XX（root前提）就行了，之前就行需要用make命令，然后终端提示没有make，需要install。
  之后就正式进入到做lab的时间了。

NO.1 bitXor - x^y using only ~ and &

  • Example: bitXor(4, 5) = 1
  • Legal ops: ~ &
  • Max ops: 14
  • Rating: 1
int bitXor(int x, int y) {
  return ~(~(~x&y)&~(x&~y));

  这题就是很简单的实现异或运算，学过数电的基本就是so easy。我是用x^y=（x&y）|（x&y）；因为没有‘|‘，所以再左右两边同时位取反两次，就可以得到只存在&和~的表达式了。

NO.2 tmin - return minimum two’s complement integer

  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 4
  • Rating: 1
int tmin(void) {
    return 1<<31;
}

  这题就是很简单的求补码的最小值，32位的补码表示的范围是-2^31 ~ 2^31-1,所以此时的最小值就是最高位为1，后面都是0，只需要将1左移31位即可。

NO.3 isTmax - returns 1 if x is the maximum, two’s complement number,and 0 otherwise

  • Legal ops: ! ~ & ^ | +
  • Max ops: 10
  • Rating: 1
int isTmax(int x) {
    int y = x+1;
    return !(~(x^y)|!y);
}

  其实这个函数就是判断x是否为0x7fffffff，这类的题目也就是不断的尝试，不断的错误，然后不断的改正…，所以我们可以很自然的想到（当然在做的时候并不自然…）先把x加上1，加上1后就变成了0x80000000，这样是不是就舒服点了？…然后去观察。
  我们这个题目要做到的就是通过一个表达式，使得当x=0x7fffffff时为最特殊的一种情况，这种情况所得的值为1。我们应该可以想到把x和y进行异或，这样就得到全是1的二进制数了，之后自然的位取反得到0，而其他数位取反肯定不为零。所以在最前面加上一个逻辑非就能实现在x为0x7fffffff返回1，其他情况返回0。然后你欣喜的去./btest，发现错误…，原因是这类特殊情况有两种可能，还有一种是当x全为1时，x和y异或也是全为1，故只需要把这种情况排除在外就可以了。那怎么排除呢，就是找这两种情况的不同点，可以发现当x全为1时，y是0，所以只需要在~（x^y）后面“|”上一个‘！y’，当y为0时，说明应该返回0。完美解决。
   其实也就是在不断的错误不断的尝试中成功的。
下面是废话可以不看：
  当时做完一个题就在onenote里面做一下笔记来着…
  一个菜鸡在做这题的心路历程：
csapp---datalab 总结

NO.4 allOddBits - return 1 if all odd-numbered bits in word set to 1 where bits are numbered from 0 (least significant) to 31 (most significant)

  • Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 2
int allOddBits(int x) {
    int y=0xaa+(0xaa<<8);
    int z=y+(y<<16);
    return !((z&x)^z);
}

  此题就是判断32位的二进制数的奇数位是否全为1，如果全为1，则返回1，否则返回0。
  其实思路很简单，就是得到一个32位的奇数位全为1，偶数位全为0的数z，然后再和给定的x进行“&”操作，然后再和z异或。如果x满足条件，得到z^z-为零，否则最终结果必然不为零。最后的逻辑非能使得满足条件返回1，不满足返回0。
  注：但我本人在做这道题的时候根本没想到这样做，我一直沉浸在用左移后移来比较。把interge的题目除去最后一题都做完了又想了很久还是没想出来的情况下，去网上搜了，结果发现真的就是没有想到点子上咋都不行，找到那个点了其实非常简单。

NO.5 negate - return -x

  • Example: negate(1) = -1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 5
  • Rating: 2
int negate(int x) {
    return ~x+1;
}

  这题无须多说，基本上大家都学过数电，没学过的也应该知道补码的相反数等于它本身位取反然后再加一。

NO.6 isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)

  • Example: isAsciiDigit(0x35) = 1.
  • isAsciiDigit(0x3a) = 0.
  • isAsciiDigit(0x05) = 0.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 3
int isAsciiDigit(int x) {
    int y=3,z=0xf,p=6;
    return !(((x>>4)^y)|((x&z)+p)>>4);  // ((x>>4)^y)判断x的5-8位是否为0011，((x&z)+p)>>4判断x的1-4是否在数字0-9范围内。
}

csapp---datalab 总结

NO.7 conditional - same as x ? y : z

  • Example: conditional(2,4,5) = 4
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 16
  • Rating: 3
int conditional(int x, int y, int z) {
    return ((x>>31|((~x+1)>>31))&y)|(~(x>>31|((~x+1)>>31))&z);
}

 首先确定共有几种情况：
1.当符号位为1的时候，非零，返回y
2.当符号位为0的时候，当x为0x0时，为零，返回z
3.当符号位为0时，当x不为0x0时，非零，返回y
  此题是当通过判断x是否为0，最终决定返回y还是z。所以最终形式类似这样 ：（表达式1和y的运算）运算（表达式2和z的运算）。
  表达式1的目的是完成处理1和3的情况，表达式2的目的是完成处理2的情况。

分工明确后，首先完成表达式1:
  当符号位为1的时候，可以通过将x>>31,最终得到0xffffffff，可以和符号位0的情况区分开来。
  当符号位为0的时候，这里只需要把x为零和非零的情况区分开来，将为零的部分取反然后加一仍然得到0（你问我咋想到的，嗯…我想想，就是尝试，疯狂尝试，丧心病狂的尝试），而把非零的部分取反加一就得到负数，然后再重复符号位为1时候的操作。（~x+1）>>31，这样当x为0得到0，x非零得到0xffffffff。
  可知只有当“x>>31”或“（~x+1）>>31”为0xffffffff的时候，才返回y。所以可以把这两个表达式用‘|’运算符连接在一起，然后最后得到的表达式再和y进行‘&’操作，完成返回y。
表达式1：（x>>31 |（（~x+1）>>31））

其次是完成表达式2:
  这种情况是当符号位为0，且x为零的情况。由表达式1可以知道，当x为0时，表达式1为0，所以可以确定表达式1和2是通过‘|’进行连接的。其实表达式2的书写很简单，之前我们提到了，当x为0的时候，表达式1为0，所以在表达式二的书写中，我们只需要在表达式1的前提上位取反就可以。
  所以表达式2：~（x>>31 |（（~x+1）>>31）)
  最终表达式1和y进行‘&’运算，表达式2和z进行‘&’运算，最终得到的结果再进行 ‘|’运算即可。
下面可以不看：
这是我在刚做完这道题的时候记的笔记：
csapp---datalab 总结

NO.8 isLessOrEqual - if x <= y then return 1, else return 0

  • Example: isLessOrEqual(4,5) = 1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 24
  • Rating: 3
int isLessOrEqual(int x, int y) {
      return !!((x>>31)&(~y>>31))|(!!((x+(~y+1))>>31)&~((~x>>31)&y>>31))|!(x+(~y+1));
}

  这里我把之前做的笔记修改了一下，更加通俗易懂。
csapp---datalab 总结csapp---datalab 总结

csapp---datalab 总结
csapp---datalab 总结

No.9 logicalNeg - implement the ! operator, using all of the legal operators except !

  • Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
  • Legal ops: ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 4
int logicalNeg(int x) {
    return ~(x>>31)&(((~x+1)>>31)+1);
}

csapp---datalab 总结

NO.10 howManyBits - return the minimum number of bits required to represent x in two’s complement

  • Examples: howManyBits(12) = 5
  • howManyBits(298) = 10
  • howManyBits(-5) = 4
  • howManyBits(0) = 1
  • howManyBits(-1) = 1
  • howManyBits(0x80000000) = 32
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 90
  • Rating: 4
int howManyBits(int x) {
    int a16,a8,a4,a2,a1,a0;
    int sign=x>>31;
    x=(~sign&x)|(sign&~x);
    a16=!!(x>>16)<<4;
    x=x>>a16;
    a8=!!(x>>8)<<3;
    x=x>>a8;
    a4=!!(x>>4)<<2;
    x=x>>a4;
    a2=!!(x>>2)<<1;
    x=x>>a2;
    a1=!!(x>>1)；
    x=x>>a1;
    a0=x;
    return a16+a8+a4+a2+a1+a0+1;
}

  此题我并没有自己独立想出来，而是参考了网上的答案。看完之后不禁大呼，真吉尔巧妙。那我就简单阐述以下这些代码的思路。
  需要返回的是补码的最小组成位数，首先明确一点，符号位也占一位的组成位数的。
然后就是当补码为正的时候，只需要找到最高位的1，然后再加上1（符号位）就是最小的组成位数了。
  当补码为负的时候，应该是找到最高位的0，然后也是再加上1（符号位）即可。原因可以参考补码的位数扩充，如16位补码-》32位补码，当补码符号位为1的时候，往高16位全补1，以保持补码数值不变，具体可自己证明。
  然后再看代码，它很巧妙的把正负补码联系到一起，因为正补码找最大的1，而负补码找最大的0，所以只需要符号位为0的时候得到x，符号位为1的时候得到~x即可。也是异或的思想。
  然后就是判断高16位是否存在1，如果存在1，则说明x至少需要16位来表示，所以记下此时的位数：a16。然后将x右移16位（经过变形后，x的符号位是0），继续判断下面的16位，然后类似的进行处理，判断下面的8位、4位、2位、1位，最终将所有的加在一起然后再加1（符号位）就得到了最终的最小表示位数。
  想到这个确实很不容易，唉，说到底菜是原罪。

下面正式进入到浮点数的题目，不得不说因为对浮点数的限制放宽了很多，所以在做起来比整数的题目简单了好多（最起码能用if语句了…if语句yyds！），但是需要对浮点数的表示很熟悉。做完下面3题后，明显感觉对浮点数的理解更深刻了。

NO.11 floatScale2 - Return bit-level equivalent of expression 2*f for floating point argument f.

Request：Both the argument and result are passed as unsigned int’s, but they are to be interpreted as the bit-level representation of single-precision floating point values.When argument is NaN, return argument

  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4
unsigned floatScale2(unsigned uf) {
    if((uf>=0x7f800000 && uf<=0x7fffffff)||(uf>=0xff800000 && uf<=0xffffffff) || uf==0 || uf==0x80000000)
        return uf;  //当uf=NAN或无穷或0的时候，返回它本身
    else if(uf>0x80000000 && uf<=0x807fffff)
        return ((uf<<1)+0x80000000);  // uf为负的非规格化数  
    else if(uf>0 && uf<=0x007fffff)
        return uf<<1;  //uf为正的非规格化数
    else
        return (uf+(1<<23));  // uf为规格化数
}

csapp---datalab 总结

NO.12 floatFloat2Int - Return bit-level equivalent of expression (int) f for floating point argument f.

Request: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) {
    int a=(uf>>23)&0xff;
    if((uf>0xcf000000) || (uf>0x4effffff && uf<0x80000000))
        return 0x80000000;      // 浮点数uf表示的数超出int表示数的范围
}
    else if((uf>=0 && uf<=0x007fffff) || (uf>=0x80000000 && uf<=0x807fffff) || a<0x7f)
        return 0;    // 当uf为非规格化数或者规格化数的指数小于127的时候
    else 
    {
        int b=0x96-a;
        int c=!(uf>>31)-(uf>>31);
        uf=(uf&0x7fffff)+0x800000;
        if(b>=0)
            return c*(uf>>b);
        else
            return c*(uf<<-b);
    }

  这题我个人认为是浮点数这三题最难的一题，首先要考虑的情况巨多，而且限制了操作数个数，所以完全暴力的解法肯定不行。我失败的次数已经记不清了（太多了），不过最终还是写出来了。
下面是我在做这题时记的笔记,在记这篇博客的时候又整理了一下，更加通俗易懂了：
csapp---datalab 总结
csapp---datalab 总结
csapp---datalab 总结

csapp---datalab 总结

NO.13 floatPower2 - Return bit-level equivalent of the expression 2.0^x (2.0 raised to the power x) for any 32-bit integer x.

  • The unsigned value that is returned should have the identical bit
  • representation as the single-precision floating-point number 2.0^x.
  • If the result is too small to be represented as a denorm, return 0. If too large, return +INF.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
  • Max ops: 30
  • Rating: 4
unsigned floatPower2(int x) {
      if(x>=0x80000000 && x<0xffffff6a)
          return 0;            //  表示的数小于32位float表示的最小值
      else if(x>=0xffffff6a && x<=0xffffff81)
          return 1<<(149+x);   //  表示的数是非规格化数
      else if(x>=0x00000080 && x<0x80000000)
          return 0x7f800000;   //  表示的数大于32位浮点数表示的最大值
      else
      {   //  规格化情况
          unsigned y=x+127;
          return y<<23;
      }
}

  这个题目也略微有点绕。
  首先分析什么时候返回0，也就是当小于float最小表示的数的时候返回0。因为2^x必然是大于0的，float表达的最小数就是0x1，此时为2的-126次方乘以2的-23次方，等于2的-149次方，所以第一种情况就是x大于-149，则返回0。
  然后再分析什么时候返回正无穷，float表示的最大值是0x7f7fffff，即当x大于等于128（阶码全为1）的时候表示无穷，返回正无穷。
  然后分析，2^x能表示当float阶码为0，尾数只有一位为1的情况和阶码为0x1，尾数为0的情况即-149<=x<=-126。这个时候的float的表示应该是除了尾数有一位为1，其他位都是0。可以计算出尾数为1的那一位距离尾数最低位的位数m，然后将1<<m即可。这里的m应该用“23-（-x-126）”即m=149+x。所以是1<<(149+x)。
  然后就是规格化数的一种情况，这种情况最简单，就是阶码位加一就可以了。

总结：

  这十三题中，只有“allOddBits“和“howManyBits” 这两个函数是因为实在想不出来从网上看的别人写的代码，其他的题目没有任何“作弊现象”（David老师严厉的话语我依旧历历在目），过程很艰辛，前面整数的一个题花几小时太正常了，就是不断的去尝试。但是做出来非常有成就感，不得不说cmu这种学习方法真的不错，做出一题就能检验你做的对不对，而且还有分数，很有满足感，让我有种高中做数学难题的感觉，做出一题就迫不及待的和别人分享喜悦。
  这学期刚开始学计组的时候，因为老师讲的都是偏硬件的，再加上老师讲的听不大懂（没有老师的原因！都是我菜）计组前半学期没咋听过课，觉得学csapp才是正道，有点误入歧途的意思了，为了期末去“预习”计组的时候才意识到掌握基本的硬件也是必须的。人都傻了。
  之后要做的就是闻名已久的boom lab了，非常期待。

上一篇：《深入理解计算机系统》（CSAPP）读书笔记 —— 第六章 存储器层次结构


下一篇：CSAPP Lab2