csapp-Datalab

Posted on | In | Visitors:
Words count in article: 2k

序

　　这是csapp系列的第一篇文章。本文主要讲一下关于 datalab [Updated 11/2/18] 的解决方法以及简单的思路。如果有哪里写的不清楚或者有问题，欢迎联系我修改(右下角小图标点开即可对话)。
注：其中某些题目应该有更优的解法。以下仅供参考

bitXor

题意：用 ~ 和 & 运算符实现 Xor 运算符
思路：我们知道Xor运算符是对每一个位，相同的话返回0，不同的话返回1。题目中仅有 & 是双目运算符，那么我们可以采用 & 运算符获得均为1的位，再取反，同理，用 & 和 ~ 获得均为 0 的位，再取反，最后两者再进行 & ，即可得到答案。
解：

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

tmin

题意：让你输出反码下的最小值
思路：水题。。直接由定义得。
解：

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

isTmax

题意：判断一个数是否为反码下的最大值
思路：若x为Tmax，x+1取反之后应该等于x。故可以采用取反与原数Xor的思路。但要注意，0xffffffff也满足该性质，需要排除。
解：

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

allOddBits

题意：判断一个数是否所有的奇数位都为1。(位的序号从0到32)
思路：我们知道，若奇数位为均为1，则右移一位后偶数位均为1，两者相与的话为0xffffffff。利用该性质可得到答案。不过要注意，偶数位上的1会影响我们的判断，故需要利用掩码将其过滤。(0xA = 1010)
解：

1
2
3
4
int allOddBits(int x) {
	x = x & 0xAAAAAAAA;
	return !(~(x|(x>>1)));
}

negate

题意：求一个数的相反数。
思路：水题，由常用结论我们知道，-x = ~x + 1
解：

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

isAsciiDight

题意：判断一个数字是否在(0x30和0x39)之间
思路：这道题我想不出比较好的解法。只能暴力判断。即先看2进制下的前26六位是否有值，然后在看下后6位。x+6仍然小于0x40，则x小于0x3。.再看下剩下六位中前两位是否均为1，是的话x大于0x30。
解：

1
2
3
4
5
int isAsciiDigit(int x) {
	int t = x & 0xFFFFFFC0;
	x = x & 0x3F;
	return !t&!((x+6)&0x40)&(x>>4)&(x>>5)&1;
}

conditional

题意：实现三目运算符 ？：
思路：先用！判断是否为x是否为真。然后在利用与的性质：一个数和0xffffffff相与结果为其本身，和0相与结果为0。
解：

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

isLessOrEqual

题意：判断x是否小于等于y
思路：x<=y 则 y - x >= 0。分别取出x和y的符号，进行判断。若y大于0，x小于0，则显然为真。若y小于0，x大于0，则显然为假。剩下的异号的情况则用y + (-x) 判断即可。
解：

1
2
3
4
5
int isLessOrEqual(int x, int y) {
	int sgnx = (x>>31)&1;
	int sgny = (y>>31)&1;
	return !sgny & sgnx | !(sgnx^sgny) & !((y + (~x+1))&(1<<31));
}

logicalNeg

题意：使用其他的逻辑运算符和位运算符实现 ！运算符
思路：我们知道，一个数的相反数等于其本身的数只有0(注意：~0x80000000 + 1 = 0x80000000)
解：

1
2
3
int logicalNeg(int x) {
	return ((~x+1 | x)>>31)+1;
}

howManyBits

