https://hakula-1257872502.file.myqcloud.com/images/article-covers/csapp.webp

CS:APP - Data Lab

Hakula收录于笔记

2019-10-09 约 3436 字预计阅读 7 分钟 0 次阅读

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

实验简介

参见

CS:APP3e, Bryant and O’Hallaron - CMU

实验报告

1 bitAnd

题目

x & y using only ~ and |.

1.1 思路

利用 De Morgan’s laws 即可。

1.2 解答

1
2
3
4
int bitAnd(int x, int y) {
    /* De Morgan's laws */
    return ~((~x) | (~y));
}

2 getByte

题目

Extract byte $n$ from word $x$.
Bytes numbered from $0$ (LSB) to $3$ (MSB).

2.1 思路

$1\ \mathrm{byte} = 8\ \mathrm{bit}$，因此将 $x$ 右移 $8n$ 位后，$x$ 最低的字节就是我们需要提取的 byte $n$。之后利用掩码 $\mathtt{0xFF}$ 提取即可。

2.2 解答

1
2
3
4
int getByte(int x, int n) {
    /* x AND 0xff returns the lowest byte of x. */
    return (x >> (n << 3)) & 0xff;
}

3 logicalShift

题目

Shift $x$ to the right by $n$, using a logical shift.
Can assume that $0\le n\le 31$.

3.1 思路

负数右移时会在高位补 $1$，因此需要用掩码提取最低的 $(32-n)$ 位。这里将 $\mathtt{0x1}$ 左移 $31$ 位到最高位，然后右移 $(n-1)$ 位得到一个高位 $n$ 个 $1$、低位 $(32-n)$ 个 $0$ 的二进制数，最后取反即得到我们所需的掩码。

3.2 解答

1
2
3
4
5
6
7
8
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

题目

Returns count of number of $1$’s in word.

4.1 思路

因为不允许使用循环遍历，这里采用了分治法的思想。¹

我们先将这 $32$ 位数分成左右两组，每组 $16$ 位；然后将每组 $16$ 位数再分成左右两组，每组 $8$ 位数；以此类推，一直细分到每组 $1$ 位数。

我们知道每组中 $1$ 的个数 $=$ 左组 $1$ 的个数 $+$ 右组 $1$ 的个数，因此只要每次将相邻的左组加到右组上，即可得到这组中 $1$ 的个数。而对于最开始只有 $1$ 位数的组，其中 $1$ 的个数就等于这个数本身。

例如：

1
2
3
4
5
     1 0 1 1 0 0 0 1
=>   1+0 1+1 0+0 0+1
=>    01 +10  00 +01
=>      0011   +0001
=>          00000100 (= 4)

在具体实现中，由于常数限定在 $[\mathtt{0x0},\mathtt{0xFF}]$ 的范围，因此做了一些额外处理。

4.2 解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

题目

Compute !x without using !.

5.1 思路

只需判断原数是否为 $0$。这里将 $x$ 每次压缩成原来位数的一半，用 $\mathrm{OR}$ 运算来保留所有的 $1$。如果最终得到的 $1$ 位数为 $0$ 即表示 $x = 0$，否则 $x\ne 0$。最后取反并利用掩码 $\mathtt{0x1}$ 提取结果即可。

5.2 解答

1
2
3
4
5
6
7
8
9
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

题目

Return minimum two’s complement integer.

6.1 思路

由二补码的规则易知 $\mathrm{tmin} = \mathtt{0x80000000}$。由于常数限定在 $[\mathtt{0x0},\mathtt{0xFF}]$ 的范围，因此采用 0x1 << 31 来表示。

6.2 解答

1
2
3
4
int tmin(void) {
    /* tmin = 0x80000000 */
    return 0x1 << 31;
}

7 fitsBits

题目

Return $1$ if $x$ can be represented as an $n$-bit, two’s complement integer. $(1\le n\le 32)$

7.1 思路

如果一个非负数 $x$ 可以表示成 $n$ 位二补码的形式，那么 $x$ 最高的 $1$ 必然不能高于第 $(n-1)$ 位。因此如果对 $x$ 右移 $(n-1)$ 位所得的结果为 $0$，即表示 $x$ 是符合要求的。

为了方便起见，将负数直接取反。如果取反后的 $\mathrm{NOT}\ x$ 能表示成 $n$ 位二补码的形式，那么 $x$ 也同样能表示。这是因为 $x$ 的范围 $[\mathtt{0x80000000},\mathtt{0xFFFFFFFF}]$ 与 $\mathrm{NOT}\ x$ 的范围 $[\mathtt{0x00000000},\mathtt{0x7FFFFFFF}]$ 一一对应，而后者正是非负数的范围。

因为不允许使用条件语句，如何将负数取反的同时保持正数不变，这里用了一个 trick，详见代码部分。因为不允许使用减号，这里就用 $\mathrm{NOT}\ 0$ 来表示 $-1$ 了。

7.2 解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 become 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

题目

Compute $x / 2^n$, for $0\le n\le 30$.
Round toward zero.

8.1 思路

非负数直接右移即可；负数直接右移会向下取整，但要求是向 $0$ 取整（向上取整），因此需要加上一个偏移量。具体处理方式类似于十进制里对进一法的处理，即在原数上先加 $2^n - 1$，这样即可确保右移 $n$ 位后的结果是向上取整。

8.2 解答

1
2
3
4
5
6
7
8
9
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

题目

Return $-x$.

9.1 思路

取反加一即可。

9.2 解答

1
2
3
int negate(int x) {
    return ~x + 1;
}

10 isPositive

题目

Return $1$ if $x > 0$, return $0$ otherwise.

10.1 思路

关键在于对 $0$ 的处理，直接返回 !(x >> 31) 对于 $0$ 是错误的。

我们发现：

	正数	0
`!(x >> 31)`	1	1
`!x`	0	1
期望结果	1	0

可见这里存在一个 $\mathrm{XOR}$ 的关系，于是就得到解答。

10.2 解答

1
2
3
4
5
6
7
8
int isPositive(int x) {
    /*
     * Positive numbers: !(x >> 31) = 1, !x = 0, expected 1
     * Negative numbers: !(x >> 31) = 0, !x = 0, expected 0
     * Zero:             !(x >> 31) = 1, !x = 1, expected 0
     */
    return (!(x >> 31)) ^ (!x);
}

11 isLessOrEqual

题目

If $x\le y$ then return $1$, else return $0$.

11.1 思路

首先判断 $x$ 和 $y$ 的符号是否相同，因为如果符号不同，相减可能导致溢出问题，从而得出错误的结果。

如果 $x$ 和 $y$ 同号，那么 $y-x$ 不会导致溢出，我们判断 $y-x$ 的符号即可。如果 $y-x$ 为非负数则结果为真，否则为假。

如果 $x$ 和 $y$ 异号，那么负数必然小于非负数，我们判断 $x$ 的符号即可。如果 $x$ 为负数则结果为真，否则为假。

11.2 解答

