【计算机系统】CSAPP_LAB01::Data Lab

《深入理解计算机系统》这本书的质量着实很高，内容丰富充实，课后的实验也都很有意思，也有一定的难度。当时做这鬼东西也是花了我不少时间最终还有几道题去网上查阅了答案才写完，勉强看看吧。

首先呢这个实验是有自动检查工具可以用的，但是一方面这个工具需要在Linux下才能运行，另一方面还要是32位的Linux，否则就要先安装gcc-multilib方便多版本编译。鉴于篇幅有限，我就不在这里介绍怎么使用Linux进行实验和怎么进行自动检查了。

在这里我使用的Linux环境是Windows SubSystem for Linux（WSL）的Ubuntu16，由于WSL只支持64位程序，所以需要一些骚操作才能成功运行这个DataLab的检查，这里给一个GitHub上的教程https://github.com/microsoft/wsl/issues/2468#issuecomment-374904520，按照里面的步骤去做就可以成功在WSL运行这个实验，效率不算很高但是至少可以用。

那么就直接进入正题，以下是各道题目的要求，代码和简要思路，这个实验主要就是要在限定的操作符和操作数下完成数据的转换。由于网上这个实验有多个版本的题目，以下是这个版本的题目目录：

int bitXor(int x, int y);

int tmin(void);

int isTmax(int x);

int allOddBits(int x);

int negate(int x);

int isAsciiDigit(int x);

int conditional(int x, int y, int z);

int isLessOrEqual(int x, int y);

int logicalNeg(int x);

int howManyBits(int x);

unsigned float_twice(unsigned uf);

unsigned float_i2f(int x);

int float_f2i(unsigned uf);

接下来是具体的题目：

1.仅允许使用~和&来实现异或

异或也就是两个数据不同的位变为1，相同的位变成0。由于限制了操作符，所以要多绕几圈才能做出来。

首先143行和144行将x进行位非运算然后和y与运算，得到r01，相反地操作得到r02。目的是将x与y不同的位变成1，而相同的位在两边都会变成0，但是由于0与0与会得到0，所以才要进行相反的操作才能覆盖所有异或的位。完成后，由于所有1的位都是异或的位，但是并不重叠，所以我们可以知道当r01和r10如果或运算在一起便能得到想要的结果。

然后由于限定了操作符只有与和非，所以不能直接让r01和r10或运算，于是在145行将其都非运算然后在与，由于前面进行了相反的操作，所以异或的位是相反的，而相同的位得到的都会是1且重叠，所以与后得到的所有0位就是异或的位。最后在146行进行一次非运算就得到了异或的结果了。

2.返回最小的二进制补码 这道就比较简单了，可以在155行先将-1转换为无符号数，便得到全部十六进制位为F的数，然后将其右移一位，由于是无符号数，所以采用了无符号右移，最高位会被0填充。再在156行和-1异或来把最高置0，再转换为int型便得到了最小值。这样的写法与机器的位数无关，比较实用。

3.如果x是最大的二进制补码，返回1；否则，返回0

这道也不太难，先在167行将输入加一，当输入值为最大值时，加一后会溢出得到最小值。然后将那个数在168行取反，再在169行让其与输入值异或。由于最大值加一溢出再取反有能得到原值的特性，所以异或后若为零，即两个值相等，也就是这个值满足这个特性。但是又由于-1也有这个特性，所以在170行再加入判断值是否为-1的语句，即！！（x+1），与操作后便能得到正确的返回值。

4.如果所有奇数位都为1则返回1;否则返回0

这道题要用到掩码的操作了。先在181行定义一个掩码只有奇数位为1的掩码，在182行让输入值与掩码与操作，然后再和掩码本身异或操作，若掩码后的值与掩码相同，即表示掩码位都为1，也就是说奇数位为1

5.返回-x

这个很简单，使用常用的取反加一操作来获得一个数的相反补码

6.如果x是ascii码中的0~9，返回1;否则返回0

先在206行定义掩码，以用于在之后提取出符号位。然后在207和208行分别让x与0和9的ascii码相减，得到的数在209和210来与掩码与运算获取符号位然后逻辑非。这样就能判断相减得到的数是正是负，只有当减0大于等于0且减9-1小于0时才返回1。最后将其与运算返回即可。

7. 实现x?y:z

这个是三元条件运算符，x为真时返回y，否则返回z。

先在221行和222行将x逻辑非取反再加一。若x为0，Tchoose会得到0，Fchoose会得到0xFFFFFFFF，若x不为0，Tchoose会得到0xFFFFFFFF，Fchoose会得到0，也就是它们总能得到相反的结果。然后在223行返回的时候，各自是y，z与Tchoose，Fchoose进行与操作，然后在或操作，与0与操作的数会被置零，与0xFFFFFFFF与不会改变，然后0与其他数或操作不会改变，于是便能返回要被选择的结果。

8.如果x<=y返回1否则返回0

还是使用掩码来判断大小。先在235行将其相减并用掩码取符号位，然后用逻辑非把符号位转为0或1，小于时会被置为1。然后再在236行利用异或操作判断是否相等，相等时结果会被置1，不等时被置0。这样就完成了一般情况下的判断。

但是两数相减是会有溢出的可能的，所以要有额外的判断。在237行将结果与后面的运算进行或操作，当x是负数y是正数是把结果强行置1，238行类似，当x是正数而y是负数时把结果强行置0。最后返回result。

9.实现！运算符的功能

