CSAPP Data Lab

CSAPP 的第一个 Lab，对应知识点为书中的第 2 章（信息的表示与处理），要求使用受限制的运算符和表达式实现一些位操作。主要分为两个部分：整数部分和浮点数部分。其中整数部分限制较多，比较偏重技巧性，部分题个人认为很有难度。而浮点数部分则比较基础，主要考察对 IEEE 754 标准的熟悉程度，代码较长，但思路相对简单。

bitXor

思路

使用德-摩根定律进行推导，推导过程如下：

代码

int bitXor(int x, int y) {
    // 德-摩根定律
    return ~(~(x & ~y) & ~(~x & y));
}

tmin

思路

最小整数即最高位（负数权重）为 1，其余（正数权重）为 0。

代码

int tmin(void) {
    return 1 << 31;
}

isTmax

思路

由于不能使用左移运算符，因此没办法直接构造出 tmax，需要仔细考虑 tmax 的性质：tmax = 0x7fffffff ，而 tmax + 1 = 0x80000000 ，这两个数的二进制位完全互补，因此满足：tmax + tmax + 1 = 0xffffffff，结果全为 1，对该结果取反即可得到 0，取非得到 1。

但这里还要考虑一个特殊情况：当 x = 0xffffffff 时，x + 1 + x 也满足等于 0xffffffff，因此需要借助异或运算进行特判。

代码

int isTmax(int x) {
    int case1 = !((x + 1) ^ 0);  // case = x == 0xffffffff ? 1 : 0;
    return !(~(x + 1 + x)) & !case1;
}

allOddBits

思路

首先构造一个掩码 mask，奇数位全为 1，偶数位全为 0。将 mask 与 x 进行按位与，如果 x 的奇数位全为 1，那么按位与的结果仍然为 mask。然后便可以借助异或和非的组合，将结果转换为 0 或 1。

代码

int allOddBits(int x) {
    int mask = 0xaa;            // mask = 0x000000aa
    mask = (mask << 8) | 0xaa;  // mask = 0x0000aaaa
    mask = (mask << 8) | 0xaa;  // mask = 0x00aaaaaa
    mask = (mask << 8) | 0xaa;  // mask = 0xaaaaaaaa
    return !((x & mask) ^ mask);
}

negate

思路

补码表示法的重要特性，取反加一即可。

代码

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

isAsciiDigit

思路

这里我用了比较笨的逐位判断的方法。首先判断第 4 到第 31 位是否为 0x3，然后只需要关注低 4 位的二进制表示了：若第 3 位为 0，则一定位于指定范围之内，再加上两个特例（1000 和 1001）即可。

最后将运算符的个数刚好卡在 15 个，勉强过关。

代码

int isAsciiDigit(int x) {
    // 0011 0000 <= x <= 0011 1001
    int high = !((x >> 4) ^ 0x3);         // 4 ~ 31 位是否为 0x3
    int case1 = ((x & 0xf) >> 3) ^ 0x1;   // bit3 = 0
    int case2 = !((x & 0xf) ^ 0x8);       // bit0~3 = 1000
    int case3 = !((x & 0xf) ^ 0x9);       // bit0~3 = 1001
    return high & (case1 | case2 | case3);
}

conditional

思路

很容易想到根据 x 的值是否非 0 构造出全 0 或者全 1 的数据 flag，然后将 flag 和 flag 取反后的值分别与 y 和 z 进行按位与，这样必然得到两个数：一个为 y 或 z 本身，另一个为 0，再将结果按位或即可。

构造的方法比较巧妙，需要注意到全 0 和全 1 分别代表整数 0 和 -1，它们分别是 0 和 1 的相反数，而 0 和 1 我们可以根据表达式是否非 0，使用非运算符构造出来，再将构造的结果取反加一即可。

代码

int conditional(int x, int y, int z) {
    int flag = ~(!x) + 1;     // flag = x ? 0 : -1;
    int yp = ~flag & y;       // flag = 0, yp = y; flag = -1, yp = 0;
    int zp = flag & z;        // flag = 0, zp = 0; flag = -1, zp = z;
    return yp | zp;
}

isLessOrEqual

思路

判断两个数的大小关系，很容易想到使用作差的方法，判断 x + ~y + 1 的结果是否小于等于 0，即全为 0 或者最高位为 1。

不过这里还需要考虑溢出：由于同号相减必定不会导致溢出，因此我们只需要考虑异号的情况。而如果两个数异号，那它们之间的大小关系就显而易见了。

代码

int isLessOrEqual(int x, int y) {
    int sign1 = ((x >> 31) & 1) & ((y >> 31) ^ 1);  // sign1 = (x < 0 && y > 0) ? 1 : 0;
    int sign2 = ((x >> 31) ^ 1) & ((y >> 31) & 1);  // sign2 = (x > 0 && y < 0) ? 1 : 0;
    int z = x + ~y + 1;                             // z = x - y
    int sub = !(x ^ y) | ((z >> 31) & 1);           // z <= 0    
    return (sub | sign1) & !sign2;
}

logicalNeg

思路

这题从二进制位的角度不好思考，不妨从其表示的十进制数的角度出发：

