CSAPP - Data Lab
1. BitXor
函数实现
1
2
3
int bitXor(int x, int y) {
return ~(~x & ~y) & ~(x & y);
}
函数分析
通过真值表可写出按位异或运算函数：~((~x & ~y) | (x & y))，通过德摩根定律将或运算改为与运算即可。
2. copyLSB
函数实现
1
2
3
int copyLSB(int x) {
return (x << 31) >> 31;
}
函数分析
这个函数要求把x的所有位都替换成x的最低位，因此想到有符号数的算数右移会根据正负自动补0或1。于是将x先左移31位，把最低位置于最高位，再右移31位，实现替换。
3. isEqual
函数实现
1
2
3
int isEqual(int x, int y) {
return !(x ^ y);
}
函数分析
这个函数的实现很显然，即把x和y进行按位异或运算，若所有位均相同，则结果为0，否则为非0，将结果取反即可。
4. bitMask
函数实现
1
2
3
4
5
6
int bitMask(int highbit, int lowbit) {
int n = ~0x00;
int high = (n << highbit) << 1;
int low = n << lowbit;
return low & ~high;
}
函数分析
为使掩码lowbit位至highbit位均为1，设想生成两个数，其中一个数从lowbit及以上均为1，另一个数从highbit及以下全为1，之后将两数进行按位与，即可得到掩码。为此，将0按位取反，得到每一位都为1的数n。之后分别将其左移highbit+1位和lowbit位，并将前者取反，再将两数按位与，得到答案。
5. tmax
函数实现
1
2
3
int tmax(void) {
return ~(1 << 31);
}
函数分析
最大的补码为0x7FFFFFFF，即最高位为0，其余位均为1。于是想到将1左移31位再按位取反。
6. isNonNegative
函数实现
1
2
3
int isNonNegative(int x) {
return !(x >> 31);
}
函数分析
这一函数的实现也很显然，只需判断x最高位是0还是1即可。运用算数右移，将x的所有位替换为最高位，再取反即可。
7. addOK
函数实现
1
2
3
4
int addOK(int x, int y) {
int sum = x + y;
return !(((sum ^ x) & (sum ^ y)) >> 31);
}
函数分析
溢出发生在x和y的符号相同，但x与y的和符号与他们不同时，即x和y分别与sum(x与y的和)进行按位异或运算，两者最高位均为1。为判断最高位是0还是1，再次使用右移31位的方法，并对结果取反。
8. isLess
函数实现
1
2
3
4
5
6
int isLess(int x, int y) {
int res = x + (~y + 1);
int flag1 = x & (~y);
int flag2 = (~(x ^ y)) & res;
return (flag1 | flag2) >> 31 & 1;
}
函数分析
x < y有两种可能，第一种情况是x为负，y为正，此时x一定小于y，该情况用flag1表示；第二种情况为x和y同号，即~(x ^ y)的最高位为1时，此时通过res，即x减y的值来进行判断。若x小于y，则res为负，最高位为1，反之为0，该情况用flag2表示。最后将两种情况取或，并右移31位把所有位替换为最高位，再和1按位与，返回结果
9. float_neg
函数实现
1
2
3
4
5
6
unsigned float_neg(unsigned uf) {
if ((uf & 0x7FFFFFFF) > 0x7F800000) {
return uf;
}
return uf ^ 0x80000000;
}
函数分析
这一函数需要处理两种情况：uf为NaN时返回uf本身，其余情况返回-uf。返回负数很简单，将uf与0x80000000进行异或运算即可，以达到将uf的最高位取反的目的。难点在于判断uf是否为NaN，即uf的阶码全为1，尾数不为0。思考后想到将uf与0x7FFFFFFF按位与，若结果大于0x7F800000，则说明阶码全为1，尾数不为0，返回uf。
10. float_half
函数实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned float_half(unsigned uf) {
unsigned res;
if ((uf & 0x7F800000) == 0x7F800000) {
return uf;
}
if (uf & 0x7F000000) {
res = uf + 0xFF800000;
} else {
res = uf >> 1;
if ((uf & 3) == 3) {
res += 1;
}
if (uf & 0x80000000) {
res += 0x40000000;
}
}
return res;
}
函数分析
把一个浮点数的值除以2有三种情况需要考虑：
- 当该数为
NaN或inf的时候，无法进行操作，直接返回uf本身，该情况通过uf与0x7F800000进行按位与运算的结果是否与0x7F800000相等来判断，即判断阶码是否均为1。 - 当该数为normalized数且阶码不为00000001时(若为00000001， 将阶码减1的时候会变为denormalized数，造成错误)，把这个数加上0xFF800000，即把阶码减1，实现除以2。
- 当该数为denormalized数或者阶码为00000001时，不能再对阶码进行操作，而应把尾数除以2，并应对舍入情况。首先将uf右移一位的结果赋值给
res，再判断uf的最低2位是否为11。若为11，则应进一位，其他情况舍去最后一位。最后判断uf的正负，若uf为负，在右移时符号位的1也跟着右移一位， 因此通过加上0x40000000恢复符号。
再判断一下阶码为00000001是是否成立，阶码为00000001时，指数大小为1 - 127 = -126。右移一位之后阶码变为全0，此时运用denormalized数的转换方法，指数大小仍为1 - 127 = -126不变，尾数则右移一位，达到目的。