CSAPP-Labs

本文用来记录我的CSAPP实验代码，坚持坚持坚持！

Lab网址：http://csapp.cs.cmu.edu/3e/labs.html , 下载Self-Study Handout

网课：https://www.bilibili.com/video/BV1iW411d7hd

我的代码仓库：https://github.com/Lyb-code/CSAPP-Labs

Lab1 DataLab

1 代码

//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) {
  int z = x & y; // Bit[1, 1] -> 1
  int w = (~x) & (~y); // Bit[0, 0] -> 1
  return (~z) & (~w); // Bit[1, 0], [0, 1] -> 1
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  int x = (0x80) << 24;
  return x;
}
//2
/*
 * 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) { // Tmax + 1 = 0x10000000 = ~Tmax. Remember to exclude the case of x = -1.
  int k = x + 1;
  int m = k ^ (~x);// when x = -1 or Tmax, m = 0
  return (!!k) & !m;
}
/* 
 * 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 k = 0xAA;
  k = (k << 8) | k;
  k = (k << 16) | k;//0xAAAAAAAA
  x = x & k; // remove all even-numbered bits of x
  return ! (x ^ k);
}
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return (~x) + 1;
}
//3
/* 
 * 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 a = (x ^ 0x30) >> 4;
  int b = (x & 0x8) >> 3;
  int c = (x & 0x4) >> 2;
  int d = (x & 0x2) >> 1;
  return ! ((a) | (b & c) | (b & d));// return 1 if a = 0 And b & c = 0 And c & d = 0;
}
/* 
 * 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) {
  int a = !x; // [x->a]  0->1, others->0
  a = (a << 1 | a);
  a = (a << 2 | a);
  a = (a << 4 | a);
  a = (a << 8 | a);
  a = (a << 16 | a);
  return ((~a) & y) + (a & z);
}
/* 
 * 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) {
  int k = 0x80 << 24;
  int hbx = x & k; // keep only the highest bit of x
  int hby = y & k; // keep only the highest bit of y
  int hbEqual = !(hbx ^ hby);// if highest bits are equal, return 1
  int z = x + (~y) + 1;// x - y;
  int ans1 = (!hbEqual) & ((hbx >> 31) & 1);// if hbEqual = 0, use hbx to judge to prevent overflow of z.
  int ans2 = hbEqual & (((z >> 31) & 1) | (!(z ^ 0)));
  return ans1 + ans2;
}
//4
/* 
 * 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) {
  x = (x >> 16) | x;
  x = (x >> 8) | x;
  x = (x >> 4) | x;
  x = (x >> 2) | x;
  x = (x >> 1) | x;
  return (~x) & 1;
}
/* 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 b16, b8, b4, b2, b1;
  int sign = x>>31; // all 1 or all 0
  x = ((~sign) & x) | (sign & (~x));// x < 0 --> ~x ; x > 0 --> x;
  b16 = (!!(x >> 16)) << 4;// If the upper 16 bits have 1, at least the lower 16(1<<4) bits are required.
  x = x >> b16;
  b8 = (!!(x >> 8)) << 3;// If the remaning top 8 bits have 1, at least the lower 8(1<<3) bits are required.
  x = x >> b8;
  b4 = (!!(x >> 4)) << 2;// narrow the scope
  x = x >> b4;
  b2 = (!!(x >> 2)) << 1;
  x = x >> b2;
  b1 = (!!(x >> 1));
  x = x >> b1;
  return b16 + b8 + b4 + b2 + b1 + x + 1;
}
//float
/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   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) {
  int sign = 0x80000000 & uf;
  int exp = (0x7f800000 & uf) >> 23;
  int frac = 0x7fffff & uf;
  if (exp == 0xff) {// NaN and infinity: do nothing
    
  } else if (exp == 0) {// Denormalized value
    if ((frac >> 22) == 0) {
      frac = frac << 1;
    } else {
      exp = 1;
      frac = (frac << 1) & 0x007fffff;
    }
  } else {//Normalized value
    exp += 1;
  }
  uf = sign | (exp << 23) | frac;
  return uf;
}
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (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) {
  int sign = uf >> 31;
  int exp = (0x7f800000 & uf) >> 23;
  int bias = (1 << 7) - 1;
  int E = 0, ans = 0;
  int frac = 0x7fffff & uf;
  if (exp == 0xff) {// NaN and infinity
    return 0x80000000u;
  } else if (exp == 0) {// Denormalized value
    E = 1 - bias;
  } else {//Normalized value
    E = exp - bias;
    frac |= 0x800000;
  }
  //printf("%d %d \n", E, frac);
  if (E > 30) { // prevent left shift overflow
    return 0x80000000u;
  } else if (E > 23) {
    ans = frac << (E - 23);
  } else if (E > -9) {// prevent the right shift length from being greater than 32
    ans = frac >> (23 - E);
  }
  if (sign) {
    ans = -ans;
  }
  return ans;
}
/* 
 * 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) {
    int bias = 127;
    if (x > 128) {
      return 0x7f800000;
    } else if (x > -150) {
      x += bias;
      if (x >= 0) { // Normalize
        return x << 23;
      } else { // Denormalize
        return 1 << (23 + x);
      }

    } else {
      return 0;
    }
}

2 代码说明

• allOddBits构造了一个奇数位全1的掩码 k

• isAsciiDigit的思路是看形参x是不是"0x3m"的形式，且m处于0到9之间。

  我觉得这样做的推广性不强，当范围变大之后就能难再这样做。CSAPP 之 DataLab详解链接提供了一个更有推广性的解，如下：

  int isAsciiDigit(int x) {
    int sign = 0x1<<31;
    int upperBound = ~(sign|0x39);//加上比0x39大的数后符号由正变负
    int lowerBound = ~0x30;//加上小于等于0x30的值时是负数
    upperBound = sign&(upperBound+x)>>31;  
    lowerBound = sign&(lowerBound+1+x)>>31;
    return !(upperBound|lowerBound);
  }
  

• conditional的思路是正确的，不过可以更简洁。!!x挺好用的。

  int conditional(int x, int y, int z) {
    x = !!x; // 0->0, others->1
    x = ~x + 1; //0的补码是全0，1的补码是全1	
    return (x & y) + ((~x) & z);
  }
  

• isLessOrEqual思路：符号不同，正数大；符号相同，看差值符号

• logicalNeg思路：使用或操作，把所有的1都压缩到第一位。

  可以更简洁，如下。利用了补码的性质：0和tmin(1后面全0)的补码是本身，其余整数的补码是自己的相反数。只有当x为0时，x和其补码的或操作得到的符号位才会是0，其余情况都是1.

  int logicalNeg(int x) {
    return ((x | (~x + 1)) >> 31) & 1 ^ 1;
  }
  

• howManyBits，卡住我的一题。思路就是找与符号位不同的最高位n，然后用该位数加1得n+1.

  首先，做了个处理，如果x的符号位为0，x不变；否则对x取反。解题目标简化为：找最高的1位的位数n，然后用该位数加1。

  不断地判断x的最高16、8、4、2、1位和最低1位是否有1，用**!!**可以很方便判断二进制数是否含有1。如果最高16位有1，那么最低16位肯定需要，答案加上16，并将x右移16位，查看接下来的最高8位…如果最高16位没有1，那么x不右移，直接看x低16位的最高8位…依次类推。实现是很巧妙的，我开始没想到。

• floatScale2、floatFloat2Int和floatPower2考察浮点数，做起来比想象的顺利，因为可以用if、while等操作符了。关键是对浮点数的结构有了解，知道Normolize Value和Denormolize Value是啥，可以看看网课或书本，实现起来就能分情况讨论了。具体见代码和注释。

  当位移操作的长度大于等于窗口长度时，得到的移动量为（位移长度%窗口长度），这是看弹幕知道的，看书时可以再验证。Undefined Behavior: Shift amount < 0 or ≥ word size。因此，不要做出移位数量小于0或大于窗口长度的操作。我在floatFloat2Int方法中排除了这两种情况。

• 其他函数，直接看代码，参考注释即可

3 总结

CMU老师说“任何形式的搜索都是作弊”，因此实验一定要自己做！！！！先找资料、看网课，不到最后一步，不看别人的代码。

除了howManyBits外，所有的问题都是我自己解决的，对位操作、浮点型的表示更加熟悉了，还是不错的。howManyBits实在没有思路了，借鉴了网友的解答。所以，作弊了一小点点(4/36)。

注意实验总结，享受思考总结的过程，多学习优秀的代码。

本次实验耗时：22.5h。