CSAPP之实验一:位操作(Datalab)

    技术2025-03-14  31

    写在前面:对于想要入门csapp的人最好边看书边做实验,看书的时间不需要太多,主要有个大概的概念就行,通过做实验再慢慢理解,切记做实验的时候别只为了通过系统的测试而且改参数,而应该先分析,然后提取出大致思路后再开始着手改错。

    实验环境

    我是在windows10下的vscode编辑(因为比较熟悉这款软件),然后在搭建的服务器上测试,利用xshell和xftp工具进行文件传输和指令测试。

    为什么不在vmware上呢?因为我感觉我比较菜,解决了这个问题很久,有网络问题,有编译器问题。所以索性就直接用我之前花了10块钱买的服务器来玩。

    为什么不在docker虚拟化环境下做呢?因为在这个环境下不能用自己的vscode,而且每次做了一半的实验保存起来有点麻烦,主要我是有一次完成了几个小实验,然后不小心点了关闭窗口,然后。。。。数据就不见了,好像很难找回了,所以我就放弃了,docker虚拟化感觉比较适合在线上服务器中的搭建,而且只适合一次性编程。

    实验要求

    实验内容

    //1 /* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ //思路:求异或的非与表达式。逆方向来求解,异或是不同为一,那我们先求他们相同项,最后取反。 // 把1相同项找出来,再把0相同项找出来,然后分别取反再与起来 int bitXor(int x, int y) { return ~(x&y)&~(~x&~y); } /* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ // 思路:求0xffffffff,利用算术左移会根据符号位进行补位 int tmin(void) { return 0x1<<31; } //2 /* * isTmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * Legal ops: ! ~ & ^ | + * Max ops: 10 * Rating: 1 */ // 思路:求是否为补码最大值0x7fffffff,利用取反和加一一样的特质,除了最小值一样 int isTmax(int x) { return !((x+1)^(~x))&!!((x+1)); } /* * 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 */ // 思路: 求奇数位是否全为1,利用半掩码来算 int allOddBits(int x) { int i = 0xaa + (0xaa<<8); i += i<<16; return !((x&i)^i); } /* * 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 lowerBound = 0x30; int upperBound = 0x39; int sign = 0x1<<31; return !((x+~lowerBound+1)&sign)&!((~x+1+upperBound)&sign); } /* * 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) { x = ((!x)<<31)>>31; return (y&(~x))|(z&x); } /* * 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 checkSign = (x>>31)^(y>>31); return !!((checkSign&(~y>>31))|(~checkSign&(~(~x+1+y)>>31))); } //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 */ // 思路:逻辑非怎么实现,利用0的补码本身也是自己的特性去操作 int logicalNeg(int x) { return ((x|(~x+1))>>31)+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,b0; x = (~x&(x>>31))|(x&(~(x>>31))); b16 = !!(x>>16)<<4; x = (x>>b16); b8 = !!(x>>8)<<3; x = (x>>b8); 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; } //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 */ // 思路:计算浮点数*2,通过对特殊情况的浮点数值进行处理(如NAN,INF,非正规化),然后对正规化进行对exp+1就行; unsigned floatScale2(unsigned uf) { int exp = (uf&(0xff<<23))>>23; int sign = uf&(0x1<<31); if(exp == 0) return (uf<<1)|sign; if(exp == 0xff) return uf; exp++; if(exp == 0xff) return uf+(0x1<<23); return uf+(0x1<<23); } /* * 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 exp = ((uf&(0x7f800000))>>23)-127; int s = uf&0x80000000; int frac = (uf&(~((0x80000000)|(0x7f800000))))|0x800000; if(!!(exp&0x80000000)) return 0; if(!((exp-32)&0x80000000)) return 0x80000000; if((23-exp)&0x80000000) frac<<=exp-23; else frac>>=23-exp; if(!s) return frac; else if(frac>>31) return 0x80000000; return ~frac+1; } /* * 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 */ // 求2.0^x,化为(1.0*2^x) unsigned floatPower2(int x) { if((0x7f-x)&0x80000000&(~x)) return 0x7f800000; else if((0x7f+x)&0x80000000&x) return 0; else return (x+127)<<23; }

    测试方式

    ./dlc bits.c //测试代码是否符合要求,且有没有错误 ./dlc -e bits.c //每个小实验用了多少个运算符 make clean //清除上次的测试工具(内含历史测试数据) make //构造测试工具 ./btest //使用测试工具(只有通过这个测试才能宣布实验成功)

    实验截图

    最后一个实验因为测试数据比较多,所以导致超时,在网上看到别人把测试时间10改为20就通过了,我也试了下,通过了(具体是修改btest.c里的TIMEOUT_LIMIT)

    思考

    对底层的学习,很多内容很抽象,和我们的常规十进制理解有很大不同,这就需要我们在边看理论的过程中边做实验来更深的理解它。(实验花费了我好几天的时间才做出来,呜呜呜~)

    Processed: 0.009, SQL: 9