相关资料

• writeup：http://csapp.cs.cmu.edu/3e/datalab.pdf
• 实验材料：http://csapp.cs.cmu.edu/3e/datalab-handout.tar
• 介绍视频：https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=392a2070-4d49-443c-90b8-4fbbc9f666c6
• docker版实验环境：https://hub.docker.com/r/yansongsongsong/csapp/tags?name=datalab
• 个人题解：https://github.com/LittleGreenMouse/csapp-labs

任务目标

Data Lab主要是通过在约束条件下填充一些函数实现指定功能来熟悉整型、浮点数的位表达形式和一些简单的位操作。

题目列表

题目约束

整数

你的表达式只能使用

1. 整数常数0(0x00) ~ 255(0xff)，不允许使用大常数，如0xffffffff
2. 函数参数和局部变量，不能用全局变量
3. 一元运算符：! ~
4. 二元运算符：& ^ | + << >>

有些问题会进一步限制允许使用的运算符集合

你被明确禁止

1. 使用任何控制结构，如if do while for switch
2. 定义或使用任何宏
3. 定义任何额外的函数
4. 调用任何函数
5. 使用任何其他操作，如&& || - ? :
6. 使用任何形式的类型转换
7. 使用任何int 以外的数据类型，如array struct union

你可以假设你的机器

1. 使用32位的二进制补码表示整数
2. 右移操作为算数右移
3. 如果移位操作的移位量小于0或者大于31，移位结果不可预测

浮点数

对于浮点数任务，限制没有这么严格。你可以

1. 使用循环和条件控制
2. 使用任意的int或unsigned常量
3. 可以在int和unsigned数据上使用任何算数、逻辑或比较操作

你被禁止

1. 定义或使用任何宏
2. 定义任何额外的函数
3. 调用任何函数
4. 使用任何形式的类型转换
5. 使用任何int和unsigned以外的数据类型
6. 使用任何符点数据类型、操作或常量

结果验证

评分标准

正确性分数。每个题目都有一个难度等级，只要能够正确实现题目指定的功能就可活动对应分数，总和36分

性能分数。每个题目都有操作数限制，在解决方案正确的前提下满足数量限制即可获得2分，共26分

自动打分

使用 ./dlc bits.c检查解决方案所用操作是否符合要求

使用 ./dlc -e bits.c会打印每个函数所使用的运算符数目

使用 make编译出 btest，使用 ./btest验证解决方案的正确性

使用 ./driver.pl自动打分

题解

$bitXor(int x, int y)$

• 题目要求：x^y using only ~ and &
• 允许操作：~ &
• 操作数限制：14
• 分数：1

异或，两数相同得0、不同得1，易得，$x \bigoplus y = \overline{x} \& y | x \& \overline{y}$。不过题目要求只使用 ~ &，取两次非用德摩根定律然后展开一个非即可，$x \bigoplus y = \overline{x} \& y | x \& \overline{y} = \overline{\overline{\overline{x} \& y | x \& \overline{y}}} = \overline{\overline{\overline{x} \& y} \& \overline{x \& \overline{y}}}$

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

$tmin(void)$

• 题目要求：return minimum two's complement integer
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：4
• 分数：1

返回最小的整数补码。w位补码的最小整数为$2^{w-1}$，具体到32位即$2^{31}$。直接把1左移31位即可

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

$isTmax(int x)$

• 题目要求：returns 1 if x is the maximum, two's complement number, and 0 otherwise
• 允许操作：! ~ & ^ | +
• 操作数限制：10
• 分数：1

判断 x是否为最大的整数补码。最大的整数补码为 0x7fffffff，从这个数的特点下手，易得 ~(tmax + 1) = tmax，即验证 ~(x + 1) ^ x = 0是否成立。不过由于溢出，0xffffffff也满足这个特性，要注意排除

