CSAPP数据实验

发表于
| 字数统计: 1.5k | 阅读时长 ≈ 6

1.bitXor

  • 题目要求：使用~和&实现x^y
  • 允许操作：~ &
  • 操作数限制：14
  • 分值：1

第一题使用not以及and来实现xor。从书中例题可以知道x^y=(x&~y)|(~x&y)，但是这题不能用or。

观察(x&~y)，发现只有x=1且y=0时为1，对于(~x&y)，x=0且y=1时为1。

将这两个取反得
| (x&y) | 1 | 0 |
| ——- | - | - |
| 1 | 1 | 0 |
| 0 | 1 | 1 |

(x&y) 1 0
1 1 1
0 0 1

此时两个结果做and再not即为xor的结果

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

2.tmin

  • 题目要求：返回最小二进制补码整数
  • 允许操作：! ~ & ^ | + << >>
  • 操作数限制：4
  • 分值：1

最小二进制补码整数Tmin就是10000000 00000000 00000000 00000000，十进制对应就是的-217483648。

把1左移31位就成了。

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

3.isTmax

  • 题目要求：如果x是最大二进制补码整数返回1，否则返回0
  • 允许操作：! ~ & ^ | +
  • 操作数限制：10
  • 分值：1

和上一题类似，最大二进制补码整数Tmax的值为 01111111 11111111 11111111 11111111，对于这个数发现对其加一和取反的结果是一样的，都是Tmin，于是写出了!(~x ^ (x + 1))，想通过异或判断这两个数是否一样。但是测试的时候发现0xffffffff也有这个性质，只好在后面加一个判断看是否为全1.

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

4.allOddBits

  • 题目要求：判断所有奇数位是否为1（最低位为0，最高位31），如果是返回1否则返回0。
  • 例：allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
  • 允许操作：! ~ & ^ | + << >>
  • 操作数限制：12
  • 分值：2
1
2
3
4
5
6
int allOddBits(int x) {
  int res;
  x = x & (x>>8) & (x >> 16) & (x >> 24);
  res = !(~(x | 0x55) & 0xff);
  return res;
}

5.negate

  • 题目要求：返回-x
  • 例：negate(1) = -1
  • 允许操作：! ~ & ^ | + << >>
  • 操作数限制：5
  • 分值：2

此题使用观察法得出结果。设x=7则其二进制补码为0000 0111，-7的二进制补码为1111 1001。可以发现这两个数除了最后一位都是反过来的，要想得到一个数的相反数对其补码取反再加一就行了。这也是一个补码的性质。

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

7.conditional

  • 题目要求：返回x?y:z的值
  • 例：conditional(2,4,5) = 4
  • 允许操作：! ~ & ^ | + << >>
  • 操作数限制：16
  • 分值：3

要得到x?y:z的值首先要判断x是0还是1，这就要用到!!操作符来两次取反将x变为0或1。之后将x扩展到所有32位，我用的方法是先左移32位使其成为最高位之后再右移32位（算术右移）。这样如果原先x为0则获得0，如果不为0则获得0xffffffff。

因为x为1的话返回y，为0返回z，可以通过将y与mask进行与操作，z与~x进行与操作来得到选择的效果，最后将两个结果合并就是最后的结果了。

1
2
3
4
5
6
int conditional(int x, int y, int z) {
  int x1 = !!x;
  int mask = x1 << 31 >> 31;
  int res = (y&mask)|(z&~mask);
  return res;
}

floatScale2

  • 题目要求：返回2*f的浮点数表示，当参数为NaN时直接返回参数
  • 允许操作：所有的，包括|| && if while
  • 操作数限制：30
  • 分值：4

对于规格化浮点数，其表示为2^expfrac，2f即2^(exp+1)*frac，将exp部分加一即可。

对于非规格化浮点数，因为exp已经确定不能改变，所以要想将其乘以2只要将frac乘以2，即左移一位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned floatScale2(unsigned uf) {
  int sign = uf & 0x80000000;
  int exp = (uf & 0x7f800000) >> 23;
  int frac = uf & 0x007fffff;
  int res, masked;
  if(exp == 255){
    // if number is NaN or Infinity
    return uf;
  }
  if(exp == 0){
    // for denormal numbers, *2 means left shift frac once
    frac = frac << 1;
    return frac | sign;
  }
  // for normal numbers, *2 means left add one to exp
  exp = exp + 1;
  // clear original number's exp area and then apply new exp in
  masked = uf & 0x807fffff;
  res = (exp << 23) | masked;
  return res;
}

floatFloat2Int

  • 题目要求：将输入的浮点数用整型表示，如果输出超出范围（包括NaN或是Infinity）返回0x80000000u
  • 允许操作：所有的，包括|| && if while
  • 操作数限制：30
  • 分值：4

首先从输入的浮点数中获取sign，exp和frac，然后根据这些信息来算出对应的整数。

主要思想为通过exp-127获得bias，就是frac乘以的2的次方数，如果bias为1就是乘以二，以此类推。通过将frac右移23-bias位即可获得对应的整数值。

最后如果sign为1还需要将结果变为负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int floatFloat2Int(unsigned uf) {
  // getting sign, exponent and fraction from the float number
  int sign = uf & 0x80000000;
  int exp = (uf & 0x7f800000) >> 23;
  int bias = exp - 127;
  int frac = uf & 0x007fffff;
  int res;
  if(exp == 255 || bias > 30){
    // if the number is infinity, NaN (bias is 255) or too big for integer (exp > 30)
    return 0x80000000u;
  } else if (exp == 0 || bias < 0){
    // if the number is smaller than 0, return 0
    return 0;
  }
  // add back the lost 1 to the front of fraction
  frac = frac | (1 << 23);
  // result is fraction right shift 23-bias times
  res = frac >> (23 - bias);
  // if the sign of float is 1, need to return -res
  if(sign){
    res = ~res+1;
  }
  // for debug purpose
  //printf("\n%x\t%x\t%x\n", sign, bias, res);
  return res;
}

floatPower2

  • 题目要求：返回2.0^x的浮点数表示，如果数太小不能用非规格化表示返回0，如果太大返回+INF
  • 允许操作：所有的，包括|| && if while
  • 操作数限制：30
  • 分值：4
    因为x是整数，所以2的x次方用浮点数表示就是exp部分为x。因为规格化浮点数只能表示到2^127，所以x比127大则返回+INF。又因为非规格化浮点数只能表示到2^-126，所以x<-126直接返回0。剩余的情况就是能表示的了，将x+bias（127）左移23为成为exp返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned floatPower2(int x) {
  int inf = 0x7f800000;
  int exp, res;
  if(x > 127){
    return inf;
  }else if(x < -126){
    return 0;
  }
  exp = x+127;
  res = exp << 23;
  //printf("\n%x\t%x\n", exp, res);
  return res;
}