当 x = 0 时，-x = x ，即 x 和 -x 的最高位相同，都为 0；当 x != 0 时，x 和 -x 的最高位必定有一个为 1。

可以利用这一特性将 x | nx 右移 31 位，由于整数进行的是符号右移，因此当最高位为 0 时，右移的结果全为 0，当最高位为 1 时，右移的结果全为 1。再将右移结果加 1，即可构造出 1 或者 0，且刚好与零和非零对应。

代码

int logicalNeg(int x) {
    int nx = ~x + 1;
    return ((x | nx) >> 31) + 1;
}

howManyBits

思路

这题看到限制 90 个运算符就给吓着了，实际上也确实很困难，自己想了半天也没有思路，于是在网上参考了别人的解法，感觉相当精妙，在这里介绍一番：

对于正整数 x 而言，可以使用二分搜索的方式来确定所需的位数。首先判断 x 是否需要 16 位来表示，即 x 右移 16 位是否为 0，如果是，则右移 16 位，否则不做处理，然后再判断是否需要 8 位来处理，以此类推。最后将上述过程中的右移次数累加起来再加一（正整数首位需要为 0），即为总共需要的位数。

对于负整数 x 而言，它所需的位数与 x 取反得到的整数所需位数相同，证明没整明白。。。

代码

int howManyBits(int x) {
    int absx = (x >> 31) ^ x;
    int b16, b8, b4, b2, b1, b0;

    // 二分搜索
    b16 = (!!(absx >> 16)) << 4;
    absx = absx >> b16;
    b8 = (!!(absx >> 8)) << 3;
    absx = absx >> b8;
    b4 = (!!(absx >> 4)) << 2;
    absx = absx >> b4;
    b2 = (!!(absx >> 2)) << 1;
    absx = absx >> b2;
    b1 = (!!(absx >> 1));
    absx = absx >> b1;
    b0 = absx;

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

floatScale2

思路

这题主要是要对规格化数和非规格化数进行分类讨论：

当 uf 为规格化数，即阶码不为 0 时，乘二相当于将阶码位加 1。

当 uf 为非规格化数，即阶码为 0 时，此时 uf 的值完全由尾数来表示，且不含隐含 0，因此乘二相当于将尾数乘二，即左移 1 位。

需要注意的是，当 uf 为非规格化数且尾数最高位为 1 时，尾数左移会导致最高位的 1 移动到阶码的最低位。但经过验证，此时的结果仍然符合预期，即非规格化数无缝衔接到了规格化数，不禁感叹 IEEE 754 标准浮点数的设计之精妙。

代码

unsigned floatScale2(unsigned uf) {
    unsigned t = (uf >> 23) & 0xff;  // 阶码
    unsigned m = uf & 0x7fffff;      // 尾数
    if (t == 0xff) return uf;        // 无穷大或者 NaN
    // 非规格化数
    if (t == 0x00) {
        m <<= 1;
        uf &= 0xff800000;
        uf |= m;
    }
    // 规格化数
    else {
        t += 1;
        uf &= 0x807fffff;
        uf |= (t << 23);
    }
    return uf;
}

floatFloat2Int

思路

首先确定整数所能表示的上下界的值：当阶码小于 127，即指数位小于 0 时，此时浮点数 uf 小于 1，对应的整数为 0；当阶码大于 150，即指数位大于 23 时，此时单精度浮点数的精度（尾数长度）不足以正确表示对应的整数，返回 0x80000000。

对于在合理范围内的 uf，将其转换为对应的整数，首先需要尾数最高位的高一位加上规格化数隐含的 1，再根据阶码的大小将尾数进行右移，阶码越大，右移位数越少。最后根据符号位的值选择是否将结果取反加一。

代码

int floatFloat2Int(unsigned uf) {
    unsigned s = (uf >> 31) & 0x1;   // 符号
    unsigned t = (uf >> 23) & 0xff;  // 阶码
    unsigned m = uf & 0x7fffff;      // 尾数
    int val;
    // 小于 1
    if (t < 127) {
        val = 0;
    }
    // 大于 1 且不溢出
    else if (t <= 150) {
        val = m | 0x800000;
        val >>= (23 - (t - 127));
        if (s == 1) {
            val = ~val + 1;
        }
    }
    // 溢出
    else {
        val = 0x80000000;
    }
    return val;
}

floatPower2

思路

同样是对规格化数和非规格化数的分类讨论：

当 x >= -150 && x < -127 时，结果为非规格化数，此时浮点数表示只有一个位为 1，其余全为 0。直接根据指数 x 的值确定该位的位置即可。

当 x >= -127 && x < 128 时，结果为规格化数，此时浮点数表示的尾数全为 0，只有阶码用来表示指数的值。根据指数 x 的值确定阶码的值，然后构造出浮点数即可。

代码

unsigned floatPower2(int x) {
    unsigned val;
    // 太小
    if (x < -150) {
        val = 0;
    }
    // 非规格化数
    else if (x < -127) {
        val = 1 << (150 + x);
    }
    // 规格化数
    else if (x < 128) {
        unsigned t = x + 127;
        val |= (t << 23);
    }
    // 太大
    else {
        val = 0x7f800000;
    }
    return val;
}