题意：给一个数字x,求出要表示出x需要的最少的位数。
思路：个人觉得，本题难度很大。以下的思路可能并不算很好，不过还是可以通过的。
　　首先，我们知道，对于一个n位的二进制数，能表示的数字的范围为 -2n ~ 2n - 1。故对于输入的整数x，我们可以先将其变成正数，即下方的_mask。现在就只需考虑正数。题目转化为求最高位的1。但最高位的1不是很好求，我们可以将其转化为求二进制下x含有多少个1。
　　假设当前最高位的1位于第5位，右移并按位或后，第五位，第四位均为1，再向右移两位并且按位或，第二、三、四、五位均为1，以此类推，我们将最高位的1后的所有位全部变成了1。(假设原数为0x0A0BA973，经过处理之后就会变成0x0FFFFFFF)。
　　接下来考虑如何求出所有位上1的总数。我们可以考虑使用分段的办法。考虑以下的32位二进制数,我们将其分成四个部分：
　　00000010 | 00100111 | 11010010 | 00110001
接下来我们采用掩码分别将其各个部分的1的总数做一个累加，掩码应为：
　　00000001 | 00000001 | 00000001 | 00000001
即对每一个部分，掩码的值都是1。接下来用&运算符获得最低位的数字，四个部分分别为0,1,0,1. 然后，再将x右移一位，再继续进行&运算，以此类推，最后得到四个部分的值分别为：1,4,4,3。即最后得到的sum为：
　　00000001 | 00000100 | 00000100 | 00000011
最后再利用掩码0xff(11111111)，分别得到各个部分的值，做一个累加，得到答案(别忘记+1)。
解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int howManyBits(int x) {
 	int _mask = (x&(1<<31))>>31;
	x = x^_mask;
	x |= x>>1;
	x |= x>>2;
	x |= x>>4;
	x |= x>>8;
	x |= x>>16;
	int sum = 0, mask = 0x1 | 0x100 | 0x10000 | 0x1000000;
	sum += x & mask;
	sum += (x>>1) &mask;
	sum += (x>>2) &mask;
	sum += (x>>3) &mask;
	sum += (x>>4) &mask;
	sum += (x>>5) &mask;
	sum += (x>>6) &mask;
	sum += (x>>7) &mask;
	return (sum&0xff) + ((sum>>8)&0xff) + ((sum>>16)&0xff) + ((sum>>24)&0xff) + 1;
}

floatScale2

题意：本题给一个无符号数，让你把它看成一个浮点数(都是32位)，让你输出x * 2 的值
思路：比较简单，按照浮点数1,8,23的分布将符号，指数，尾数分别取出，并分类讨论即可。
解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned floatScale2(unsigned uf) {
	unsigned frac = uf&0x007fffff;
	uf>>=23;
	unsigned exp = uf&0xff;
	uf>>=8;
	if (!exp) {
		frac <<= 1;
		int t = frac>>23;
		if (t) 	{
			frac = frac & 0x007fffff;
			exp++;
		}
	} else if (exp != 0xff)  exp++;
	return (uf<<31) + (exp<<23) + frac;
}

floatFloat2Int

题意：给你一个无符号数，并将其看成浮点数(32位)，要求输出(int)x的值
思路：本题依然在考察对浮点数的基本理解。解决的思路同上题类似，不再赘述。另外提醒一下，本题有个坑，求得到的bias直接拿来进行右移运算或左移运算会存在问题：>> 和 << 运算符当偏移量超过32时，会自动进行取模运算，故有可能使得结果出现错误。左移的话有可能还会导致答案溢出。记得分类讨论。
解：

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) {
	int frac = uf & 0x007fffff;
	uf >>= 23;
	int exp = uf & 0xff;
	uf >>= 8;
	int sgn = uf;
	if (exp == 0xff) return 0x80000000u;
	else if (!exp) return 0;
	else {
		frac |= 0x800000;
		int bias = exp - 0x7f - 23;
		if (bias < 0) {
			bias = -bias;
			if (bias >= 32) bias = 31;
			frac >>= bias;
		}	else if (bias > 0) {
			while(bias) {
				frac<<=1;
				bias--;
				if (frac < 0) return 0x80000000u;
        	}
		}
		if (sgn) return -frac;
		else return frac;
	}
}

floatPower2

题意：给一个整数x，要求输出2.0x的值。
思路：同样，本题依然在考察对浮点数存储的基本理解。要注意的是，+INF的是指exp为0xff，frac为0的值。NaN指的是exp为0xff，frac不为0的值。0的浮点数表示依然为0。
解：

1
2
3
4
5
6
7
8
9
10
unsigned floatPower2(int x) {
    int sgn = 0, exp = 0, frac = 0;
    if (x < -126 - 23) return 0;
    else if (x < -126) frac = 1 << (149+x);
    else {
	    exp = x + 127;
	    if (exp > 0xff) return 0x7f800000;
    }
    return (exp<<23) + frac;
}

结尾

　　倘若一切顺利，你最终将得到类似这样的一张图片：
　　Datalab_final
　　那么恭喜你，你的第一个实验————Datalab通关啦！

------------- The artical is over Thanks for your reading -------------