ccsp深入了解计算机系统配套datalab-handout实验

修改bits.c的副本，使其通过所有在不违反任何编码准则的情况下在btest中进行测试。
（2）源程序清单或者主要伪代码；
①.bitAnd：
这个函数是将两个数x，y进行与运算。根据以前学的数电的知识，利用摩根定理，/（x&y)=_x|y,再次求反可得结果

②.getByte：
要得到X的第n个字节。只需要简单的把留的字节移到最右端，再与0xff相与即可

③.logicalShift
实现逻辑右移。即在右移的过程之中在左端都填零而不是填符号位。先求出一个左端有n个0，右端是32-n个1的常数，得到这个常数之后就可以和x进行算术右移后的结果相与，这样左端的n位就=0，满足逻辑右移

④.bitCount
计算1的个数。也就是把32位的数都加起来。可以通过移位计算的方法，其中也有分治的思想在里面。先分成两位两位的计算，x和0101…01相与（也就是看x的第1,3，。。n-2位是不是1），x向右移一位再和0101.。01与（同理，是为了看x的0,2,4.。，n-1是不是1），前面两个计算得到的结果加起来,再把这个结果看成16个两位的数，把这两个数加起来就是最终1的个数。
如表格所示，每格=上一行的两个数字之和，想要执行这样的加法，就要对应和0x55555555或0x33333333…进行与运算，再相加，得到最后结果

示例：


⑤.bang:
不用操作符！，来实现！的功能。每一位的数进行或运算，再取反，和1相与就得到结果
不是一位一位的与，因为这样操作符数不够，需要分治的，先高十六位和后十六位相与，得到16位的结果，再把16位分成高8位和低8位，进行或运算，得到8位的结果，再拆成高四位和低四位，进行或运算，一直进行下去直到只剩一位，根据这个位判断结果，将该位取反和1与，得到结果。如果这位为1，说有32位中肯定有一个1，取反=0，和1与结果=0，返回0，否则返回1.

⑥.tmin：返回最小的二进制补码，也就是0x80 00 00 00

⑦.fitsBits：
x是否可以用n位二进制整数表示，能则返回1，否则返回0.
x是肯定能用32位表示的，能否用n位表示可看成符号拓展的逆过程。所以经过x<<(32-n)>>(32-n)后若与原来的x相等则表示能用n位二进制补码表示x。判断相等可利用异或，相同为0，不同为1，前面加个!得到正确映射关系。

⑧.divpwr2：计算x/(2^n)
因为除法是向0取整，而右移位是向负取整，如果是正数，就只需要x右移n位，但是如果是负数，就要考虑到舍入的问题，需要判断舍去的n位=0，或者说有没有1，通过移位得到一个高32-n位全是0，低n位全是1的数，把这个数和x相与，如果结果进行两次！运算，if=0，说明没有一个1，就不存在舍入。否则，还要看x的符号位和n的大小，n=0不存在舍入，n>0才有可能，所以需要考虑n的大小。

⑨.negate:取反，求补码即可

⑩.isLessOrEqual：
判断x<=y是否成立。分成三种情况，1.x是负数，y是正数，只需要看两个的符号位；2.x是正数，y是负数，返回0；3.x，y同号，算出x-y，看结果的符号位，符号位=1并且两个不相等并且不符合情况2

⑪.ilog2：求以2为底的对数，log2x
只需要看1最高在哪一位。用分治的方法，移位判断高16位是否=0，如果等于，说明高16位肯定没有1，就往低16位继续二分的检查，8、4or6…
如果高16位不等于0，就往高十六位继续二分检查，24、20or28，二分过程中检查当前位如果=1，就加上当前位数（用与运算实现），
移位位数s=原基础s-分治位数的一半+（-1）^t分治位数，t=0，可以看出就往低位二分，t=1，就往高位二分。

⑫.float_neg
参数格式虽为unsigned型，但实为浮点单精度表示，返回-uf
根据浮点数的表示规则，先通过移位求出exp和frac，根据这两个判断是否是特殊的无穷或者无法表示的数，这种情况就直接返回参数uf
否则就通过和0x80000000异或，符号位取反，其他位不变。

⑬.float_i2f：将一个int型的数转成float单精度表示法返回
先设置符号位，通过一个循环右移，当移后结果=1，说明数的左边只有一个1，此时就能求得阶码E。考虑特殊情况+0直接返回0，0x80000000返回0xcf000000
接下来就求一般情况，因为传进来的参数是一个整数，所以不用考虑非规格化数，直接exp=127+E，求frac时，根据阶码E大小，如果<=23需要x左移23-E位，如果>23，就有一些尾数需要舍掉，向右移E-23，再和0x7fffff相与，得到frac。
这里就涉及到精度问题，这个整数是否能用浮点数精确表示，不能的话取谁。先是用一个res把舍掉了E-23的情况存起来，再计算丢弃的位数部分dq，比较丢弃的dq和两个浮点数间隔2^{(E-24)大小，如果dq>2}(E-24)那就说明暂时的结果加一res+1会比res更接近真实值，如果dq=2^(E-24),就根据向偶数舍入的原则，判断frac的最低位，如果是1（奇数）就进位，也就是res+1.其他情况就直接return res


⑭.float_twice:计算浮点数uf2，返回浮点数格式的结果
移位算出exp和frac，判断是否是特殊的+0，-0，NaN，无穷，是的话就直接返回
如果是规格化数，2就直接是阶码E+1，即exp+1
如果是非规格化数，就是frac位2，左移一位，同时判断是否会有进位，进位exp就等于1
最后把符号位s、exp、frac或运算合并起来，返回。

15.突然发现实验报告少写了一个-_-，判断x正负
本来只需要将符号位移到最低位和0x1相与就得到了，但是0这个特殊情况就加上后面的~(!x)+1，如果x=0，后面这段结果=1，返回1，如果不等于0，！x=0,0再取反加1=0，正好返回符号位
实验结果及分析：


用./dlc编译器检查，通过检查，功能实现全部正确
整数部分的函数只用操作符，运行很快出结果，float型的用到if，while等语句，运行时间比int的明显长
收获与体会：
看起来题目都挺简单，debug也要de很久，但是真正要只用操作符实现还是挺难的。比如实现！运算和求log2x的，我用到了分治的方法，因为操作符的数量的限制，减少遍历的次数，就想到了分治，但是想要进行分治，你得有个结束的条件，自己想到的都是如果…,就做这些操作，否则就怎么怎么样，这里只能用操作符，还是比较难想到怎么用操作符来实现和if，判断语句的功能。log2x的这个分治，向高位分治还是低位分治，变化之后的位数，很难直观的就能得到一个表达式，幸好只有32位，还能枚举一下找规律。计算1的个数这题也很难，本来写前面3题的时候觉得还觉得挺简单，但是到这题就卡住了，想遍历32位操作符又不够。
一些有舍入的题目也很难，得先很了解移位和各种运算*/±的规则，刚开始不是很清楚，经过这个实验，算是深入了解了，还有浮点数的运算，不用电脑自己判断一个整数能否用float单精度精确表示，怎么取舍。通过小值常数的移位取反得到大值常数，对各个运算都有一定熟悉度和掌握。