CSAPP深入理解计算机系统实验代码
2021/10/22 23:15:43
本文主要是介绍CSAPP深入理解计算机系统实验代码，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
CSAPP-Labs
本文用来记录我的CSAPP实验代码，坚持坚持坚持！
Lab网址：http://csapp.cs.cmu.edu/3e/labs.html , 下载Self-Study Handout
网课：https://www.bilibili.com/video/BV1iW411d7hd
我的代码仓库：https://github.com/Lyb-code/CSAPP-Labs
Lab1 DataLab
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) {
int z = x & y; // Bit[1, 1] -> 1
int w = (~x) & (~y); // Bit[0, 0] -> 1
return (~z) & (~w); // Bit[1, 0], [0, 1] -> 1
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
int x = (0x80) << 24;
return x;
}
//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) { // Tmax + 1 = 0x10000000 = ~Tmax. Remember to exclude the case of x = -1.
int k = x + 1;
int m = k ^ (~x);// when x = -1 or Tmax, m = 0
return (!!k) & !m;
}
/*
* 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 k = 0xAA;
k = (k << 8) | k;
k = (k << 16) | k;//0xAAAAAAAA
x = x & k; // remove all even-numbered bits of x
return ! (x ^ k);
}
/*
* 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 a = (x ^ 0x30) >> 4;
int b = (x & 0x8) >> 3;
int c = (x & 0x4) >> 2;
int d = (x & 0x2) >> 1;
return ! ((a) | (b & c) | (b & d));// return 1 if a = 0 And b & c = 0 And c & d = 0;
}
/*
* 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 a = !x; // [x->a] 0->1, others->0
a = (a << 1 | a);
a = (a << 2 | a);
a = (a << 4 | a);
a = (a << 8 | a);
a = (a << 16 | a);
return ((~a) & y) + (a & z);
}
/*
* 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 k = 0x80 << 24;
int hbx = x & k; // keep only the highest bit of x
int hby = y & k; // keep only the highest bit of y
int hbEqual = !(hbx ^ hby);// if highest bits are equal, return 1
int z = x + (~y) + 1;// x - y;
int ans1 = (!hbEqual) & ((hbx >> 31) & 1);// if hbEqual = 0, use hbx to judge to prevent overflow of z.
int ans2 = hbEqual & (((z >> 31) & 1) | (!(z ^ 0)));
return ans1 + ans2;
}
//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) {
x = (x >> 16) | x;
x = (x >> 8) | x;
x = (x >> 4) | x;
x = (x >> 2) | x;
x = (x >> 1) | x;
return (~x) & 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;
int sign = x>>31; // all 1 or all 0
x = ((~sign) & x) | (sign & (~x));// x < 0 --> ~x ; x > 0 --> x;
b16 = (!!(x >> 16)) << 4;// If the upper 16 bits have 1, at least the lower 16(1<<4) bits are required.
x = x >> b16;
b8 = (!!(x >> 8)) << 3;// If the remaning top 8 bits have 1, at least the lower 8(1<<3) bits are required.
x = x >> b8;
b4 = (!!(x >> 4)) << 2;// narrow the scope
x = x >> b4;
b2 = (!!(x >> 2)) << 1;
x = x >> b2;
b1 = (!!(x >> 1));
x = x >> b1;
return b16 + b8 + b4 + b2 + b1 + x + 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
*/
unsigned floatScale2(unsigned uf) {
int sign = 0x80000000 & uf;
int exp = (0x7f800000 & uf) >> 23;
int frac = 0x7fffff & uf;
if (exp == 0xff) {// NaN and infinity: do nothing
} else if (exp == 0) {// Denormalized value
if ((frac >> 22) == 0) {
frac = frac << 1;
} else {
exp = 1;
frac = (frac << 1) & 0x007fffff;
}
} else {//Normalized value
exp += 1;
}
uf = sign | (exp << 23) | frac;
return uf;
}
/*
* 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 sign = uf >> 31;
int exp = (0x7f800000 & uf) >> 23;
int bias = (1 << 7) - 1;
int E = 0, ans = 0;
int frac = 0x7fffff & uf;
if (exp == 0xff) {// NaN and infinity
return 0x80000000u;
} else if (exp == 0) {// Denormalized value
E = 1 - bias;
} else {//Normalized value
E = exp - bias;
frac |= 0x800000;
}
//printf("%d %d \n", E, frac);
if (E > 30) { // prevent left shift overflow
return 0x80000000u;
} else if (E > 23) {
ans = frac << (E - 23);
} else if (E > -9) {// prevent the right shift length from being greater than 32
ans = frac >> (23 - E);
}
if (sign) {
ans = -ans;
}
return ans;
}
/*
* 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 bias = 127;
if (x > 128) {
return 0x7f800000;
} else if (x > -150) {
x += bias;
if (x >= 0) { // Normalize
return x << 23;
} else { // Denormalize
return 1 << (23 + x);
}
} else {
return 0;
}
}
2 代码说明
-
allOddBits构造了一个奇数位全1的掩码 k
-
isAsciiDigit的思路是看形参x是不是"0x3m"的形式，且m处于0到9之间。
我觉得这样做的推广性不强，当范围变大之后就能难再这样做。CSAPP 之 DataLab详解链接提供了一个更有推广性的解，如下：
int isAsciiDigit(int x) { int sign = 0x1<<31; int upperBound = ~(sign|0x39);//加上比0x39大的数后符号由正变负 int lowerBound = ~0x30;//加上小于等于0x30的值时是负数 upperBound = sign&(upperBound+x)>>31; lowerBound = sign&(lowerBound+1+x)>>31; return !(upperBound|lowerBound); } -
conditional的思路是正确的，不过可以更简洁。!!x挺好用的。
int conditional(int x, int y, int z) { x = !!x; // 0->0, others->1 x = ~x + 1; //0的补码是全0，1的补码是全1 return (x & y) + ((~x) & z); } -
isLessOrEqual思路：符号不同，正数大；符号相同，看差值符号
-
logicalNeg思路：使用或操作，把所有的1都压缩到第一位。
可以更简洁，如下。利用了补码的性质：0和tmin(1后面全0)的补码是本身，其余整数的补码是自己的相反数。只有当x为0时，x和其补码的或操作得到的符号位才会是0，其余情况都是1.
int logicalNeg(int x) { return ((x | (~x + 1)) >> 31) & 1 ^ 1; } -
howManyBits，卡住我的一题。思路就是找与符号位不同的最高位n，然后用该位数加1得n+1.
首先，做了个处理，如果x的符号位为0，x不变；否则对x取反。解题目标简化为：找最高的1位的位数n，然后用该位数加1。
不断地判断x的最高16、8、4、2、1位和最低1位是否有1，用**!!**可以很方便判断二进制数是否含有1。如果最高16位有1，那么最低16位肯定需要，答案加上16，并将x右移16位，查看接下来的最高8位…如果最高16位没有1，那么x不右移，直接看x低16位的最高8位…依次类推。实现是很巧妙的，我开始没想到。
-
floatScale2、floatFloat2Int和floatPower2考察浮点数，做起来比想象的顺利，因为可以用if、while等操作符了。关键是对浮点数的结构有了解，知道Normolize Value和Denormolize Value是啥，可以看看网课或书本，实现起来就能分情况讨论了。具体见代码和注释。
当位移操作的长度大于等于窗口长度时，得到的移动量为（位移长度%窗口长度），这是看弹幕知道的，看书时可以再验证。Undefined Behavior: Shift amount < 0 or ≥ word size。因此，不要做出移位数量小于0或大于窗口长度的操作。我在floatFloat2Int方法中排除了这两种情况。
-
其他函数，直接看代码，参考注释即可
3 总结
CMU老师说“任何形式的搜索都是作弊”，因此实验一定要自己做！！！！先找资料、看网课，不到最后一步，不看别人的代码。
除了howManyBits外，所有的问题都是我自己解决的，对位操作、浮点型的表示更加熟悉了，还是不错的。howManyBits实在没有思路了，借鉴了网友的解答。所以，作弊了一小点点(4/36)。
注意实验总结，享受思考总结的过程，多学习优秀的代码。
本次实验耗时：22.5h。
这篇关于CSAPP深入理解计算机系统实验代码的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-26RocketMQ入门指南：搭建与使用全流程详解
- 2024-11-26RocketMQ入门教程：轻松搭建与使用指南
- 2024-11-26手写RocketMQ：从入门到实践的简单教程
- 2024-11-25【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版
- 2024-11-23增量更新怎么做？-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些？-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗？-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
