CSAPP的Lab学习——DataLab

编程入门行业动态更新时间:2024-10-20 04:04:30

CSAPP的Lab学习——DataLab

文章目录

前言
一、bitXor（异或）
二、tmin（最小的二进制补码）
三、isTmax（判断是否为最大值）
四、allOddBits（判断奇数位是否都是1）
五、negate（计算相反数）
六、isAsciiDigit（判断0x30 <= x <= 0x39）
七、conditional（实现x ? y : z）
八、isLessOrEqual（比较两个数的大小）
九、logicalNeg（逻辑取反）
十、howManyBits（计算位数）
十一、floatScale2（将单精度浮点数乘以 2）
十二、floatFloat2Int（将单精度浮点数转为整数）
十三、floatPower2（计算2.0ˆx）
总结

前言

一个本硕双非的小菜鸡，备战24年秋招。刚刚看完CSAPP，真是一本神书啊！遂尝试将它的Lab实现，并记录期间心酸历程。
代码下载

官方网站：CSAPP官方网站

以下是官方文档翻译：
此分配的目的是为了更熟悉整数和浮点数的位级表示。你可以通过解决一系列的编程“谜题”来做到这一点。这些谜题中有很多都是人为的，但你会发现自己在思考一些细节。
bits.c文件包含了13个编程谜题中的每一个的骨架。你的任务是只使用整数谜题（即没有循环或条件）和有限数量的C运算和逻辑运算符来完成每个函数骨架。具体来说，您只允许使用以下八个运算符：
! ˜ & ˆ | + << >>
其中一些函数进一步限制了这个列表。此外，您不允许使用任何超过8位的常量。有关详细的规则和关于所需的编码风格的讨论，请参见bits.c中的注释。
本节描述您将以位解决的谜题。
表1列出了从最简单到最难的按难度顺序排列的谜题。“评级”字段给出了谜题的难度评级（点数），而“最大ops”字段给出了您允许用于实现每个函数的最大操作符数。有关函数所需行为的更多细节，请参见bits.c中的注释。您也可以参考test.c中的测试功能。这些功能被用作引用函数来表示函数的正确行为，尽管它们不满足函数的编码规则。
对于浮点难题，您将实现一些常见的单精度浮点运算。对于这些谜题，您被允许使用标准控制结构（条件、循环），并且您可以同时使用int和无符号数据类型，包括任意无符号和整数常量。您不能使用任何联合、结构或数组。最重要的是，您可能不使用任何浮点数据类型、操作或常量。相反，任何浮点操作数都将作为具有类型的形式传递给函数无符号，任何返回的浮点值都将为无符号类型。代码应该执行实现指定浮点操作的位操作。
每个"Expr"是一个表达式，只使用以下内容:

整数常量0到255 (OxFF)，包括不允许使用像oxffffffff这样的大常量。
函数参数和局部变量(没有全局变量)。
3.一元整数运算!～
二进制整数运算& ^ / + << >>
有些问题甚至进一步限制了允许的操作符集合。每个“Expr”可以由多个操作符组成。

您不局限于每行一个操作符。明确禁止您:

使用任何控制结构，如if、do、while、for、switch等。
定义或使用任意宏。
3.在此文件中定义任何附加函数。
调用任意函数。
可使用“&&”、“11”、“-”、“?”等其他操作:
使用任何形式的铸造。
使用除int以外的任何数据类型。
这意味着不能使用数组、结构体或联合。

您可以假设您的机器:

使用2s补码，32位整数表示。
按算术方式执行右移。
3.如果移位量小于0或大于31，则在移位时具有不可预测的行为。

浮点编码规则
对于需要实现浮点运算的问题，
编码规则没有那么严格。你可以使用循环和
有条件的控制。你可以同时使用整型和无符号。
可以使用任意整数和无符号常数。你可以用任何算术，
对int或unsigned数据的逻辑操作或比较操作。

你被明确禁止:

定义或使用任何宏。
在此文件中定义任何其他函数。
3.调用任意函数。
使用任何形式的铸造。
使用除int或unsigned之外的任何数据类型。这意味着你
不能使用数组、结构或联合。
使用任何浮点数据类型、操作或常量。

注:

