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 发行版可以安装:

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

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

编译并运行测试程序:

$ make clean && make btest && ./btest

bitXor

~& 来实现 ^

datalab-handout/bits.c
/* 
 * 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

求补码最小值,送分题:

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

isTmax

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

datalab-handout/bits.c
/*
 * 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 类型可以用取反加一来实现求相反数,而只有两个数满足与自身的相反数相等,即 00x80000000,其中后者是因为溢出。

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

allOddBits

判断是否所有奇数位(最低位为 0 位)都为 1

datalab-handout/bits.c
/* 
 * 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);
}

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

negate

求相反数,送分题:

datalab-handout/bits.c
/* 
 * 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 码:

datalab-handout/bits.c
/* 
 * 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

datalab-handout/bits.c
/* 
 * 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

实现 <=

datalab-handout/bits.c
/* 
 * 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 正负。

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

logicalNeg

实现逻辑非 !

datalab-handout/bits.c
/* 
 * 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,除 00x80000000 外,一个数必定与其相反数异号,若将 x-x 符号异或,则包括 0x80000000 在内 ,所有非零数异或结果必定为 1

howManyBits

求补码表示的最少位数:

datalab-handout/bits.c
/* 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$:

datalab-handout/bits.c
/* 
 * 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

datalab-handout/bits.c
/* 
 * 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$:

datalab-handout/bits.c
/* 
 * 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;
}

参考资料

CSAPP算法位操作

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

自制 OpenCore EFI 让联想 M73 Tiny 吃上黑苹果

缩减 IMG 镜像文件