CSAPP-datalab

使用docker环境进行实验

因为是mac系统，它实验里面的自动测试无法进行，所以还是使用linux 的docker ，网上已经有现成的方法和docker image所以直接使用，记录一下过程

下载镜像：

docker run -d -p 9912:22 --name datalab yansongsongsong/csapp:datalab

进入实验环境：

docker exec -it datalab /bin/zsh

很贴心zsh 都配置好了,可惜没有vim的配置

Datalab

这是一个练习位操作的实验，每年MIT课程不同实验里面的内容也稍有不同，但目的和类型都是一样，练习信息的位表示，包括整数和浮点数，由于浮点数复杂一点，所以要实现的也难一些。
我们所需要做的就是完善bits.c文件里的每一个函数，一个函数就是一个题目。其他的程序都是用来测试你的完成结果的。报告完成每个function用了多少个操作符（有的题目有运算符和操作数的限制）编译是否有错，能不能通过测试，这些在实验给的handout里面都说的很清楚了。
我们还是把目光重点放在每一个题目的实现上吧。vim bits.c 开始你的表演

bitXor

这题较为简单，就是仅用非和与来实现一个异或操作，异或就是相同为0，不同为1，数电学习逻辑门的时候有涉及到过，^可以使用 ~、&和|表示，而|又可以用 ~和&表示，但是莫名其妙的最后测试过不了（不能拿满分好难受）
```
int bitXor(int x, int y) {
  return ~(~x&~y)&~(x&y);
}
```

tmin

需要返回一个最小的补码数，也就是100…00，把1左移31位到最高位即可
```
int tmin(void) {
  return 1 << 31;
}
```

isTmax

输入一个数判断是不是最大的补码数，是的话返回1，不是返回0
观察补码最大的形式011…111，它加1就变成100…00，再和自己异或就能得到11….111，但是有一个特殊的数-1[全1串]，它加一和自己异或也是全1串，所以需要把这种特殊情况排除，即～(!x)，当x为-1时，它返回1。综合两种情况最后x为011…11时需要返回1，其他都返回0。
```
int isTmax(int x) {
  return !(~(x^(x + 1)) | !(~x));
}
```

allOddBits

串中所有奇数位都是1的话就返回1，否则返回0
实验刚开始说了，使用的整数只能是0～FF，所以想要构造32位的掩码0xAAAA就只能使用移位操作拼接起来。有掩码之后就用&操作取出所有的奇数位置，偶数位置置0，再通过和掩码异或就可以知道是不是所有的奇数位都是1。
```
int allOddBits(int x) {
  //return 2;
  int mask = (0xAA << 8) + 0xAA;
  mask = (mask << 16) + mask;
  return !((x & mask) ^ mask);
}
```

negate

这题这么简单，放到第一题不好吗
实现补码相反数，取反加1就可以
```
int negate(int x) {
  return ~x + 1;
}
```

isAsciiDigit

判断一个数是否在0x30和0x39之间
需要和上下界比大小来判断是否越界，和上界比$ 0x39-x$需要非负，即符号位为0
和下界比 $ 下界-x$ 一定要是负数或者0，这里如果使用0x30做下界减的话，不好判断相等的时候最高位是0，所以在运算中把下界变为0x2f，这样只需要保证最高位是1即可。
```
int isAsciiDigit(int x) {
 // return 2;
  int min = 0x2f+(~x+1);
  int max = 0x39+(~x+1);
  min = !!(min >> 31);
  max = !(max >> 31);
  return min & max;
}
```

conditional

实现一个条件运算符 x ? y : z
这题有两个小技巧用了之后可以写的非常简洁，就是!!x 和 （x&y）|(!x&z)
两个非操作，可以把补码的位形式转换为布尔形式，而且当表示不为0的时候（任何一位有1）都会返回逻辑1（True），而当所有位为0的时候，返回逻辑0（False）。
后面的（x&y）|(!x&z) 表达x为0返回z，x为1返回y。也是条件运算符的核心逻辑。

int conditional(int x, int y, int z) {
  //return 2;
  x = !!x;  //判断x是否为0，x=0，则赋值0，x不为0赋值1
  x = ~x + 1;   //取相反数，最高位有变化
  return (x&y) | (~x&z);  //x为0返回则z，x为1返回y
}

isLessOrEqual

实现一个小于等于号。
两个数比大小，先看符号位，符号位不同，正数大于负数。符号位相同，再做差判断。
这里做差的时候要$y-x$，因为判断的是$x \leq y$则返回1，需要$y-x$的符号位为0即可

 int isLessOrEqual(int x, int y) {
   int sign = !(x>>31)^!(y>>31);      // is 1 when signs are different
   int a = sign & (x>>31);            // diff signs and x is neg, gives 1
   int b = !sign & !((y+(~x+1))>>31); // same signs and difference is positive or = 0, gives 1
   return a | b;
 }

logicalNeg

