Hakula

CS:APP Data Lab 解题报告
Introduction to Computer Systems I @ Fudan University, fa...
扫描右侧二维码阅读全文
09
2019/10

CS:APP Data Lab 解题报告

  1.  首页 
  2. 正文  
    3. 分享到：

Introduction to Computer Systems I @ Fudan University, fall 2019.

CS:APP Data Lab 解题报告

如需参考请务必注明 Reference

仅供参考。[^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

Screenshot of dlc

Testing with btest

./btest

Screenshot of 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 许可协议 进行许可。

最后修改：2020-04-14
© 著作权归作者所有
如果我的文章对你有帮助，欢迎赞赏，谢谢你！111

发表评论