使用dlc(数据实验室检查器)编译器(在讲义中描述)检查你的解决方案的合法性。
每个函数都有一个最大的操作数(整数、逻辑、或者比较)，你可以在你的实现中使用函数的。最大运算符计数由dlc检查。注意，赋值(‘=’)不计算;你可以用尽可能多的这些都是你想要的，没有惩罚。
3.使用最好的测试工具来检查函数的正确性。
使用BDD检查器来正式验证您的函数
函数中给出了每个函数的最大操作数
每个函数的头注释。如果有任何不一致在写入操作和此文件中的最大操作之间，考虑这个文件是权威的来源。

我注：瞅代码介绍就行，要会编译。

一、bitXor（异或）

/ *

bitXor—x^y，只使用~和&
*示例:bitXor(4,5) = 1
*合法操作:~ &
*最大ops: 14
*评分:1
/
第一眼瞅到这道题我愣了两秒，在我心中CSAPP不得极为高大上且难度巨高。。。然而虽然是第一题，但是我认为也没啥难度（插旗中等到时候回来被打脸）。然后就没过去，其实主要是文档的锅，我看了个||瞅差了。回头发现是异或。
异或就是异为1同为0，这道题要是想出现比较结果只能依靠&。
首先第一想法就是依靠&把相同排出去，写了个 ~(x & y)，这个意思是不是同1为1，然后我就想到了 ~( ~x & ~y) ，这是不是同0为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) {return ~(~x & ~y) & ~(x & y);
}

Score Rating Errors Function
1 1 0 bitXor
Total points: 1/1

二、tmin（最小的二进制补码）

/ *

tmin—返回最小2的补数整数
*法律操作:!n .;在比;
*最大ops: 4
*评分:1
/
又是翻译的锅，第一眼没看懂题啥意思，后来看解释明白了（所以英语一定要学好啊）。
当时看CSAPP的时候就研究过，当码长为8时，0的补码为0000 0000，则0-1也就是-1的补码就是1111 1111，所以最小为-128即1000 0000。至于为啥不再减一，因为再减一0111 1111就转正为127了。类比此题就是把1左移31位（因为该代码运行在32位系统上）

/* * tmin - return minimum two's complement integer *   Legal ops: ! ~ & ^ | + << >>*   Max ops: 4*   Rating: 1*/
int tmin(void) {return 1 << 31;}

Score Rating Errors Function
1 1 0 tmin
Total points: 1/1

三、isTmax（判断是否为最大值）

/ *

isTmax——如果x是最大值，则返回1，如果是2，则返回2。
*，否则为0
*法律操作:!n .
*最大ops: 10
*评分:1
/
对我来说真的是一道很精彩的题目，想了一个小时才勉强搞定。主要是！与~的区别吧，还有0x80000000这个不好区分。总之真是一道很棒的题目啊！
思路最开始是想和0x7fffffff比较来着（犯了if语句用得太多的毛病），然后发现不对后改用+1判断，发现0x80000000这个相反数是跟本身一致的，然后又想到了第一题（当时还直接拷贝过来了，结果发现其实可以直接用^了）。然后就是经典的双数问题，改了又改还参考了一下其他人写的才弄好。

//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) {return !!(~x) & !((~x) ^ (x + 1));
}

Score Rating Errors Function
1 1 0 bitXor
Total points: 1/1

四、allOddBits（判断奇数位是否都是1）

/ *

allOddBits -如果单词中所有奇数位都为1，则返回1
*位从0(最低有效)到31(最高有效)
allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
*法律行动:!n; n;在比;
*最大ops: 12
*评分:2分
/
有了上一道题的经验就知道这类题该怎么做了（但其实后来发现是两个类型的），上来先找规律做比较，然后“惊讶”的发现lab是可以用=的，只是不能超限。。。
想办法凑异或呗，既然可以这么搞那就拿0xAA做比较，先想办法弄出一个0xAAAAAAAA来，移位操作再加到一起，然后一个逻辑取反。。。
一顿操作猛如虎，一看没过。奥，二百五竟是我自己，偶数位不用考虑忘了，那就先控下数再比较。