实现一个逻辑非
逻辑非就是非0为1，非非0为0，只有全0串会返回1，利用几个特征来构造
首先Tmin和0的相反数（取-x+1）都是自己（000..000和100…000）
除了0和Tmin，其他的任何数取相反数符号位总是不同的，这样的话符号位进行｜操作都是1，TMin由于符号位总是1，这样就把0区分出来了
```
int logicalNeg(int x) {
  //return 2;
  return ((x|(~x+1))>>31)+1;
}
```

howManyBits

一个数用补码最少需要几位才能表示出来，其实就找最高有效位，正数的话，找到最高有效位还需要上一个符号位。负数的话，需要找到最高位的那个0，因为补码的1扩展的原因，负数前面可以加很多1，1101和101 表示的都是-3。
这题还是挺难想的，在找最高位的时候还用了二分的思想。算是一个很精致的方式了。下面这种方法是我看到的比较容易理解的方式。

int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了）

// 不断缩小范围
  b16 = !!(x>>16)<<4;//高十六位是否有1
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = !!(x>>8)<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = !!(x>>4)<<2;//同理
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

还有一种不太好理解，但是很简洁的方法。放在这里记录一下

int howManyBits(int x) {
  method 1,hard understand,but short;
  int n = 0;^i
  int val = x^(x << 1);
  n += ((!!(((~0) << (n + 16)) & val)) << 4);
  n += ((!!(((~0) << (n + 8)) & val)) << 3);
  n += ((!!(((~0) << (n + 4)) & val)) << 2);
  n += ((!!(((~0) << (n + 2)) & val)) << 1);
  n += !!(((~0) << (n + 1)) & val);
  return n + 1;
}

float_twice

返回一个浮点数乘以2的结果。浮点数的操作相比整数的来说更复杂一点
需要判断对符号数的exp不同，而导致的规格化或者非规格化数进行判断

unsigned float_twice(unsigned uf) {

  int exp = (uf&0x7F800000)>>23;   //取出阶码
  int sign = uf&(1<<31);   //取符号位
  if(exp == 0) return uf<<1|sign;    //非规格化数，uf*2加上符号位即可
  if(exp == 255) return uf;   //无穷大或者NaN，直接返回自身
  exp++;  //如果uf乘以2（阶码加一）后变成255就返回无穷大
  if(exp == 255) return (0x7F800000|sign); 
  return (exp<<23)|(uf&0x807FFFFF); //返回阶码加1后的符号原数
}

float_i2f

int转为float的时候是有精度损失的，int32bit，但是float的尾数只有23bit，需要做舍入操作，选择向偶数舍入法

unsigned float_i2f(int x) {
  int sign, exp, frac, bitc, tailb;
  if(x == 0) return 0;
  else if(x == 0x80000000) return 0xCF000000;

  sign = (x >> 31) & 1;
  if(sign) x = -x;

  bitc = 1;
  while((x >> bitc) != 0)
    bitc++;
  bitc--;

  exp = bitc + 127;

  x = x << (31 - bitc);
  frac = (x >> 8) & 0x7FFFFF;

  if (bitc > 23) {
    tailb = x & 0xFF;

    if ((tailb > 128) || ((tailb == 128) && (frac & 1))) {
      frac += 1;
      if (frac >> 23) {
         exp += 1;
         frac = 0;
      }
    }
  }
  return (sign << 31) | (exp << 23) | frac;
}

float_f2i

浮点数转换为整数，需要将浮点数中的指数部分和尾数部分拿出来，然后通过这两部分来转换。在转换过程中需要判断是否溢出，以及浮点数是不是规格化数。

int float_f2i(unsigned uf) {
  int exp = (( uf & 0x7F800000) >> 23) - 127;  //计算指数
  int sign = uf >> 31; //取符号位
  int frac = ((uf & 0x007FFFFF) | 0x00800000);
  if(!(uf&0x7FFFFFFF)) return 0;  //如果原浮点数为0，则返回0

  if(exp > 31) return 0x80000000;  //如果原浮点数大于31，返回溢出值
  if(exp < 0) return 0;  //如果浮点数小于0，返回0

  if(exp > 23) frac = frac << (exp - 23); //将小数转化为整数
  else frac = frac >> (23 -exp);

  if(!((frac >> 31) ^ sign)) return frac;  //判断是否溢出，若符号位没有变化，则没有溢出，返回正确的值
  else if(frac >> 31) return 0x80000000;  //原数为正值，现在为负，返回溢出值
  else return ~frac + 1;   //原数为负值，现在为正值，返回相反数。
}

结果

没有满分有点难受，第一题总是不过这个最终评分测试

btest可以过

总结

总的来说datalab还是比较简单的一个lab，考察的都是一些位操作的方式，能够更底层的了解到数字的表示方法，有一些题目涉及到数电和离散逻辑之类的技巧，有一些非常精妙的解决办法吧，虽然不久之后可能都忘记了，但是写在这里做一个记录，方便需要的时候在复习。

Reference

下载资料

本文由 sengle 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名?>