CSAPP_Lab1_DataLab

实验简介

学生可以实现简单的逻辑函数、二进制补码和浮点函数，但必须使用 C 语言的一个高度受限的子集。例如，可能会要求仅用位级运算和直线代码（straightline code）来计算一个数的绝对值。该实验帮助学生理解 C 语言数据类型的位级表示和数据操作的位级行为。

具体实现

bitXor(x,y)

要求：仅使用 ~ 和 & 完成异或运算。

运算：~ &

即找出同一位都是0或者1的设为0 比较简单

1
2
3
int bitXor(int x, int y) {
  return ~(x&y)&~(~x&~y);
}

tmin()

要求：返回二进制补码表示的最小整数。

运算： ! ~ & ^ | + << >>

做法：补码表示的最小整数为 10…0，即符号位为 1，其余位为 0,直接返回即可

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

isTmax(x)

要求：判断 x 是否为补码表示的最大整数。

运算：! ~ & ^ | +

做法：当 x 为最大整数时，补码表示为 01…1，即符号位为 0，其余位为 1，可得 x + 1 = ~x。

然而当 x = -1 时，前述等式也成立，因此需要排除掉这种情况。

x = -1 为11111111

1
2
3
int isTmax(int x) {  
	return !((~x^(x+1)) | !(x+1));
}

allOddBits(x)

要求：判断 x 二进制表示下的奇数位是否全为 1。

运算：! ~ & ^ | + << >>

做法：规则允许使用最大为 0xFF 的整数，因此可使用 & 运算每 8 位合并 x 的所有位，然后使用 ^ 运算判断奇数位是否全为 1。

1
2
3
4
int allOddBits(int x) {
    int all_odd = 0xAA + (0xAA << 8) + (0xAA << 16) + (0xAA << 24);
    return !((x&all_odd)^all_odd);
}

negate(x)

要求：计算返回 -x。

运算：! ~ & ^ | + << >>

做法：取反+1

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

isAsciiDigit(x)

要求：判断值 x 是否在范围 [0x30, 0x39] 中。

运算： ! ~ & ^ | + << >>

做法：通过位级运算计算 x 是否在 0x30 - 0x39 范围内就是这个题的解决方案。那如何用位级运算来操作呢？我们可以使用两个数，一个数是加上比0x39大的数后符号由正变负，另一个数是加上比0x30小的值时是负数。这两个数是代码中初始化的 upperBound 和 lowerBound，然后加法之后获取其符号位判断即可。

1
2
3
4
5
6
7
8
int isAsciiDigit(int x) {
  int sign = 0x1<<31;
  int upperBound = ~(sign|0x39);
  int lowerBound = ~0x30;
  upperBound = sign&(upperBound+x)>>31;
  lowerBound = sign&(lowerBound+1+x)>>31;
  return !(upperBound|lowerBound);
}

即观察符号位，当符号位为1说明不满足条件

conditional(x,y,z)

要求：执行三目运算符 x ? y : z：当 x 不为 0 时，返回 y；否则返回 z。

运算：! ~ & ^ | + << >>

做法：核心思想是利用 x 得出位模式等于 -1（全为 1）的值，使用 & 运算和 ~ 运算得到 y 或 z 的位模式，最后使用 | 得到结果。

使用函数x = !x + ~0;x是0，则!x是1，则结果为0000 0000，x是1的话,结果为1111 1111

1
2
3
4
int conditional(int x, int y, int z) {  
	x = !x + ~0;  
	return (y & x) | (z & ~x);
}

isLessOrEqual

要求：判断 x <= y。

运算：! ~ & ^ | + << >>

做法：将问题转换成判断 a+b≤0，新问题下需要注意溢出问题。分符号，分类讨论

1
2
3
4
5
6
7
8
9
10
11
int isLessOrEqual(int x, int y) {
    /*
    x <= y when:
        y >= 0 and x < 0
        or sign(x) == sign(y) and  y+(-x) >=0
    */
    int sign_x = (x >> 31) & 1; // 0 for (x>=0), 1 for (x<0)
    int sign_y = (y >> 31) & 1;
    int sign_y_sub_x = (y + ~x + 1) >> 31 & 1; // 0 for (y>=x), 1 for (y<x)
    return (sign_x & !sign_y) | (!(sign_x ^ sign_y) & !sign_y_sub_x);
}

