CSAPP DataLab 题解
source link: http://claude-ray.com/2019/10/02/csapp-datalab/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
DataLab
近来开始读 CS:APP3e 第二章，但干看书做课后题太乏味，于是提前把 DataLab 拉出来练练。不一定是优解，趁热记录一下思路吧。
如果读者是那种还没做完 lab 就想借鉴答案的，还请收手，坚持独立完成吧，正如课程作者所说，
Don't cheat, even the act of searching is checting.
bitXor
/*
* 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));
}
简单的公式可以写作 (x & y) | (~x & y) ，但题目要求只能用 ~ & 两种操作，换句话就是考察用 ~ & 来实现 | 操作，和逻辑与或非类似。
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1 << 31;
}
这个题目就是计算出 0x80000000 ，基本的移位操作即可，不用复杂化。
isTmax
/*
* 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 !(~(1 << 31) ^ x);
}
上面已经知道怎么获取 TMIN，TMAX 可以用 ~TMIN 表示，因此主要考察两个数是否相等 —— ^。
感谢 @nerrons 兄指正
前面的解法忽略了操作符的限制，是不合题意的。故更换思路：由于 TMAX + 1 可得到 TMIN，若 x 为 TMAX，则 x + 1 + x 结果为 0。
但直接这样写无法通过检测程序，是因为 0xffffffff 同样满足 x + 1 + x 为 0 的特性，需要将该情况排除。
int isTmax(int x) {
return !(~((x + 1) + x) | !(x + 1));
}
allOddBits
/*
* 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 odd = (0xAA << 24) + (0xAA << 16) + (0xAA << 8) + 0xAA;
return !((x & odd) ^ odd);
}
先构造 0xAAAAAAAA，利用 & 操作将所有奇数位提出来，再和已构造的数判等。
negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
二进制基础扎实的话，可以秒出结果。
isAsciiDigit
/*
* 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) {
/* (x - 0x30 >= 0) && (0x39 - x) >=0 */
int TMIN = 1 << 31;
return !((x + ~0x30 + 1) & TMIN) & !((0x39 + ~x + 1) & TMIN);
}
主要思路可以用逻辑运算表示，(x - 0x30 >= 0) && (0x39 - x) >=0，这里新概念是如何判断数值是否小于 0。
conditional
/*
* 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 f = ~(!x) + 1;
int of = ~f;
return ((f ^ y) & of) | ((of ^ z) & f);
}
这里我用 ~(!x) + 1 构造了 x 的类布尔表示，如果 x 为真，表达式结果为 0，反之表达式结果为 ~0。
isLessOrEqual
/*
* 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) {
/* (y >=0 && x <0) || ((x * y >= 0) && (y + (-x) >= 0)) */
int signX = (x >> 31) & 1;
int signY = (y >> 31) & 1;
int signXSubY = ((y + ~x + 1) >> 31) & 1;
return (signX & ~signY) | (!(signX ^ signY) & !signXSubY);
}
核心是判断 y + (-x) >= 0。一开始我做题时被 0x80000000 边界条件烦到了，所以将其考虑进了判断条件。
具体做法是判断 Y 等于 TMIN 时返回 0，X 等于 TMIN 时返回 1。此外也考虑了若 x 为负 y 为 正返回 1，x 为正 y 为负返回 0。
这样想得太复杂了，使用的操作有点多，而题目对 ops 限制是 24，担心过不了 dlc 的语法检查。 所以又花更多时间想出更简单的方法。用逻辑操作可以写作 (y >=0 && x <0) || ((x * y >= 0) && (y + (-x) >= 0))。不过我后来在 linux 上运行了一下第一种方法，dlc 并没有报错。
logicalNeg
/*
* 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 sign = (x >> 31) & 1;
int TMAX = ~(1 << 31);
return (sign ^ 1) & ((((x + TMAX) >> 31) & 1) ^ 1);
}
x 小于 0 时结果为 1，否则检查 x + TMAX 是否进位为负数。
howManyBits
/* 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) & 1;
int f = ~(!sign) + 1;
int of = ~f;
/*
* NOTing x to remove the effect of the sign bit.
* x = x < 0 ? ~x : x
*/
x = ((f ^ ~x) & of) | ((of ^ x) & f);
/*
* We need to get the index of the highest bit 1.
* Easy to find that if it's even-numbered, `n` will lose the length of 1.
* But the odd-numvered won't.
* So let's left shift 1 (for the first 1) to fix this.
*/
x |= (x << 1);
int n = 0;
// Get index with bisection.
n += (!!(x & (~0 << (n + 16)))) << 4;
n += (!!(x & (~0 << (n + 8)))) << 3;
n += (!!(x & (~0 << (n + 4)))) << 2;
n += (!!(x & (~0 << (n + 2)))) << 1;
n += !!(x & (~0 << (n + 1)));
// Add one more for the sign bit.
return n + 1;
}
这里我利用了之前 conditional 的做法，讲 x 为负的情况排除掉，统一处理正整数。统计位数可以采取二分法查找最高位的 1，但做了几轮测试就会发现二分法存在漏位的问题。
不过这只在偶数位发生，奇数位不受影响。因此为了排除这个影响，我暴力地用 x |= (x << 1) 的办法让最高位的 1 左移 1 位。
floatScale2
/*
* 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 >> 23) & 0xFF;
// Special
if (exp == 0xFF)
return uf;
// Denormalized
if (exp == 0)
return ((uf & 0x007fffff) << 1) | (uf & (1 << 31));
// Normalized
return uf + (1 << 23);
}
只需要简单地取出指数部分，甚至不需要拆解，排除 INF、NaN、非规格化的情况之后，剩下规格化的处理是指数部分的位进一。
floatFloat2Int
/*
* 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 TMIN = 1 << 31;
int exp = ((uf >> 23) & 0xFF) - 127;
// Out of range
if (exp > 31)
return TMIN;
if (exp < 0)
return 0;
int frac = (uf & 0x007fffff) | 0x00800000;
// Left shift or right shift
int f = (exp > 23) ? (frac << (exp - 23)) : (frac >> (23 - exp));
// Sign
return (uf & TMIN) ? -f : f;
}
首先拆分单精度浮点数的指数和基数，指数部分减去 127 偏移量，用来排除临界条件。大于 31 时，超过 32 位 Two’s Complement 的最大范围，小于 0 则忽略不计，根据题意分别返回 0x80000000 和 0。
之后根据指数部分是否大于 23 来判断小数点位置。如果大于，说明小数部分全部在小数点左边，需要左移；如果小于则需要右移。最后补上符号位。
floatPower2
/*
* 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 exp = x + 127;
// 0
if (exp <= 0)
return 0;
// INF
if (exp >= 0xFF)
return 0x7f800000;
return exp << 23;
}
加 127 得到指数阶码，超过表示范围则返回 0 和 INF。由于小数点后面都是 0，只需左移指数部分。
现在 Mac 已无法运行 32 位的代码检查工具 dlc，不过可以先跑逻辑测试，等写完再放到 Linux 机跑一遍 dlc 测试。
原以为这点知识在学校掌握得还可以，随书习题和前几道 lab 也的确简单，实际做到后面有许多卡壳的点，浮点数的概念都模糊了，真是一边翻书一边做，快两天才完成。书本的这章我还是甭跳了，继续刷去吧。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK