CSAPP Data Lab

2020-07-02

Data Lab 的题1，第一眼觉得不难，仔细一看发现限制非常严格，比如只允许部分位运算符等，难度一下子就上去了，所以花了不少时间。

dlc 是 64 位 Linux 程序，使用 ./dlc bits.c 来检查是否符合限制条件。但 Makefile 里却指定了 -m32，可能是考虑到 C 标准只规定 int 至少为 16 位，一些环境可能会生成非 32 位的 int。

Debian 系 64 位 Linux 发行版可以安装：

1

sudo apt install build-essential gcc-multilib g++-multilib

后两个库用于在 64 位环境下编译 32 位程序。

编译并运行测试程序：

1

make clean && make btest && ./btest

bitXor

用 ~ 和 & 来实现 ^：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* 
 * 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));
}

根据

$$A \oplus{B} = A \cdot \overline{B} + \overline{A} \cdot B$$

来实现 ^，再根据

$$A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}}$$

来实现 |。

tmin

求补码最小值，送分题：

bits.c
1
2
3
4
5
6
7
8
9

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
    return 1 << 31;
}

isTmax

判断是否为 int 最大值 0x7fffffff，只允许使用 ! ~ & ^ | +：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/*
 * 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) {
    // If x is 0x7fffffff or 0xffffffff, then i is 1, else 0
    int i = !(~x ^ (x + 1));
    // If x == 0xffffffff, then !~x is 1, else 0
    return i & !!~x;
}

先将问题转化为判断是否为最大值的取反 0x80000000。

利用补码的特性，int 类型可以用取反加一来实现求相反数，而只有两个数满足与自身的相反数相等，即 0 和 0x80000000，其中后者是因为溢出。

再利用逻辑非 ! 排除 0 即可。

allOddBits

判断是否所有奇数位（最低位为 0 位）都为 1：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/* 
 * 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 mask = 0xaa;
    mask = (mask << 8) | mask;
    mask = (mask << 16) | mask;
    return !((x & mask) ^ mask);
}

只允许使用 0 到 0xff 之间的常数，故先用移位求 0xaaaaaaaa，再用 ^ 实现 ==。

negate

求相反数，送分题：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
    return ~x + 1;
}

isAsciiDigit

判断是否为 '0' 到 '9' 之间的 ASCII 码：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/* 
 * 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 i = 0x30, result, mask = 1 << 31;
    // x - 0x30 >= 0
    result = !((x + ~i + 1) & mask);
    i = 0x39;
    // 0x39 - x >= 0
    result = result & !((i + ~x + 1) & mask);
    return result;
}

用求相反数和 + 来实现 -，再取符号位判断其正负。

中间可能有溢出的问题，当 x - 0x30 >= 0 时，可能 x 是一个很小的负数，负负得正产生溢出；当 0x39 - x >= 0 时，不会产生溢出，从而把前一种溢出的情况排除。

conditional

实现三元运算符 a ? b : c：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/* 
 * 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) {
    // x = 0xffffffff or 0
    x = ~!!x + 1;
    return (y & x) | (z & ~x);
}

将非零数转换为掩码 0xffffffff，零转换为掩码 0。

isLessOrEqual

实现 <=：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* 
 * 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 mask = 1 << 31, x_sign = !!(x & mask), y_sign = !!(y & mask), same_sign, le;
    same_sign = !(x_sign ^ y_sign);
    le = !((~x + 1 + y) & mask);
    return (x_sign & !y_sign) | (same_sign & le);
}

问题转化为判断 -x + y 正负。

考虑溢出的问题，取 x、y 的符号位，不同号时直接判断，若同号再判断 -x + y 正负。

logicalNeg

实现逻辑非 !：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/* 
 * 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 | (x >> 1);
    // x = x | (x >> 2);
    // x = x | (x >> 4);
    // x = x | (x >> 8);
    // x = x | (x >> 16);
    // return ~x & 1;

    x = (x | (~x + 1)) >> 31;
    return ~x & 1;
}

第一反应是将首个 1 之后的位全部置 1，若原值非零，则最低位为 1，否则为 0，然后将最低位直接取反即可。

后来发现了一种更简便的方法2，除 0 和 0x80000000 外，一个数必定与其相反数异号，若将 x 与 -x 符号异或，则包括 0x80000000 在内 ，所有非零数异或结果必定为 1。

howManyBits

求补码表示的最少位数：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* 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 n = 0;
    x = x ^ (x >> 31);
    n = n + ((!!(x >> (n + 16))) << 4);
    n = n + ((!!(x >> (n + 8))) << 3);
    n = n + ((!!(x >> (n + 4))) << 2);
    n = n + ((!!(x >> (n + 2))) << 1);
    n = n + ((!!(x >> (n + 1))));
    n = n + (x >> n);
    return n + 1;
}

个人认为是最难的一题，参考了网上的答案3，并对其作了改进。

如何确定最少位数

对于非负数而言，开头连续的 0 可以去掉，只需保留其中最后一个 0 作为符号位即可（否则就会被当成负数了）。例如，0001... 与 01... 表示的是相等值。

对于负数而言，同样从符号位开始，开头连续的 1 只需保留最后一个即可。例如，1110... 与 10... 表示的是相等值。

将负数的情况转化为非负数的情况

x = x ^ (x >> 31) 的作用就是，若 x 为非负，则保持不变，若为负数，则取反。这样无论 x 符号，都可以按照非负数的情况来求解。

求最高位的 1 到最低位的长度，最终结果就是长度 + 1

这个步骤需要一些技巧。

例如，01** **** **** **** **** **** **** **** 的最高位 1 到最低位是 31 位，最终结果就是 32。

观察 31 = 16 + 8 + 4 + 2 + 1，与 x 右移试零的过程一致：首先取 x 最高 16 位，若非零，说明需要 16 位以上的位数，此时 n 计数 + 16，并将低 16 位去掉。接着尝试将低 8 位去掉，以此类推，直到 x 只剩一位。手动模拟一下会更容易理解。

上个步骤已经排除了负数的情况，所以无需担心算数右移高位产生 1 的问题。

01** **** **** **** **** **** **** ****

n = 16

01** **** **** ****

n = 16 + 8

01** ****

n = 16 + 8 + 4

01**

n = 16 + 8 + 4 + 2

01

n = 16 + 8 + 4 + 2 + 0

01

n = 16 + 8 + 4 + 2 + 0 + 1

floatScale2

书上的习题，求 $2x$：

bits.c
 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

/* 
 * 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) {
    unsigned sign = uf & 0x80000000, exp = uf & 0x7f800000, frac = uf & 0x007fffff;
    // 0 or denorm
    if (exp == 0)
        return sign | uf << 1;
    // inf or NaN
    if (exp == 0x7f800000)
        return uf;
    // norm
    exp += 0x00800000;
    // large number becomes inf
    if (exp == 0x7f800000)
        frac = 0;
    return sign | exp | frac;
}

浮点数题目的限制比前面宽松很多，虽然构造复杂一点，只要按照定义求解即可。

floatFloat2Int

书上的习题，float 转换为 int：

bits.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/* 
 * 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, exp = ((uf >> 23) & 0xff) - 127, frac = (uf & 0x007fffff) | 0x00800000, value = 0;
    if (exp < 0)
        return 0;
    if (exp > 30)
        return 0x80000000;
    if (exp < 23)
        value = frac >> (23 - exp);
    else if (exp > 23)
        value = frac << (exp - 23);
    return sign ? -value : value;
}

float 范围比 int 更广，但精度（有效数字）更低，注意溢出的情况。

floatPower2

书上的习题，求 $2^x$：

bits.c
 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

/* 
 * 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) {
    if (x < -149)
        return 0;
    // denorm
    if (x < -126)
        return 1 << (149 + x);
    // norm
    if (x < 128)
        return (x + 127) << 23;
    // inf
    return 0x7f800000;
}

参考资料

  1. CS:APP3e, Bryant and O’Hallaron ↩︎

  2. Introduction to CSAPP（八）：Datalab - 知乎 ↩︎

  3. CSAPP DataLab 题解 | Claude’s Blog ↩︎

CSAPP算法位操作

本作品根据 署名-非商业性使用-相同方式共享 4.0 国际许可 进行授权。

CSAPP 信息的表示和处理