CSAPP DataLab

本文是笔者完成CSAPP DataLab的一个记录

请访问Lab官网以获得所需资料

注：DataLab中的int和unsigned int都是32位

1. bitXor(x, 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);
}

主要思路：比较简单的问题，可以考虑到基本结构多半是两块东西取&，并且当x，y同为1或同为0的时候必有其中一块东西是0。

2. tmin()

返回补码表示下int的最小值

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

主要思路：这个但凡学过都该会了吧。

3. isTmax(x)

判断x是否为补码表示下int的最大值

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

主要思路：Tmax特殊性质就是+1之后溢出到Tmin，然后Tmin的特殊性质就是Tmin=-Tmin，也即Tmin+Tmin=0，从而对于Tmax应该满足：(Tmax+1)+(Tmax+1)=0，也即Tmax+Tmax+2=0（这里结合律和交换律的成立原书(CSAPP)上有证明，这是一个阿贝尔群）。至此我们获得了一个必要条件，因为除了Tmax以外，还有-1同样满足这个条件，因此我们需要!(x + 1)来排除掉-1。

4. allOddBits(x)

判断x在二进制表示下奇数位上是否全是1

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

主要思路：用到掩码的思想，用0xAA在二进制下即10101010，然后对它进行左移，或运算后就可以得到一个32位的奇数位全是1的掩码mask，再用mask和x取&，即可取出x的所有奇数位（即将x的偶数位全部置零）。最后只要用异或判断x的奇数位是否与mask相同（即全是1）即可。

5. negate(x)

得到x的相反数

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

主要思想：-x=~x+1应该十分常见了，以下用 $x>0$的情况举例证明：$w$个 $1$是 $2^w-1$（int下$w$就是32），故对于无符号数 $x$，取反后变成 $2^w-1-x$，再考虑符号位，$~x$即为 $2^w-1-x-2 \times 2^{w-1}=-x-1$，加一即得结果；对于符号位为1的情况，可以类似证明。

6. isAsciiDigit(x)

判断x在不在0~9的ASCII码范围内

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

主要思想：这题稍微有些复杂，先写成二进制看看。0x30是00110000，0x39是00111001。可以观察到，前四位是一样的，都是0011，也就是说，只要前四位不是0011 话，必定就不在这个范围里。将x右移四位得到前四位，并由此得到第一个约束3^(x>>4)==0。其次看后四位，最小值是0000不用管，最大值是1001，加上0110后就得到了1111，也就是说，如果后四位大于1001的话，加上0110后必定会进位，只要检测是否进位即可。又由于x的5、6位上全是1，一进就进到第七位，所以就得到(x+6)>>6==0的约束条件。

7. conditional(x, y, z)

纯位运算实现条件分支

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

主要思路：似乎是比较常见的东西。仍然涉及到掩码思想，如果能得到二进制下所有位全1或全0的掩码，和z取&就可以得到z或0了。这里获取全1掩码的过程利用了算数右移的性质，即会将最高位填充成符号位的值，只要算数右移31位，就可以得到全1的掩码了。

8. isLessOrEqual(x, y)

位运算实现$\leq$

