CSAPP Lab01——Data Lab完成思路

2024-06-10 00:52
文章标签 完成 data 思路 lab csapp lab01

本文主要是介绍CSAPP Lab01——Data Lab完成思路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

陪你把想念的酸拥抱成温暖

陪你把彷徨写出情节来

未来多漫长再漫长还有期待

陪伴你 一直到 故事给说完

——陪你度过漫长岁月

完整代码见:CSAPP/datalab-handout at main · SnowLegend-star/CSAPP (github.com)

01 bitXor

这道题是用~和&计算x^y

异或是两个二进制数a,b对应的位相同为0,不同为1。既然是aibi 不同才为,且只能用~和&两种位运算符号。考虑对a取反,再和b进行&操作。这样当ai =0,bi =1时可以得到1;但是还得考虑当ai =1,bi =0时也应该得到1,此时考虑的对b取反,再和a进行&操作。综合以上两点,我们可以初步得到式子为“(~a&b)|(a&~b)”,换算后得到“~(~(x & ~y) & ~(~x & y))”。

//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));
}

 

02 tmin

返回最小二进制补整数

Tmin不就是0x8000 0000吗?注意这里可以用到的整数在0~0xAA之间,所以是“1<<31”。

/* * tmin - return minimum two's complement integer *   Legal ops: ! ~ & ^ | + << >>*   Max ops: 4*   Rating: 1*/
int tmin(void) {//正数的补码是它本身,负数的补码是取反加一return 1<<31;}

03 isTmax

如果x是二进制补码的最大值,则返回1,否则返回0

       Tmax=0x7FFF FFFF,从Tmax的特殊性来考虑。如果x=Tmax,则x+1+x可以得到0xFFFF FFFF=Tmin。对于Tmin进行取反,则可以得到0。再对0取!,则可以令函数返回1。除此之外,还要考虑如果x本身就为Tmin,则它也会满足上述运算。所以得用^操作排除这种情况。

/** 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) {//二进制补码的最大值是:最高位0,其它位1int temp=x+1;int temp2=x+temp;//还得考虑x本身就是0xffffffff的情况,即x!=temp2return !(~temp2)&!!(x^temp2);}

04 allOddBits

如果word中所有的奇数位为1,则返回1,否则返回0(位从0~31位)

       这题十分恶心,是第一个卡住我的。开始想得太简单了,以为满足条件的数字只有0xAAAA AAAA这一个。后来发现0xFFAA AAAA这种也可以,这就让我犯了难——对于0xFF这种形式要怎么判断呢?想了很久都没有头绪。跳过这题后面再写的时候灵光一闪,想到只要判断奇数位是1就行,根本就不用考虑偶数位。要做到这一步其实就是把x和0xAAAA AAAA进行&操作,可以提取出x奇数为上所有的1得到数字x2。我们会发现,只要x满足条件,那进行上一步操作后的形式都是统一的0xAAAA AAAA。所以最后判断x2是不是与0xAAAA AAAA一致就行。

/* * 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) {//没搞出来//计算机的右移位运算默认是逻辑还是算数呢?dev c++是逻辑//直接不用考虑偶数位的情况,只考虑奇数位全为1的时候//怎么在dev c上跑x=0x80000000的时候返回0,这时候就返回1了?????int a=0xAA<<8;int b=a+0xAA;     //b=0xAAAAint c=(b<<16)+b;  //这里b<<16得加括号,因为+的优先级大于<<int d=!((c&x)^c); return d;//强行令偶数位全为0再进行比较
}

05 negate

返回-x

       简单的取反加一操作。最开始还在考虑Tmin的特殊性,验算后发现Tmin也符合这个规律。秒了,芜湖

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

06 isAsciiDigit

如果0x30 <= x <= 0x39,返回1,否则返回0

       开始我的思路是挨个判断x的每一位。即x的第5、6位只能为1,再高位只能为0;对于低四位,第4位为1的时候只有第1位可以同时为1,如果第4位为0则后三位无论是什么值都可以。但是挨个判断每一位需要的符号好像会超过限制。

       后来看了别的解法,第一次发现了符号位的大用。基本上这次的lab都没提供“-”这个操作,但是可以利用“+(~x+1)”来实现减法。如果给出x,只要用两个边界值0x30和0x39对x进行减法操作就行。最后通过符号位来判断x与0x30和0x39的大小。这种思路在后面的题目也会用到。

/* * 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) {//判断第四五位都是1、且高位都是0,1-3位值得小于等于9//x做完移位运算后自身值不发生改变的int a=x+~(0x30)+1;int b=0x39+~x+1;int c=a>>31;int d=b>>31;return !c&!d;
}

07 conditional

用位级运算表示三目运算符 x?y:z

       我们要注意到一点,这种返回值在几个数中选一个的势必得用到“|”操作,比如T01要是能用上“|”就会简单许多。由于只要x不为0就返回y,为0才返回z。要返回y,就是考虑当x不为0时让y和0xFFFF FFFF进行&操作。一个全新的操作在我脑中应运而生,那就是“!!x”。只要x不为0,那!!x就会得到1;x为0,那!!x会得到0。而对0或者1进行取反加一就可以得到0或者0xFFFF FFFF。这样我们就得到了想要的全1二进制数。此题结束。

/* * 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 y&(~(!!x)+1)|(z&~(~(!!x)+1));
}

08 isLessOrEqual

如果x<=y,则返回1,否则返回0

       这题算是T06的弱化版。T06还得进行两次比大小,这题只用比一次就行了。也是用减法然后进行符号位的判断就可以解决。

/* * 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 a=y+(~x+1);int b=x>>31&1;int c=y>>31&1;return (b&!c)|(!(a>>31)&!(b^c));//得控制后半部分只有同号的时候才能计算 
}

09 logicalNeg

用其余的操作符实现

       这题算是第二题卡了我很久的。想了一个多小时也没头绪——要如何才能做到当x不为0时返回0?假如从x的每一位着手,只要发现有一位不为0就可以判断x不为0,但是这样就要用到for循环了。遂跳过这题。

后来第二天再看的时候灵光一闪。既然对x的每位进行判断有困难,那还是老样子直接考虑数字这个整体。由于题目提供的运算符也不多,所以x的正负性成了可以拿来解题的性质。注意到一点,只要x不为0,那x的相反数符号位就和x的符号位是不同的。从正负性和符号位着手这题就很容易解决了。

/* * 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) {//不会 //果然过一天再搞就会有新思路,利用相反数符号的性质int x2=~x+1;int sign=(x>>31)^(x2>>31);int min=x>>31;return (~sign)&1&~((x2^x)^min);
}

10 howManyBits

使用补码时最少需要多少比特位

       这题的运算符限制是90,给人一种代码结构肯定十分庞大的感觉,倒是让我一下子不知如何下手。首先考虑的是把数字x和 ​​​​​​​​​​​​​​​​​​​​​ 进行比较,但这样用到的运算符数目必然会超过90。于是又想到了用二分法,但是二分法得结合for循环才好实施吧。最后又想到了一种二分法的变体。即x先和 ​​​​​​​ 比较,若是大于它就对x进行“>>16”的操作,然后再和 ​​​​​​​ 相比;小于它就直接和 ​​​​​​​ 进行比较。在不断的比较和移位操作中应该是可以判断出来的。

但是写其他题已经是花费了许多心力,遂开摆。等什么时候状态好了再来拿下这题。

/* 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 temp=x>>31;       //记录x的正负性int a=~x+1;int b=(1<<16)+a;int c=b>>31;          //用符号位判断2^16和x的大小return 0;
}

11 floatScale2

给定一个无符号数f,我们以浮点数的格式来看待这个数f,返回2*f

       首先得明白浮点数大致有三种类型:规格数,非规格数,无穷大或者NaN。然后提取出f的exp和frac部分。若f不是非规格数,对它进行判断再返回。若是规格数就好办了,直接在exp部分加上1就能返回了。

       值得一提的是,非规格数如果尾数最高位为1时,右移1位会使阶码最低位从0变为1,而这时候恰好就是正确的结果,并不需要额外的处理。这是因为乘2之后完成了进位,刚好规格数在小数点前有一个1,规格数和非规格数从而无缝衔接。

/* * 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 exp=uf & 0x7f800000;int frac=uf & 0x7fffff;if(uf==0x7f800000||uf==0xff800000)return uf; else if(exp==0x7f800000&&frac!=0)return uf;else if(exp==0)return (uf&0x80000000)+(frac<<1);//记得给位运算加括号elsereturn uf + 0x800000;
}

12 floatFloat2Int

给定一个无符号数f,我们以浮点数的格式来看待这个数f,将这个浮点数f转换为整形。

       上来就考虑两个边界,即浮点数太小就返回0;太大就返回0x80000000u。我们知道,浮点数的计算方法是“”,其中E=e-127。故当e<127的时候,这个数整体就<1了。当e>127+30的时候,E>=31,直接达到了32bit能表达的数据上限。其他情况就是套用此式即可。

/* * 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;int frac=uf & 0x7fffff;if(exp>127+30)//无穷大或者是NaN都返回统一的值return 0x80000000u;else if(exp<127){//非规格化的数,return 0;}if(uf>>31)return -(((frac>>23)+1)<<(exp-0x7F));else return ((frac>>23)+1)<<(exp-0x7F); 
}

 

13 floatPower2

返回2的x次方,返回用无符号数表示的浮点数

当e<-126时,这已经是浮点数能表示的最小值了,所以返回0。当e>127,浮点数表示不出来这种数字,只能返回无穷大了。其他的情况E=x+bias,左移23位即可。

/* * 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<-126)return 0;else if(x>127)return (0xFF)<<23;return (x+127)<<23;return 2;
}

这篇关于CSAPP Lab01——Data Lab完成思路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1046785

相关文章

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

Java 后端接口入参 - 联合前端VUE 使用AES完成入参出参加密解密

加密效果: 解密后的数据就是正常数据: 后端:使用的是spring-cloud框架,在gateway模块进行操作 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>30.0-jre</version></dependency> 编写一个AES加密

三相直流无刷电机(BLDC)控制算法实现:BLDC有感启动算法思路分析

一枚从事路径规划算法、运动控制算法、BLDC/FOC电机控制算法、工控、物联网工程师,爱吃土豆。如有需要技术交流或者需要方案帮助、需求:以下为联系方式—V 方案1:通过霍尔传感器IO中断触发换相 1.1 整体执行思路 霍尔传感器U、V、W三相通过IO+EXIT中断的方式进行霍尔传感器数据的读取。将IO口配置为上升沿+下降沿中断触发的方式。当霍尔传感器信号发生发生信号的变化就会触发中断在中断

Jenkins 插件 地址证书报错问题解决思路

问题提示摘要: SunCertPathBuilderException: unable to find valid certification path to requested target...... 网上很多的解决方式是更新站点的地址,我这里修改了一个日本的地址(清华镜像也好),其实发现是解决不了上述的报错问题的,其实,最终拉去插件的时候,会提示证书的问题,几经周折找到了其中一遍博文

CentOS下mysql数据库data目录迁移

https://my.oschina.net/u/873762/blog/180388        公司新上线一个资讯网站,独立主机,raid5,lamp架构。由于资讯网是面向小行业,初步估计一两年内访问量压力不大,故,在做服务器系统搭建的时候,只是简单分出一个独立的data区作为数据库和网站程序的专区,其他按照linux的默认分区。apache,mysql,php均使用yum安装(也尝试

使用Spring Boot集成Spring Data JPA和单例模式构建库存管理系统

引言 在企业级应用开发中,数据库操作是非常重要的一环。Spring Data JPA提供了一种简化的方式来进行数据库交互,它使得开发者无需编写复杂的JPA代码就可以完成常见的CRUD操作。此外,设计模式如单例模式可以帮助我们更好地管理和控制对象的创建过程,从而提高系统的性能和可维护性。本文将展示如何结合Spring Boot、Spring Data JPA以及单例模式来构建一个基本的库存管理系统

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

如何打造个性化大学生线上聊天交友系统?Java SpringBoot Vue教程,2025最新设计思路

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录

15 组件的切换和对组件的data的使用

划重点 a 标签的使用事件修饰符组件的定义组件的切换:登录 / 注册 泡椒鱼头 :微辣 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta http-equiv="X-UA-