《深入理解计算机系统》一书是计算机系统入门的极好选择，从其第三版的豆瓣评分 9.8分 可见一斑。该书的起源是卡耐基梅龙大学 计算机系统入门课【Introduction to Computer System】的讲义，与其配套的还有发布在其官网上的实验，这也正是【CSAPP-LAB】这个系列所要【DIY】的。
这个系列包含哪些内容？
WARNING1:本系列不提供实验环境的搭建教程。
WARNING2:CSAPP的LAB会不定时优化，所以本系列的解答有时效性。
这次实验名为 Data-Lab，是从位级视角来看待整形数与浮点型数。实验使用高度受限的c语言子集实现一些高级功能，如只用&和~实现 x^y（详见bitXor(int x,int y)），我们称之为谜题。共有13个待完成的c语言函数如下表所示：
| 名称 | 描述 | 分数 | 指令数 |
|---|---|---|---|
| bitXor(int x,int y) | 只用&和~实现 x^y | 1 | 14 |
| tmin(void) | 返回最小的补码数 | 1 | 4 |
| isTmax(int x) | x是最大的补码数吗? | 1 | 10 |
| allOddBits(int x) | 所有的奇数位都为1吗? | 2 | 5 |
| negate(int x) | 不用-号得到 -x | 2 | 5 |
| isAsciiDigit(int x) | 是字符0~9中的ACCSI码吗? | 3 | 15 |
| conditional(int x,int y,int z) | 实现x ? y : z | 3 | 16 |
| isLessOrEqual(int x, int y) | x\(\leq\)y 吗? | 3 | 24 |
| logicalNeg(int x) | 不用!号得到 !x | 4 | 12 |
| howManyBits(int x) | 至少多少位能无歧义地表示一个补码数? | 4 | 90 |
| floatScale2(unsigned uf) | 2*f 的位级表示是多少? | 4 | 30 |
| floatFloat2Int(unsigned uf) | (int) f 的位级表示是多少? | 4 | 30 |
| floatPower2(int x) | 2.0*x 的位级表示是多少? | 4 | 30 |
注意事项
对于整型谜题（除了最后三个函数），实验要求如下：
对于浮点型谜题（最后三个函数），他在整型谜题的基础上作了适当放宽：
^ 唤作按位异或，相同为0，不同为1。由于操作符限制，这题显然是利用x y ~ &构造两个新数，使他们按位与（&）的值恰好等价与x^y。
参考答案：
int bitXor(int x, int y) { // 以4位二进制 （x: 1100 y: 1010）为例，这就涵盖了所有的4种排列。 int tep1 = ~(x&y); // tep1: 0111 int tep2 = ~((~x)&(~y)); // tep2: 1110 return tep1&tep2; // 0110}最高位为1，其余位全为0便是最小的补码数。
参考答案：
int tmin(void) { return (1<<31);}最高位为0，其余位全为1便是最大补码数。
参考答案：
int isTmax(int x) { int y = x + 1; return !(y + y)&!!y; // 如果x是最大的补码数，那y+y就溢出得到0，!0得到1。但是要排除x是 0x11..1的情况}注意可以用移位操作，那么便能直接构造出奇数位全为1、偶数位全为0的数。
参考答案：
int allOddBits(int x) { int mask = 0xAA; // 二进制：10101010 mask = (mask<<8)+mask; mask = (mask<<16)+mask; // 1010...1010 return !((x&mask)^mask); // x奇数位全为1，此时x&mask的值仍是mask，mask^mask是0；若x奇数位不全为1，此时x&mask的值一定和mask不同，(x&mask)^mask的值非0。}由补码数的性质易得。
参考答案：
int negate(int x) { return (~x+1); }显然不可能枚举所有字符与x作比较，只能从字符的共性入手。
参考答案：
int isAsciiDigit(int x) { // 如果x与0x30从第四位起完全相同，那x一定属于ASCII数字字符 int xh4 = (~0x7)&x; // 给x低3位清零 // 如果x与0x28从第二位起完全相同，那x一定属于ASCII数字字符 int xh2 = (~0x1)&x; // 给x最低位清零 return !(xh4^0x30)|!(xh2^0x38);}根据x是否为零决定返回y还是z，所以这题的关键正是根据x的不同构造出两个不同的位级表示。
参考答案：
int conditional(int x, int y, int z) { int cond = ~(~(!x)+1); // x=0，return 0X00000000; x不等于0，return 0xFFFFFFFF; return (cond&(y^z))^z; // x=0, return z; x不等于0，return y^z^z = y;}根据x与y符号是否相同，分别作比较。
参考答案：
int isLessOrEqual(int x, int y) { int cond1 = (y>>31)&((x>>31)+1); // x最高位为0,y最高位为1时 返回 1； int cond2 = !((y>>31)^(x>>31)); // x y 最高位相同时 返回1，不同时 返回 0； int cond3 = !!(x^y); // x y 不相等时为1，相等时为0； int cond4 = !(((x+(~y+1))>>31); // x-y最高位为0时返回1。 return !(cond1|(cond2& cond3&cond4)); // x>y两的两种情况都返回0，x<=y时返回1}0与-0的符号位都为0，而1与-1的符号位不同，可以利用这个特点。
参考答案：
int logicalNeg(int x) { int cond = ((~x+1)^x)>>31; // x=0或0x80000000 时，x与~x+1最高位相同，所以cond返回0；否则，x与~x+1最高位不同，cond返回0xFFFFFFFF。 return (cond+1)&((x>>31)+1); // 排除x=0x80000000情况，只有x=0时返回1}这题换种说法便是：第一个与最高位不同的位是哪一个？由于最高位到底是0是1不重要，因此可以把最高位为1的x按位取反。问题转化为：从高到低，第一个为1的位是哪一个？如果每次右移一位再判断是否为零，90个操作符也未必够用，所以这里可以考虑二分法思想。
参考答案：
int howManyBits(int x) { x = (x>>31)^x; // x最高位为1，x按位取反；x最高位为0，x不变。 int t1 = ~(~(!(x>>16))+1); // x右移后为0则返回0，非0则返回0xFFFFFFFF int x1 = t1&((x>>16)^x)^x; // 如果x右移后为0，x1仍返回x；如果x右移后非0，x1返回x右移后的值。 int t2 = ~(~(!(x1>>8))+1); int x2 = t2&((x1>>8)^x1)^x1; int t3 = ~(~(!(x2>>4))+1); int x3 = t3&((x2>>4)^x2)^x2; int t4 = ~(~(!(x3>>2))+1); int x4 = t4&((x3>>2)^x3)^x3; int t5 = ~(~(!(x4>>1))+1); int x5 = t5&((x4>>1)^x4)^x4; return (t1&16)+(t2&8)+(t3&4)+(t4&2)+((t5&(2^x5))^x5)+1; // 注意0x2需要3位才能无歧义表示，所以t5不能不能如前者一样操作}ggffff