/* 
 * 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 sigx = x >> 31;
    int sigy = y >> 31;
    int diff = sigx ^ sigy;
    int sub = y + (~x + 1);
    return (diff & sigx & !sigy) | !(diff | (sub >> 31));  // return (判断x,y符号) | (判断y-x正负)

//    下面的做法也符合要求，但是略傻
//    int diff = x ^ y;
//    int sigx = (x >> 31) & 1;
//    int sigy = (y >> 31) & 1;
//    diff |= diff >> 1;
//    diff |= diff >> 2;
//    diff |= diff >> 4;
//    diff |= diff >> 8;
//    diff |= diff >> 16;
//    diff ^= diff >> 1;
//    return !(x & diff) ^ (!sigx & sigy);
}

主要思路：第一种方法比较优秀，思路是计算出y-x，然后判断其符号。但由于int有溢出的问题，所以应该先判断x，y是否同号，异号可直接确定，同号再进行相减（这时不会溢出）。第二种方法用的操作符有点多（是我最开始的愚蠢思路qwq），思路是异或取出x和y不相同的位，再取出异或结果的最高位（因为最高位决定大小），哪个数字里有这一位哪个就是较大的数（主要是取最高位感觉没什么好办法）。

9. logicalNeg(x)

位运算实现!

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

主要思路：只有0和Tmin取相反数后符号位不变，并且0是0而Tmin是1；更进一步，只有0符号位在操作前后一直是0。而由于算术右移的特性，我们会得到-1或0，故+1变成0或1。

10. howManyBits(x)

计算出用二进制补码表示x需要多少位

/* 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;
    int sig = x >> 31;
    x = (sig & ~x) | (~sig & x); // 如果x为正则不变，否则按位取反
    b16 = !!(x >> 16) << 4;      // 高十六位是否有1
    x >>= b16;                   // 如果有（至少需要16位），则将原数右移16位
    b8 = !!(x >> 8) << 3;        // 剩余位高8位是否有1
    x >>= b8;                    // 如果有（至少需要16+8=24位），则右移8位
    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;  // +1表示加上符号位

//    一种不优秀的解法
//    int lg2 = 0, c, zero;
//    int sig = x >> 31;
//    x = (sig & ~x) | (~sig & x);
//    zero = !x << 31 >> 31;
//    c = ~((x + ((1 << 31) >> 15)) >> 31) & 16;
//    lg2 += c; x >>= c;
//    c = ~((x + ((1 << 31) >> 23)) >> 31) & 8;
//    lg2 += c; x >>= c;
//    c = ~((x + ((1 << 31) >> 27)) >> 31) & 4;
//    lg2 += c; x >>= c;
//    c = ~((x + ((1 << 31) >> 29)) >> 31) & 2;
//    lg2 += c; x >>= c;
//    c = ~((x + ((1 << 31) >> 30)) >> 31) & 1;
//    lg2 += c;
//    return (~zero & (lg2 + 2)) | (zero & 1);
}

主要思路：这题困扰了我相当长的时间，比较棘手。思考一下，对于正数而言，只要在最高位的1前面加一个符号位0即可，对于负数而言，只要在最高位的0前面加一个符号位1即可（这里可以考虑一下负数补码下是怎么做位数拓展的，原书中也有相关内容）。然后采用类似倍增的想法，判断高位上是否有1，有就进行右移，同时记录下右移的总位数。
这道题没有注释部分的答案来自@李明岳的一篇专栏](https://zhuanlan.zhihu.com/p/59534845?utm_source=qq))

下面被注释掉的是笔者的解法，主要思路就是把if (x >> 16) lg2 |= 16, x >>= 16;翻译成了位运算，劣于上面解法的原因主要是没有考虑到用变量把中间进行的位移一个个记录下来。具体的位运算太丑了，就不进行详细解释了。

11. floatScale2(f)

实现浮点运算的2*f

/* 
 * 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 sig = (uf >> 31) & 1;
    int exp = (uf >> 23) & 0xFF;
    if (exp == 0xFF) return uf;  // 无穷大和NaN
    if (!exp) return (sig << 31) + (uf << 1);  // 非规格化
    return uf + (1 << 23);  // 规格化
}

主要思路：只要掌握了浮点数的储存结构就没什么难度，分无穷和NaN，非规格化，规格化三种情况处理即可。

12. floatFloat2Int(f)

将浮点数转换成整数

/* 
 * 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 sig = (uf >> 31) & 1;
    int exp = (uf >> 23) & 0xFF;
    int frac = (uf & 0x7FFFFF) + (1 << 23);  // 这里直接把规格化情况下省略的1加上了
    int offset = 150 - exp, res;  // offset = 23 - (exp - 127)
    if (exp >= 158) return 0x80000000u;  // 158 = 127 + 31
    if (offset > 31) offset = 31;
    if (offset < -31) offset = -31;
    if (offset > 0) res = frac >> offset;
    else res = frac << -offset;
    return sig ? -res : res;
}

主要思路：首先通过指数的范围判断是否过大造成int的溢出。若不溢出，由于C中float转int是向零取整，所以只要将多余的小数位直接丢掉即可（注意一下位移的位数不能<0或>31，否则是undefined behavior）。

13. floatPower2(x)

计算2.0的x次幂

/* 
 * 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;  // -149 = -23 - 126
    if (x > 127) return 0x7F800000;  // +inf
    if (x < -126) return 1 << (149 + x);  // (1 << 22) >> (-127 - x), denorm
    else return (x + 127) << 23; // x放到exp的位置, norm
}

主要思路：主要是区分规格化值是将指数直接放在exp区，非规格化值exp区全是0，只处理很小的数字，所以放在尾码区。注意处理+inf和0即可。

最后

当然是要贴上完成截图啦！

撒花！🌺🌻🌼🌷🌹

受笔者知识水平和表达能力所限，有的问题难免解释得或啰嗦或出现疏漏，欢迎在评论区指正