logicalNeg(x)

要求：计算 !x：当 x = 0 时返回 1；当 x ≠ 0 时返回 0。

运算：~ & ^ | + << >>

做法：当 x≠0 时，x|(−x) 的符号位必然为 1。

1

howManyBits

要求：使用二进制补码表示 x 的最少位数。

运算：! ~ & ^ | + << >>

做法：当 x≥0 时，位数取决于 1 的最高位数；当 x<0 时，位数则取决于 0 的最高位数（根据补码表示的定义，符号位起连续的 1 可合并起来用一个位表示）。

首先考虑将负数取反，将问题统一成计算 1 的最高位，利用算术右移即可完成，

然后使用二分法计算 1 的最高位：判断高 16 位是否大于 0，若大于 0 说明高 16 位中存在 1，否则 1 在低 16 位中。使用 conditional 函数更新 x（取出高 16 位或低 16 位）。迭代判断 8 位、4 位等等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);


// 不断缩小范围
  b16 = !!(x>>16)<<4;//高十六位是否有1
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = !!(x>>8)<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = !!(x>>4)<<2;//同理
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

floatScale2(f)

要求：计算 2 * uf，若 uf 为特殊值时，直接返回 uf。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：这道题需要对浮点数表示比较了解，单精度（float）表示包括：1 位符号，8 位阶码，23 位尾数。这里使用 e 表示阶码的无符号数，B 表示阶码的偏置值，f 表示尾数值。

1
2
3
4
5
6
7
8
9
10
11
12
unsigned floatScale2(unsigned uf) {
    unsigned s = (uf >> 31) & 1;
    unsigned e = (uf >> 23) & 0xff;
    // ---- ---- -111 1111 1111 1111 1111 1111
    unsigned f = uf & 0x7fffff;
    if (!e)
        return (s << 31) | (f << 1);
    if (!(e^0xff))
        return uf;
    return (s << 31) | ((e+1) << 23) | f;
}

  1. 当 e 全 0 时，表示非规格化的值，真实值

    乘上系数 2 时，阶码是否变动看 2f 是否大于等于 1，即 f 最高位是否为 1。由于阶码在尾数的高位，该情况下位数左移 1 位即可。

  2. 当 e 不全 0 也不全 1 时，表示规格化的值，

    阶码 + 1 即可。

  3. 当 e 全 1 时，表示特殊值。

floatFloat2Int(uf)

要求：将浮点数 uf 转换成整数。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：首先考虑特殊情况：如果原浮点值为0则返回0；如果真实指数大于31（frac部分是大于等于1的，1<<31位会覆盖符号位），返回规定的溢出值**0x80000000u**；如果 exp<0 （1右移x位,x>0，结果为0）则返回0。剩下的情况：首先把小数部分（23位）转化为整数（和23比较），然后判断是否溢出：如果和原符号相同则直接返回，否则如果结果为负（原来为正）则溢出返回越界指定值0x80000000u，否则原来为负，结果为正，则需要返回其补码（相反数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int floatFloat2Int(unsigned uf) {
  int s_    = uf>>31;
  int exp_  = ((uf&0x7f800000)>>23)-127;
  int frac_ = (uf&0x007fffff)|0x00800000;
  if(!(uf&0x7fffffff)) return 0;

  if(exp_ > 31) return 0x80000000;
  if(exp_ < 0) return 0;

  if(exp_ > 23) frac_ <<= (exp_-23);
  else frac_ >>= (23-exp_);

  if(!((frac_>>31)^s_)) return frac_;
  else if(frac_>>31) return 0x80000000;
  else return ~frac_+1;
}

floatPower2(x)

要求：使用浮点数表示 2^x。无法表示时：过小返回 0，过大返回 +INF。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：

1
2
3
4
5
unsigned floatPower2(int x) {
  x = x + 0x7f;
  if (x < 0) return 0;
  return x < 0xff ? x << 23 : 0x7f800000u;
}

主要阶码有个偏移值127

image-20231018104856905