/*
 * 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 !((!~x) | (~(x + 1) ^ x));
}

前式 !~x用于排除 0xffffffff，当 x = 0xffffffff时，前式为1，则最终返回0；当 x != 0xffffffff时，前式为0，解决取决于后式

$allOddBits(int x)$

• 题目要求：return 1 if all odd-numbered bits in word set to 1, where bits are numbered from 0 (least significant) to 31 (most significant)
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：12
• 分数：2

判断 x的奇数位是否都为1。构造一个奇数位为1、偶数位为0的掩码 mask，显然当 x满足要求时，x | mask = x。不过由于可用常数限制，掩码需要通过两次移位相加构造

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

$negate(int x)$

• 题目要求：return -x
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：5
• 分数：2

求 -x。-x = ~x + 1

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

$isAsciiDigit(int x)$

• 题目要求：eturn 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：15
• 分数：3

判断 x是否满足$0x30 \leq x \leq 0x39$。容易发现，满足要求的数高28位均为 0x0000003；低4位加6不会产生进位，即 x + 6的高28位仍为 0x0000003

/* 
 * 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) {
    return !(((x >> 4) ^ 3) | (((x + 6) >> 4) ^ 3));
}

$conditional(int x, int y, int z)$

• 题目要求：same as x ? y : z
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：16
• 分数：3

实现 x ? y : z。第一反应是构造两个式子求和，一式只包含 xy，二式只包含 xz。当 x = 0时，一式得 0、二式得 z；当 x != 0时，一式得 y、二式得 0。

不过当 x != 0时，其值可能多种多样，使用 !x和 !!x对其进行规格化，不论 x取何值，两式结果一定一个为0、一个为1

由于我们的操作要么是消除一个是数、要么是保留一个数，分别与 0(0x00000000)和 -1(0xffffffff)进行 &操作是一个不错的选择

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

其中，t = ~0 = -1

$isLessOrEqual(int x, int y)$

• 题目要求：if x <= y then return 1, else return 0
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：24
• 分数：3

判断$x \leq y$是否成立。当 x和 y异号时，直接就可判断其大小关系；当 x和 y同号时，判断$x - y \leq 0$是否成立

求差的可行性：由于异号时我们直接通过符号判断结果，只有同号才需要求差；而同号求差，结果的绝对值一定小于两个数中较大的绝对值，不存在溢出风险

int isLessOrEqual(int x, int y) {
    int sx = x >> 31 & 1;
    int sy = y >> 31 & 1;
    int d = x + ~y + 1;
    return (!((sx ^ 1) | (sy ^ 0))) | ((!(sx ^ sy)) & (((d >> 31) & 1) | !d));
}

其中，sx是 x的符号位，sy是 y的符号位，d = x - y

关键点在于表达式 !(sx ^ sy)，当 x和 y异号时其值为0，通过 &把整个后式变成了0，整个结果取决于前式；当 x和 y同号时其值为1，结果取决于$d \leq 0$是否成立

$logicalNeg(int x)$

• 题目要求：implement the ! operator, using all of the legal operators except !
• 允许操作：~ & ^ | + << >>
• 操作数限制：12
• 分数：4

实现逻辑非。把所有整数分成两个集合： 0和非 0。对于任意 x，只有 0和 -0的符号位都为0；其余数两个符号位至少有一个为1，特别地，tmin和 -tmin符号位都为1

/* 
 * 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) {
    return (((x >> 31) & 1) | (((~x + 1) >> 31) & 1)) ^ 1;
}

$howManyBits(int x)$

• 题目要求：return the minimum number of bits required to represent x in two's complement
• 允许操作：! ~ & ^ | + << >>
• 操作数限制：90
• 分数：4

求用补码表示 x最少需要多少位。对于正数，高位的连续0可以合为1个，所以最少位数就等于最高1的位数+1；对于负数，高位的连续1可以合为1个，所以最少位数就等于最高0的位数+1

为了方便，可以对负数取反，转求最高位1

求最高位1的位置可以使用二分法

/* 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 b16, b8, b4, b2, b1, b0;
    x = x ^ (x >> 31);

    b16 = (!!(x >> 16)) << 4;
    x >>= b16;

    b8 = (!!(x >> 8)) << 3;
    x >>= b8;

    b4 = (!!(x >> 4)) << 2;
    x >>= b4;

    b2 = (!!(x >> 2)) << 1;
    x >>= b2;

    b1 = !!(x >> 1);
    x >>= b1;

    b0 = !!x;

    return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

其中 x = x ^ (x >> 31)用于统一正负数。对于正数，x ^ (x >> 31) = x ^ 0x00000000 = x；对于负数，x ^ (x >> 31) = x ^ 0xffffffff = ~x

b16 ~ b0逻辑相同，这里对 b16进行进一步说明。对于32位数 x，二分查找其高16位：

1. 高16位有1。b16 = (!!(x >> 16)) << 4 = 16，下一步x >>= b16把高16位移动到低16位，然后对低16位进行二分
2. 高16位无1。b16 = (!!(x >> 16)) << 4 = 0，下一步x >>= b16没有任何作用，然后对低16位进行二分

IEEE 754 单精度浮点数

后面3道题目是浮点数相关，为便于理解，这里给出IEEE 754单精度浮点数（32位）格式

其中

• 第31位表示符号s
• 第23～30共8位exp用于求出阶码E
• 第22～0共23位frac用于求出尾数M

浮点数的值$V = (-1)^s \times M \times 2^E$

规格化值。当 $exp \neq 0$ 并且 $exp \neq 255$ 时，这个数为一个规格化数。此时，$M = 1.frac, E = exp - 127$

非规格化值。当 $exp = 0$时，这个数是一个非规格化数。此时，$M = 0.frac, E = 1 - 127 = -126$

特殊值。当$exp = 255$时

• $frac = 0$表示无穷。$s = 0$表示$+\infty$，$s = 1$表示$-\infty$
• $frac = 1$表示$NaN$，不是一个数

$floatScale2(unsigned uf)$

• 题目要求：Return bit-level equivalent of expression 2*f for floating point argument f.
• 允许操作：Any integer/unsigned operations incl. ||, &&. also if, while
• 操作数限制：30
• 分数：4

对于浮点数$f$，求$2 \times f$

对于特殊值$0, \pm\infty, NaN$，乘2之后还是其本身，直接返回即可

对于非特殊值，乘2可以有两种做法，令$E = E + 1$或令$M = 2 \times M$，分别对应于规格化数和非规格化数

• 规格化数，其阶码$E = exp - 127$，阶码可直接操作，直接令$exp = exp + 1$返回即可
• 非规格化数，其阶码$E = -126$，阶码不可直接操作，可以令$M = 2 \times M$，即把frac左移一位。如果frac最高位是1，直接左移会溢出，此时丢掉溢出令$exp = exp + 1$即可

/* 
 * 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 frac = uf & 0x007fffff;
    int exp = (uf & 0x7f800000) >> 23;

    if ((exp == 0 && frac == 0) || exp == 0xff) return uf;

    if (exp != 0) exp += 1;
    else {
        exp += (frac >> 22) & 1;
        frac <<= 1;
    }

    return (uf & 0x80000000) + (exp << 23) + (frac & 0x7fffff);
}

$floatFloat2Int(unsigned uf)$

• 题目要求：Return bit-level equivalent of expression (int) f for floating point argument f. Anything out of range (including NaN and infinity) should return 0x80000000u.
• 允许操作：Any integer/unsigned operations incl. ||, &&. also if, while
• 操作数限制：30
• 分数：4

对于浮点数 f，求 (int) f。浮点数强转整型数，直接保留其整数部分，丢弃小数部分即可。不过浮点数范围远大于整型，可以先通过阶码大小进行分类

• $E < 0$。不论是非规格化数$0.frac$还是规格化数$1.frac$，其值均小于1，结果为0
• $E = 0$。此时$V = 1.frac \times 2^0 = 1.frac$，结果为$\pm1$（由符号位决定）
• $E > 31$。此时 $V > 1.frac \times 2^{31}$，超出32整型范围，根据题目要求返回 0x80000000

• $0 < E \leq 31$。此时$V = 1.frac \times 2^E$，舍弃结果中的小数部分即可得到答案的绝对值，最后根据符号位判断正负即可

  • $E \leq 23$。结果中还有$23 - E$个小数位，直接右移舍弃小数部分
  • $E > 23$。结果中还需在最右边补上$E -23$个0

/* 
 * 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) & 1;
    int exp = (uf >> 23) & 0xff;
    int E = exp - 127;

    if (E < 0) return 0;
    else if (E == 0) return sign ? -1 : 1;
    else if (E > 31) return 0x80000000;
    else {
        int frac = uf & 0x007fffff;
        frac += 1 << 23;
        if (E <= 23) frac >>= (23 - E);
        else frac <<= (E - 23);

        if (sign) frac = -frac;
        return frac;
    }
}

其中E直接取了$exp - 127$，虽然在非规格化数时计算错误，但是并不影响分支判断

$floatPower2(int x)$

• 题目要求：Return bit-level equivalent of the expression 2.0^x. If the result is too small to be represented as a denorm, return 0. If too large, return +INF.
• 允许操作：Any integer/unsigned operations incl. ||, &&. Also if, while
• 操作数限制：30
• 分数：4

求$2.0^x$。参照公示$V = (-1)^s \times M \times 2^E$，本题其实就是指定$s = 0$，$M = 1$（即$frac = 0$）并且$E = x$的规格化浮点数。规格化浮点数的阶码范围为$-126 \leq E \leq 128$

• $x < -126$。返回0
• $x > 128$。返回$+\infty$，即 0x7f800000
• $-126 \leq x \leq 128$。令$s = 0, exp = x + 127, frac = 0$构造32位二进制即为答案。(x + 127) << 23

/* 
 * 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 < -126) return 0;
    else if (x > 128) return 0x7f800000;
    else return (x + 127) << 23;
}