Introduction to Computer Systems I @ Fudan University, fall 2019.
CS:APP Data Lab 解题报告
仅供参考。[^1]
实验简介
See: README or all materials Here
解题报告
1. bitAnd
1.1 要求
x & y using only ~ and |
1.2 思路
利用 De Morgan 定律即可。
1.3 解答
int bitAnd(int x, int y) {
/* De Morgan's Laws */
return ~((~x) | (~y));
}
2. getByte
2.1 要求
Extract byte n from word x
Bytes numbered from 0 (LSB) to 3 (MSB)
2.2 思路
1 byte = 8 bits,因此将 x 右移 (n * 8) 位后,x 最低的字节就是我们需要提取的 byte n。之后利用掩码 0xff 提取即可。
2.3 解答
int getByte(int x, int n) {
/* x AND 0xff returns the lowest byte of x */
return (x >> (n << 3)) & 0xff;
}
3. logicalShift
3.1 要求
Shift x to the right by n, using a logical shift
Can assume that 0 <= n <= 31
3.2 思路
负数右移时会在高位补 1,因此需要用掩码提取最低的 (32 - n) 位。这里将 0x1 左移 31 位到最高位,然后右移 (n - 1) 位得到一个高位 n 个 1、低位 (32 - n) 个 0 的二进制数,最后取反即得到我们所需要的掩码。
3.3 解答
int logicalShift(int x, int n) {
/*
* Mask the highest n bits after doing right shifts,
* especially for negative numbers
*/
int mask = ~(((0x1 << 31) >> n) << 1);
return (x >> n) & mask;
}
4. bitCount
4.1 要求
Returns count of number of 1's in word
4.2 思路
因为不能用循环遍历,这里采用了分治法的思想。
我们先将这 32 位数分成左右两组,每组 16 位;然后将每组 16 位数再分成左右两组,每组 8 位数;以此类推,一直细分到每组 1 位数。
我们知道每组中 1 的个数 = 左组 1 的个数 + 右组 1 的个数,因此只要每次将相邻的左组加到右组上,即可得到这组中 1 的个数。而对于最开始只有 1 位数的组,其中 1 的个数就等于这个数本身。
举例说明:
1 0 1 1 0 0 0 1
=> 1+0 1+1 0+0 0+1
=> 01 +10 00 +01
=> 0011 +0001
=> 00000100 (= 4)
在具体实施中,由于常数限定在 [0, 0xff] 的范围,因此做了一些额外处理。
4.3 解答
int bitCount(int x) {
/* Add adjacent bits together each time */
int mask16 = 0x55 | (0x55 << 8);
int mask8 = 0x33 | (0x33 << 8);
int mask4 = 0x0f | (0x0f << 8);
int mask2 = 0xff | (0xff << 16);
int mask1 = 0xff | (0xff << 8);
mask16 = mask16 | (mask16 << 16);
mask8 = mask8 | (mask8 << 16);
mask4 = mask4 | (mask4 << 16);
x = (x & mask16) + ((x >> 1) & mask16);
x = (x & mask8) + ((x >> 2) & mask8);
x = (x & mask4) + ((x >> 4) & mask4);
x = (x & mask2) + ((x >> 8) & mask2);
x = (x & mask1) + ((x >> 16) & mask1);
return x;
}
5. bang
5.1 要求
Compute !x without using !
5.2 思路
只需要判断原数是否为 0。这里将 x 每次压缩成原来位数的一半,用 OR 运算来保留所有的 1。如果最终得到的 1 位数为 0 即表示 x = 0,否则 x ≠ 0。最后取反并利用掩码 0x1 提取结果即可。
5.3 解答
int bang(int x) {
/* Compress the original number to 1 bit */
x = x | (x >> 16);
x = x | (x >> 8);
x = x | (x >> 4);
x = x | (x >> 2);
x = x | (x >> 1);
return (~x) & 0x1;
}
6. tmin
6.1 要求
Return minimum two's complement integer
6.2 思路
根据二补码的规则容易知道 tmin = 0x80000000。由于常数限定在 [0, 0xff] 的范围,因此采用 (0x1 << 31) 来表示。
6.3 解答
int tmin(void) {
/* tmin = 0x80000000 */
return 0x1 << 31;
}
7. fitsBits
7.1 要求
Return 1 if x can be represented as an n-bit, two's complement integer. (1 <= n <= 32)
7.2 思路
如果一个非负数 x 可以被表示成 n 位二补码的形式,那么 x 最高的 1 必然不能高于第 (n - 1) 位。因此如果对 x 右移 (n - 1) 位所得的结果为 0,即表示 x 是符合要求的。
为了方便起见,将负数直接取反。如果取反后 ~x 能被表示成 n 位二补码的形式,那么 x 也同样能被表示。这是因为 x 的范围 [0x80000000, 0xffffffff] 与 ~x 的范围 [0x00000000, 0x7fffffff] 一一对应,而后者正是非负数的范围。
因为不能使用条件语句,如何将负数取反,同时保持正数不变,这里用了一个 trick。详见代码部分。
7.3 解答
int fitsBits(int x, int n) {
/*
* Convert x to a non-negative number in advance for convenience. If a
* non-negative number can be represented as an n-bit, two's complement
* integer, it should becomes 0 after doing right shift by (n - 1) times.
*/
int sign = x >> 31;
x = (x & ~sign) + (~x & sign); // x = x < 0 ? ~x : x;
return !(x >> (n + ~0));
}
8. divpwr2
8.1 要求
Compute x / (2 ^ n), for 0 <= n <= 30
Round toward zero
8.2 思路
非负数直接右移即可;负数直接右移将会向下取整,但要求是向 0 取整(即向上取整),因此需要加上一个偏移量。具体的处理方式类似于十进制中对进一法的处理,即在原数上先加 (2 ^ n - 1),这样即可确保右移 n 位后结果向上取整。
8.3 解答
int divpwr2(int x, int n) {
/*
* Positive numbers: x >> n
* Negative numbers: (x + (1 << n) - 1) >> n (to round toward 0)
*/
int sign = x >> 31;
int offset = sign & ((0x1 << n) + ~0);
return (x + offset) >> n;
}
9. negate
9.1 要求
Return -x
9.2 思路
取反加一即可。
9.3 解答
int negate(int x) {
/* Obvious solution */
return ~x + 1;
}
10. isPositive
10.1 要求
Return 1 if x > 0, return 0 otherwise
10.2 思路
关键在于对 0 的处理,这使得直接返回 !(x >> 31) 对于 0 是错误的。
我们发现:
正数 | 负数 | 0 | |
---|---|---|---|
!(x >> 31) | 1 | 0 | 1 |
!x | 0 | 0 | 1 |
result | 1 | 0 | 0 |
可见这是一个 XOR 的关系,即结果可表示为 (!(x >> 31)) ^ (!x)。
10.3 解答
int isPositive(int x) {
/*
* Positive numbers: !(x >> 31) = 1, !x = 0, result = 1
* Negative numbers: !(x >> 31) = 0, !x = 0, result = 0
* Zero: !(x >> 31) = 1, !x = 1, result = 0
*/
return (!(x >> 31)) ^ (!x);
}
11. isLessOrEqual
11.1 要求
If x <= y then return 1, else return 0
11.2 思路
首先判断 x 和 y 的符号是否相同,因为如果符号不同,相减可能导致溢出问题,从而使结果不正确。
如果 x 和 y 同号,那么 (y - x) 不会导致溢出,我们判断 (y - x) 的符号即可。如果 (y - x) 为非负数,则结果为真,否则为假。
如果 x 和 y 异号,那么负数必然小于非负数,我们判断 x 的符号即可。如果 x 为负数,则结果为真,否则为假。
11.3 解答
int isLessOrEqual(int x, int y) {
/*
* If x and y have the same sign: Judge the sign of (y - x);
* Else: The negative one is less than the positive one
*/
int sign_diff = x ^ y;
int diff = y + ~x + 1;
return (((sign_diff & x) | (~sign_diff & ~diff)) >> 31) & 0x1;
}
12. ilog2
12.1 要求
Return floor(log base 2 of x), where x > 0
12.2 思路
目标是找到 x 最高的 1 所在的位置。
因为不能用循环遍历,这里采用二分查找。详见代码部分。
12.3 解答
int ilog2(int x) {
/* Find the highest 1 in x through binary search */
int result = (!!(x >> 16)) << 4;
result += (!!(x >> (result + 8))) << 3;
result += (!!(x >> (result + 4))) << 2;
result += (!!(x >> (result + 2))) << 1;
result += (!!(x >> (result + 1)));
return result;
}
13. float_neg
13.1 要求
Return bit-level equivalent of expression -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 representations of single-precision floating point values.
When argument is NaN, return argument.
13.2 思路
关键在判断原数是否为 NaN,是则直接返回,否则将符号位(最高位)取反后返回。
当 uf 的 exponent bits 全为 1 且 fraction bits 不全为 0 时,uf 即为 NaN。[^2]
13.3 解答
unsigned float_neg(unsigned uf) {
/*
* If uf is NaN: Return uf;
* Else: Convert the sign bit to the opposite
*/
unsigned sign_mask = 0x1 << 31;
unsigned exp_mask = 0xff << 23;
unsigned frac_mask = 0x7fffff;
unsigned exp = uf & exp_mask;
unsigned frac = uf & frac_mask;
if (exp == exp_mask && frac) return uf; // uf is NaN
return uf ^ sign_mask;
}
14. float_i2f
14.1 要求
Return bit-level equivalent of expression (float) x.
Result is returned as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point values.
14.2 思路
为了方便起见,先将负数转化为其相反数。为此需要将 INT_MIN (0x80000000) 作为特殊情况处理。同时由于整数中只有 0 是 subnormal number [^2],因此也作为特殊情况处理。
此后先将 fraction bits 顶到最高位,这样做的好处是之后将有效位数部分截断时,方便判断是否需要进位。
而本题的关键正是这个进位判断。需要注意的是,二进制进位时不是只看被舍去部分的最高位,而是整个被舍去部分(有时也可以只看最高两位)和被保留部分的最低位。在本题中,因为已经将 fraction bits 顶到最高位,因此最低 8 位就是被舍去的部分(32 位数中,fraction bits 最多只能有 23 位)。于是,进位判断的条件为:
如果被舍去部分大于 0x80,则需要进位;
如果被舍去部分等于 0x80,且被保留部分最低位为 1,则需要进位;
其余情况不进位。
解决了进位问题后,其余问题都不是问题。详见代码部分。
14.3 解答
unsigned float_i2f(int x) {
unsigned int_min = 0x80000000;
unsigned exp = 31;
unsigned carry = 0;
unsigned new_x = 0;
/* Special cases */
if (x == 0) return 0;
if (x == int_min) return 0xcf000000;
/* Convert x to positive for convenience */
if (x < 0) {
x = -x;
/* Set the sign bit */
new_x |= int_min;
}
/* Move the fraction bits to the top */
while (!(x & int_min)) {
x <<= 1;
--exp;
}
/* Set the exponent bits */
new_x |= (exp + 127) << 23;
/* Judge whether carry is 0 or 1 */
if ((x & 0x1ff) == 0x180 || (x & 0xff) > 0x80) carry = 1;
// else carry = 0;
/* Set the fraction bits */
new_x |= (x >> 8) & 0x7fffff;
new_x += carry;
return new_x;
}
15. float_twice
15.1 要求
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.
15.2 思路
只需要处理一些特殊情况即可。
当 uf 是 ±0 时,直接返回;
当 uf 是 NaN 时,直接返回;
当 uf 是 subnormal number 时,直接将 fraction bits 左移后返回(无需担心溢出到 exponent bits 的问题,这是 IEEE 制定的标准所保证的 [^2]);
其余情况,将 exponent bits 加一。
15.3 解答
unsigned float_twice(unsigned uf) {
/* Carefully deal with the special cases */
unsigned sign_mask = 0x1 << 31;
unsigned exp_mask = 0xff << 23;
unsigned sign = uf & sign_mask;
unsigned exp = uf & exp_mask;
if (uf == 0 || uf == sign_mask) return uf; // uf is +-0
if (exp == exp_mask) return uf; // uf is NaN
if (exp == 0) return (uf << 1) | sign; // uf is a subnormal number
return uf + (0x1 << 23);
}
运行结果
Checking with the dlc compiler
./dlc bits.c
./dlc bits.c -e
Testing with btest
./btest
测试环境
- OS: Ubuntu 18.04.3 LTS (GNU/Linux 5.0.0-29-generic x86_64)
- Compiler: gcc version 7.4.0
- Using GNU Make 4.1
心得体会
有几个题确实难,想了几个小时都想不出来,只好去参考网上的思路。其实从学习效率的角度,感觉自己毫无头绪的题,在那边硬想只不过是一种「自我感动」的浪费时间。做这个 Lab 总共耗时 3 天,其中不少时间就是这样无意义地浪费掉了,很不值得。
参考资料
[^1]: 15213-labs/bits.c at master · codinfox/15213-labs - GitHub
[^2]: Single-precision floating-point format - Wikipedia
版权声明:本文为原创文章,版权归 Hakula 所有。
本文链接:https://hakula.xyz/csapp/datalab.html
本文采用 CC BY-NC-SA 4.0 许可协议 进行许可。