限定不能使用逻辑非(!)运算符。由于逻辑非即是让0返回1，非0返回0的操作，所以利用x取反加一操作如果是正数符号位会变成1，如果是负数或0符号位便会为1，右移31位后只有负数和0会得到0的这三个特性。然后再在后面直接右移，这之后只有正数和0会得到0。这样子在将他们两个与操作，便只有0会保持0了。然后将得到的数在和1与清空高位，最后和1异或操作，0会变成1，1会变成0，便得到了答案。

10. 返回将X表示为补码所需的最小有效位数

这道开始就有难度了，目的是得到X的补码表示所需的最小位数，通常的想法是从高位往低位计数，数到第一个不是符号位的数出现，得到的数加一再和总数作差便是所需的最小位数，但是由于限定了90个操作符，所以以上的方法明显会由于数量超出而不能在这里使用。

于是在网上查找资料明白可以使用二分法来查找刚才说的那个最高数和计数。先做些准备操作，在267行通过右移来获得符号位-1或0，然后利用异或操作，若是负数会被异或为那个数的位非，这是为了让正数负数都能以1为最高位来计算。

然后在269行将那个数取逻辑非，得到的oppSign当被操作数是0时得到0，其他情况得到-1。在270行对操作数操作，若操作数是0会变成-1，其他情况会变成0，这便完成了准备。然后开始从271行开始二分法查找最高有效位。

我们将操作数右移16位，若得到的数等于0，意味着此时最高位在16位以下，于是右移4位后也会计数为0，若得到的数不等于0，意味着有最高位在16位以上，那么所需的最小位数一定不只16位，于是右移4位计数为16。然后再把数右移刚才的计数值，若计数为16，就会右移16位然后暴露出16位以上的位数到低16位的地方，若小于16位则不需要右移，因为位数本来就在16位以下的地方。

然后从273行再进行类似操作，这次改为右移8位，然后4位...也就是二分法来重复上面的步骤。以此类推到右移1位为止。这便能查找到最高位的位置，再280行将所有计数加在一起便得到了初步的答案了。

接下来在来特殊处理其他情况，也就是0最少需要返回1。在281行我们将这个计数先加2，若被计算数是0，加2后与oppSign与会得到0，此时其他情况由于oppSign是-1，所以与操作后不变。然后再让其与268行得到的negateOps或操作可以使0加1，其他情况不变。这样便解决了0最少需要返回1的情况，也就完成了这道题目。

11.返回以unsinged表示的浮点数二进制的二倍的二进制unsigned型

接下来的题考察了对浮点数的掌握，从这里开始就不再对运算符有什么要求了。首先利用掩码来得到输入的浮点数的符号位和阶码。然后在300行先判断一下阶码是不是0，分多个情况来解决。

当阶码为0时代表可以在保留符号位的情况下直接整体乘二也就是左移一位，因为不会导致阶码错误，然后在312位还原符号位并返回。

当阶码不为0时，先判断阶码是不是位数全为1，阶码全为1代表这个数NaN，所以按照要求直接返回原来的数。

当阶码不为0也不是全部位为1时，乘二的操作就是直接把阶码加0x00800000，也就是让阶码部分加一，代表内容位左移乘二了一次，而在305行，如果乘二后的浮点数阶码变为全为1（也就是乘二前阶码为0x7F000000，代表为无穷，因为内容位不为0时代表NaN），那就将其与负无穷与运算，这样可以将输入的数置为无穷有不会影响符号位。最后在314行返回处理完的数便解决了这道题。

12.返回int x的unsigned浮点数的二进制形式

将整数转换为浮点数需要记录左移的次数和得到的浮点数的小数部分，小数部分是数的核心，左移次数将会变成数的阶码。

首先在328行剔去输入数为0这个特殊情况。然后由于浮点数的正负只与符号位有关，小数部分固定是正数表示，所以先利用掩码获取符号位，然后在332行改变输入数的正负，将负数变为正数来操作。

再利用333行的循环不断左移那个小数直到小数的最高有效位被移到最高位为止，并记录下左移的次数，再由于小数点前的1会被隐去，所以再在循环结束后多左移一次并记录，这个次数将会变为阶码，左移完的数将会变为浮点数的小数部分。

然后把小数移到最高位后需要把小数右移到阶码后面，那就还需要判断在右移途中是否需要进行舍入操作。由于C支持的是过半舍入，所以真正可能产生有效舍入的情况仅当小数的第9位是1且低8位不全是0时或者虽然低8位全为0但第9和第10位都是1。于是从341到346进行判断并赋值给一个额外的舍入加一位adds，这样条件就都完成了。

最终返回：符号位+右移9位的小数部分+经过偏移的阶码+舍入位。

13.返回unsigned uf的整型数的二进制形式

上一题是把整型数转为了浮点数，这一题就是它的反向操作。原理类似于上一题。

先分离出符号位，阶码和小数。然后在364行将阶码进行偏置(-127)得到真正数值。在365行和367行判断经阶码计算后的数是否会超出int的表达范围，超出的话直接返回0x80000000，过小的值依据题目要求也是直接返回0。

接着我们希望把小数直接用来作为整数int的值，由于小数点左边的1被省去所以需要先在小数最低位补一个1。然后由于之前浮点数的小数被限制长度为23位，这里可以想象一下，如果阶码原本就是23，那么也就是说整数会是x的2的23次方，那么实际上也就是说小数部分并不需要移动。由于左移右移各自是给小数乘二或除二，我们直接把小数看作是转换好的整数，那么左移右移的次数自然就是程序里那么写了。

移位部分可能比较难理解，多看几次，自己多画几个情况会比较好想。最后根据符号位判断是否需要取反加一获得对应符号然后返回结果即可。