CSAPP数据实验

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;
}