深入理解计算机系统(CSAPP) 实验：data lab

作者: userheng | 来源:发表于2020-06-06 12:46 被阅读0次

datalab简介

这个lab要求使用高度受限的C语言操作，来实现一些简单的逻辑功能，以及补码、浮点数的相关操作函数。比如，只能使用位级运算符来实现计算一个数的绝对值，并且必须是straightline code(代码中不能使用if else、switch、while、goto等)。

这个lab的主要目的是帮助我们 理解数据的位级表示和位级操作

完成datalab

1. bitxor

功能：对于入参 int x，y 。使用 ~和&运算符实现 x ^ y

解题思路：
我们可以快速的构建 c = a ^ b 的 真值表。

a	b	c
0	0	0
0	1	1
1	0	1
1	1	0

然后将 真值表 转化为 卡诺图，这样可以得到
a ^ b == (~a&b | a&~b)
然后根据 摩尔根定律
~~(a ^ b) == a ^ b == ~(~(~a&b) & ~(a&~b))

这里只涉及a,b两个元的逻辑关系，比较简单，所以其实没有必要使用真值表和卡诺图。但是要注意这种解题的思路，当涉及到多个元的逻辑关系时。卡诺图是将逻辑关系简化转换为 &和| 的利器。

旁注：卡诺图化简法

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
    int m = x & ~y;
    int n = ~x & y;
    return ~(~m & ~n); 
}

2.isTmax

功能：对于入参 int x，若x是最大值则返回1，否则返回0。

解题思路：
32位int（补码表示）的最大值 TMax 为 0x7fffffff ，我们发现 TMax + 1 即为 0x80000000（1 << 31）。
所以若 x+1 == (1 << 31) 即说明 x 是 TMax。
这里利用异或来做相等判断。（a ^ a = 0 ）

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

3.allOddBits

功能：对于入参 int x 的位级表示，若其每个奇数位都为1则返回1，否则返回0。

解题思路：
构造一个 0xAAAAAAAA。
若x所有的奇数位均为1，那么有 x & 0xAAAAAAAA = 0xAAAAAAAA。

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

4. negate

功能：对于入参 int 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;
}

5. isAsciiDigit

功能：对于入参 int x，如果它的值可以表示Ascii字符0到9，则返回1，否则返回0。

解题思路：
0x30 ~ 0x39 (Ascii码0~9的十六进制值)，的二进制表示为 0011 0000 ~ 0011 1001
观察二进制位，我们可以发现。若第4位二进制位为 0 则其左侧第三位可以取任何值，若第4位二进制位为 1，则其左侧第三位只能为 001。