1
2
3
4
5
6
7
8
9
int isLessOrEqual(int x, int y) {
    /*
     * If x and y have the same sign, judge the sign of (y - x);
     * otherwise, the negative one is smaller 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

题目

Return $\lfloor \log_2{x}\rfloor$, where $x>0$.

12.1 思路

目标是找到 $x$ 最高的 $1$ 所在的位置。

因为不允许使用循环遍历，这里采用二分查找¹，详见代码部分。

12.2 解答

1
2
3
4
5
6
7
8
9
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

题目

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 $\mathrm{NaN}$, return argument.

13.1 思路

关键在于判断原数是否为 $\mathrm{NaN}$，是则直接返回，否则将符号位（最高位）取反后返回。

当 $f$ 的 exponent bits 全为 $1$ 且 fraction bits 不全为 $0$ 时，$f$ 即为 $\mathrm{NaN}$。²

13.2 解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
unsigned float_neg(unsigned uf) {
    /*
     * If uf is NaN, return uf;
     * otherwise, 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

题目

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.1 思路

为了方便起见，先将负数转化为其相反数。为此需要将 INT_MIN（$\mathtt{0x80000000}$）作为特殊情况处理。同时由于整数中只有 $0$ 是 subnormal number²，因此也作为特殊情况处理。

此后先将 fraction bits 顶到最高位，这样做的好处是之后将有效位数部分截断时，方便判断是否需要进位。

而本题的关键正是这个进位判断。需要注意的是，二进制进位时不是只看被舍去部分的最高位，而是整个被舍去部分（有时也可以只看最高两位）和被保留部分的最低位。在本题中，因为已经将 fraction bits 顶到最高位，因此最低 $8$ 位就是被舍去的部分（$32$ 位数中，fraction bits 最多只能有 $23$ 位）。于是，进位判断的条件为：

如果被舍去部分大于 $\mathtt{0x80}$，则需要进位；
如果被舍去部分等于 $\mathtt{0x80}$，且被保留部分最低位为 $1$，则需要进位；
其余情况不进位。

解决了进位问题后，其余问题都不是问题，详见代码部分。

14.2 解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
unsigned float_i2f(int x) {
    unsigned int_min = 0x80000000;
    unsigned exp     = 31;
    unsigned carry   = 0;
    unsigned new_x   = 0;

    /* Deal with 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

题目

Return bit-level equivalent of expression $2f$ 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 $\mathrm{NaN}$, return argument.

15.1 思路

只需要处理一些特殊情况即可。

当 $f$ 是 $\pm 0$ 时，直接返回；
当 $f$ 是 $\mathrm{NaN}$ 时，直接返回；
当 $f$ 是 subnormal number 时，直接将 fraction bits 左移 $1$ 位后返回³；
其余情况，将 exponent bits 加 $1$。

15.2 解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
unsigned float_twice(unsigned uf) {
    /* Deal with 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 / -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);
}

运行结果

dlc

1
2
./dlc bits.c
./dlc bits.c -e

/posts/note/csapp/data-lab/assets/dlc.webp — dlc 检查结果

btest

./btest

测试环境

Ubuntu 18.04.3 LTS (GNU/Linux 5.0.0-29-generic x86_64)
GCC 7.4.0
GNU Make 4.1

心得体会

有几个题确实难，想了几个小时都想不出来，只好去参考网上的思路。其实从学习效率的角度，感觉毫无头绪的题，在那边硬想也只不过是一种「自我感动」的浪费时间。做这个 Lab 总共耗时 3 天，其中不少时间就是这样无意义地浪费掉了，很不值得。

参考资料

参考了 @codinfox 的思路。 ↩︎ ↩︎
参见 IEEE 二进制浮点数算术标准。 ↩︎ ↩︎
无需担心溢出到 exponent bits 的问题，这是 IEEE 标准所保证的。 ↩︎

目录

CS:APP - Data Lab

实验简介

实验报告

1 bitAnd

1.1 思路

1.2 解答

2 getByte

2.1 思路

2.2 解答

3 logicalShift

3.1 思路

3.2 解答

4 bitCount

4.1 思路

4.2 解答

5 bang

5.1 思路

5.2 解答

6 tmin

6.1 思路

6.2 解答

7 fitsBits

7.1 思路

7.2 解答

8 divpwr2

8.1 思路

8.2 解答

9 negate

9.1 思路

9.2 解答

10 isPositive

10.1 思路

10.2 解答

11 isLessOrEqual

11.1 思路

11.2 解答

12 ilog2

12.1 思路

12.2 解答

13 float_neg

13.1 思路

13.2 解答

14 float_i2f

14.1 思路

14.2 解答

15 float_twice

15.1 思路

15.2 解答

运行结果

dlc

btest

测试环境

心得体会

参考资料