/* * 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 m1 = 0xAA;int m2 = m1 + (m1 << 8);int m3 = m2 + (m2 << 16);return !(m3 ^ (x & m3));
}

Score Rating Errors Function
2 2 0 allOddBits
Total points: 2/2

五、negate（计算相反数）

/ *
*负-返回-x
*示例:negate(1) = -1。
*法律行动:!n; n;在比;
*最大操作数:5
*评分:2分

/
送分题，送分题！当时我在第三题有多狼狈，逻辑取反和按位取反整的糊涂，现在我就有多嚣张（不是）。按位取反可以通俗理解为*（-1）再-1，所以这题就是先按位取反再+1。

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

Score Rating Errors Function
2 2 0 negate
Total points: 2/2

六、isAsciiDigit（判断0x30 <= x <= 0x39）

/ / 3
/ *

isAsciiDigit—如果0x30 <= x <= 0x39(字符’0’到’9’的ASCII编码)，则返回1
*示例:isAsciiDigit(0x35) = 1。
isAsciiDigit(0x3a) = 0。
isAsciiDigit(0x05) = 0。
*法律操作:!n .;在比;
*最大ops: 15
*评分:3
/
思路好想，结果我写错了，忘了异或是按位操作的，忘加！转数字了，试了很多次才发现问题出在什么地方。

//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) {return (!((x & 8) ^ 0) + !((x & 14) ^ 8)) & !((x >> 4) ^ 3);
}

Score Rating Errors Function
3 3 0 isAsciiDigit
Total points: 3/3

七、conditional（实现x ? y : z）

/ *
*有条件的——与x相同?Y: z
*示例:条件(2,4,5)= 4
*法律操作:!n .;在比;
*最大ops: 16
*评分:3

/
这题做出来没费劲，解释费老大力了，因为我最后时候居然解释不通我的代码了。
大概路子是利用0111和0000的性质了。
主要我面临的问题是反补码和~的不清楚，这次通过这道题应该没问题了，熟悉了很多。这道题对我影响意义很大！
记住1的补码是-1，-1的补码是1111，0的补码还是0。
~0 = 1111

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

Score Rating Errors Function
3 3 0 conditional
Total points: 3/3

八、isLessOrEqual（比较两个数的大小）

/ *

isLessOrEqual—如果x <= y，则返回1，否则返回0
*示例:isLessOrEqual(4,5) = 1。
*法律操作:!n .;在比;
*最大ops: 24
*评分:3
/
心态爆炸的一道题，其实思路还是挺清晰的，但就是位操作与或非啥的太乱了，给我整的心态爆炸，费了三张演算纸，一个下午的时间才勉强解决。。。
通俗易懂的分类讨论，同号异号，正负号以及值相同的情况。我主要面对的问题是写着写着就乱了不知道是0是1（当时脑子也乱就觉得马上就能解决了），后来休息的时候发现这样不行，拿演算纸好好推导了一下思路，这才使得难度变简单了些。结果千辛万苦发现没有考虑值相等的情况，又是一顿捅咕。
说多了都是泪啊，切记！

/* * 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 flagX = (x >> 31) & 1;int flagY = (y >> 31) & 1;int z = y + (~x + 1);int flagZ = !((z >> 31) & 1) | !(z ^ 0);return (!(~flagX & flagY)) & ((flagX & ~flagY) | (flagZ));
}

Score Rating Errors Function
3 3 0 isLessOrEqual
Total points: 3/3

九、logicalNeg（逻辑取反）

/ / 4
/ *

logicalNeg—实现!操作符，使用all of
*合法的操作符except !
*示例:logicalNeg(3) = 0, logicalNeg(0) = 1
*合法操作:~ & ^ | + <<在比;
*最大ops: 12
*评分:4
/
柳暗花明又一村。这题好歹回了点信心，太惨了。

//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) {return ((x | (~x + 1)) >> 31) + 1;
}

Score Rating Errors Function
4 4 0 logicalNeg
Total points: 4/4

十、howManyBits（计算位数）

/* howManyBits:返回表示x所需的最小位数
*二进制补码
*例子:howManyBits(12) = 5
*多少位(298)= 10
*多少位(-5)= 4
*多少位(0)= 1
*多少位(-1)= 1

howManyBits(0x80000000) = 32
*法律操作:!n .;在比;
*最大ops: 90
*评分:4
/
思路不难，可惜当时没有坚持到最后，还是参考了别人的代码。
考虑正负，再每一位查找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 sign = x >> 31;x = (sign & ~x) | (~sign & x);int High_16 = (!(!(x >> 16))) << 4;x = x >> High_16;int High_8 = (!(!(x >> 8))) << 3;x = x >> High_8;int High_4 = (!(!(x >> 4))) << 2;x = x >> High_4;int High_2 = (!(!(x >> 2))) << 1;x = x >> High_2;int High_1 = (!(!(x >> 1)));x = x >> High_1;int High_0 = x;return High_16 + High_8 + High_4 + High_2 + High_1 + High_0 + 1;
}

Score Rating Errors Function
4 4 0 howManyBits
Total points: 4/4

十一、floatScale2（将单精度浮点数乘以 2）

/ /浮动
/ *

floatScale2——返回与表达式2*f for等价的位级别
*浮点参数f。
*参数和结果都以unsigned int类型传递，但是
*它们被解释为的位级表示
*单精度浮点值。
*当argument是NaN时，返回argument
*合法操作符:任何整数/无符号操作符，包括。||，&&。还有if, while
*最大ops: 30
*评分:4
/
注意：浮点数解除了很多限制，比如可以使用if，while等函数了。
主要是考察浮点数的定义：浮点数表示由符号位，尾数位和阶码位，又有单精度和双精度之分。根据阶码位分为规格化数、非规格化数和特殊值。都要分别考虑。

//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) {unsigned s = uf & (1 << 31);unsigned exp = (uf & 0x7f800000) >> 23;unsigned frac = uf & (~0xff800000);if (exp == 0) return frac << 1 | s;if (exp == 255) return uf;exp++;if (exp == 255) return 0x7f800000 | s;return s | (exp << 23) | frac;
}

Score Rating Errors Function
4 4 0 floatScale2
Total points: 4/4

十二、floatFloat2Int（将单精度浮点数转为整数）

/ /浮动
/ *

floatScale2——返回与表达式2*f for等价的位级别
*浮点参数f。
*参数和结果都以unsigned int类型传递，但是
*它们被解释为的位级表示
*单精度浮点值。
*当argument是NaN时，返回argument
*合法操作符:任何整数/无符号操作符，包括。||，&&。还有if, while
*最大ops: 30
*评分:4
/
分情况讨论的一题，根据阶码的值可分为>31(溢出)，<0（非规格化数且接近0），>23(是一个没有小数点的23位数)以及>0的数，每一种都有各自的判断及结果标准。
ps：半天没通过，搞得我以为哪里判断错了，回头一瞅发现127打成172了。。。

/* * 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) {unsigned s = uf & (1 << 31);unsigned exp = (uf & 0x7f800000) >> 23;unsigned frac = (uf & 0x7fffff) | 0x800000;int E = exp - 127;if (exp == 255 || E > 31 || frac >> 31) return 0x80000000;if (E < 0) return 0;if (E > 23) frac <<= (E - 23);else frac >>= (23 - E);if (!((uf >> 31) ^ (frac >> 31))) return frac;return ~frac + 1;
}

Score Rating Errors Function
4 4 0 floatFloat2Int
Total points: 4/4

十三、floatPower2（计算2.0ˆx）

/ *

floatPower2—返回与表达式2.0^x等价的位级别
*(2.0的x次方)表示任意32位整数x。

*返回的unsigned值应该具有相同的位
*表示为单精度浮点数2.0^x。
*如果结果太小，无法用denorm表示，则返回

0。如果太大，返回+INF。

*合法操作符:任何整数/无符号操作符，包括。||，&&。还有if, while
*最大ops: 30
*评分:4

/
这个相对来说真的简单，可能是老师最后的仁慈了（笑）。记住阶码的值的概念，然后讨论一下太大溢出和太小无法表示的情况就ok啦！

/* * 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 res = x + 127;if (res >= 255) return 0x7f800000;if (res < 0) return 0;return res << 23;
}

Score Rating Errors Function
4 4 0 floatPower2
Total points: 4/4