/* 
 * 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 p1 = !((x >> 1) ^ 0x1c);
    int p2 = !((x >> 3) ^ 0x6);   
    return p1 | p2;
}

6. conditional

功能：对于入参 int x，y，z。如果 x 非 0 则返回 y，若为 0 则返回 z。

解题思路：
通过 !!x 可以将 x 转为 0 或 1 。由于后面需要返回 y 或 z 的值，所以这里将 0 转为 0x00000000 , 1 转为 0xffffffff 。(32位全0，32位全1)

/* 
 * 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 cond = !!x;// covert x to 0 or 1
    int mask = (cond << 31) >> 31;//0 --> 0x0, 1 --> 0xffffffff
    return (mask & y) | (~mask & z);
}

7. isLessOrEqual

功能：对于入参 int x，y。若 x <= y 返回 1，否则返回 0。

解题思路：
对于 x 和 y ，考虑以下情况：
若其符号位相同，则有若x < y，即 x - y < 0 ，即x + (~y + 1) < 0
若其符号位不同，则有若x < y，即 x < 0 且 y > 0
若 x = y，则 x ^ y = 0
如果不考虑符号位是否相等，贸然通过 x 与 y 的差值来进行判断是不对的，因为符号不同 x 与 y 的差值计算可能会溢出

/* 
 * 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 x_sign = (x >> 31) & 0x1;
    int y_sign = (y >> 31) & 0x1;
    int xSign_eq_ySign = !(x_sign ^ y_sign);
    //符号位相同时， x < y --> x - y < 0 --> x + ~y + 1 < 0
    int c1 = xSign_eq_ySign & (0x1 & ((x + ~y + 1) >> 31));
    //x < y --> x < 0, y > 0
    int c2 = x_sign & !y_sign;
    // x = y时
    int c3 = !(x ^ y);
    return c3 | c2 | c1;            
}

8. logicalNeg

功能：对于入参 int x，若x为0则返回1，否则返回0。（即实现运算符 !）

解题思路：
若 int x=0 ，则有 x 有以下特征：
a. x 的符号位为0；
b. -x，即 ~x + 1 的符号位仍为0；

/* 
 * 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) {
    int x_sign = (x >> 31) & 0x1;
    //符号位为0,且x=0  --> !x 返回1
    //x=0时, -x的符号位仍然是0
    int x2_sign = ((~x + 1) >> 31) & 0x1;
    int c1 = (~x_sign & 0x1) & (~x2_sign & 0x1);
    return c1;
}

9. howManyBits

功能：对于入参 int x，返回一个可以表示其值的最小二进制位长度。

解题思路：
12（01100）
-5（1011）
0 （0）
1 （-1）
通过观察总结，我们可以发现如下规律：
a. 对于正数，结果为二进制位为中最高位为1的所在位置加1。
b. 对于负数我们可以取 ~x，结果为 -x 二进制位中最高位为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) {
    //x为负数时，取~x
    int x_sign = (x >> 31) & 0x1;
    int mask = (x_sign << 31) >> 31;
    x = (mask & ~x) | (~mask & x);
    //
    //采用二分查找法，找出x最高位为1的位置
    int left_shift = 16;
    int k = !!(x >> left_shift) << 4;//0 | 16
    left_shift = (left_shift - 8) + k;//8 | 24

    k = !!(x >> left_shift) << 3;//0 | 8
    left_shift = (left_shift - 4) + k;//4 | 12 | 20 | 28

    k = !!(x >> left_shift) << 2;//0 | 4
    left_shift = (left_shift - 2) + k;//2 | 6 | 10 | 14 | 18 | 22 | 26 | 30

    k = !!(x >> left_shift) << 1;//0 | 2
    left_shift = (left_shift - 1) + k;//1 | 3 | 5 | 7 | 9 | 11 | ... | 29 | 31

    k = !!(x >> left_shift);
    //没有涵盖x=0的情况（需要特殊处理）
    int high_bit_one_index = k + left_shift;
    
    int is_x_zero = !(x ^ 0);
    mask = (is_x_zero << 31) >> 31;
    return (mask & 0x1) | (~mask & (high_bit_one_index + 1));
}

10. floatScale2

功能：对于入参 unsigned uf，以 float 来解释其二进制位，若 uf 为 NaN 或无穷大 则直接返回，否则计算 uf * 2 并返回。

解题思路：
参见IEEE浮点标准。

/* 
 * 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 exp = (uf & 0x7f800000) >> 23;
    unsigned frac = uf & 0x7fffff;
    //NaN 和 无穷大时，返回uf
    if(exp == 255)
        return uf;
    //非规格化时
    if(exp == 0){
        //frac = (frac << 1) & 0x7fffff;
        return (uf & 0x80000000) + (exp << 23) + (frac << 1);
    }
    //规格化时
    return (uf & 0x80000000) + ((exp+1) << 23) + frac;
}

11. floatFloat2Int

功能：对于入参 unsigned uf，以 float 来解释其二进制位，并尝试将其转换为 int 返回，若溢出直接返回 0x80000000。

解题思路：
参见IEEE浮点标准。

/* 
 * 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) {
    unsigned exp = (uf & 0x7f800000) >> 23;
    int bias = 127;
    //小于1
    if(exp < bias)
        return 0;
    //溢出    
    if(exp >= (bias + 31))
        return 0x80000000;
    int v = 1 << (exp -bias);
    int s = (uf >> 31) & 0x1;
    if(s)
        return -v;
    return v;
}

12. floatPower2

功能：对于入参 int x，返回 2.0 的 x 次方的位级表示。

解题思路：
参见IEEE浮点标准。
浮点数表示的标准表达式为 $V=(-1)^s * M * 2^E$ ，则对于 float 值 2.0 ，s=0 M=1 E=1 。

类型	偏置值Bias	$E$	$M$
规格化的	$2^{k-1} - 1$	exp - Bias	1 + frac
非规格化的	$2^{k-1} - 1$	1 - Bias	frac

单精度float类型的偏置值Bias 为 127， float 值 2.0 为规格化的。所以我们可以得出 exp=128 frac=0
即float 2.0 的二进制表示为 0 10000000 000000000000000
2.0的x次方，即E = E * 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) {
    //normalize exp [1, 254] --> E [-126, 127]
    int E = 1;
    E = x * E;
    if(E < -126)
        return 0;
    if(E > 127)
        return 0x7f800000;
    int bias = 127;
    int exp = E + bias;
    return exp << 23;
}

测试报告

btest.png

很遗憾，最后一个函数 floatPower2 没有通过，网上找了很多资料，也没有找到解决的办法，如果大家有正确的解法，希望能告诉我一下，谢谢😀。

lab资料

Data Lab [Updated 12/16/19] (README, lab 操作指南, lab 修订记录, lab 下载)