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
- https://zhuanlan.zhihu.com/p/82529114
- https://yieldnull.com/blog/4b85a93fe9e4c80735233aa6dff922245f303698/#float_i2f
- https://zhuanlan.zhihu.com/p/28335741
- https://www.cnblogs.com/Xlgd/p/12667422.html
- https://zhuanlan.zhihu.com/p/59534845
- https://www.ravenxrz.ink/archives/2d758396.html
- https://wdxtub.com/csapp/thick-csapp-lab-1/2016/04/16/
下载资料
本文由 sengle 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名?>