CSAPP dataLAB实验报告

一、实验目的

本实验目的是加强学生对位级运算的理解及熟练使用的能力。

二、报告要求

本报告要求学生把实验中实现的所有函数逐一进行分析说明，写出实现的依据，也就是推理过程，可以是一个简单的数学证明，也可以是代码分析，根据实现中你的想法不同而异。

三、函数分析

1、bitAnd函数

函数要求：

实现分析：

由于限制了只能使用~和$|$这两种运算符，所以可能情况数很少，穷举一下表达式就出来了。

函数实现：

int bitAnd(int x, int y) {
  return ~(~x|~y);
}

2、getByte函数

函数要求：

实现分析：

主要想法是先将$x$右移$n$个字节，再截取出最右的字节。
1个字节对应2个十六进制位，2个十六进制位对应8个二进制位。
所以右移$n$个字节$=$右移$n*8$个二进制位。
然后再用$0xFF(255)$相与，截取出最右的字节即可。

函数实现：

int getByte(int x, int n) {
  return (x>>(n<<3))&255;
}

3、logicalShift函数

函数要求：

实现分析：

右移很简单，但是逻辑右移补的是符号位。。。
所以考虑构造一个数$t$来相与，把补的$1$变成$0$，同时保证其它的位不变。
哪些位不需要变呢？初始状态下$x$的右$31$位肯定都需保证不变，于是构造$\sim(1<<31)$。
然后按题意将其右移$n$位，最后左移$1$位给符号位。
最后把答案和$t$相与，就可以去除补上的符号位$1$啦。

函数实现：

int logicalShift(int x, int n) {
  int ans=x>>n;
  int t=(~(1<<31)>>n<<1)+1;
  return ans&t;
}

4、 bitCount函数

函数要求：

实现分析：

一开始的构想是每次把$x$右移$1$位，与$1$相与，并将每次与的结果累加起来就是答案。
道理是没错，但是这里限制只能用$40$个运算符，按上面搞法都$64$个了。。。
所以考虑用分治思想来优化，使得一次运算能完成多次累加。
第一步运算，将$x$相邻两个二进制位分为一组。组内让右移$1$位再与$1$相与的结果，和不右移与$1_2$相与的结果相加，这样每组内得到/存的就是该组内二进制$1$的个数。
第二步运算，将$x$相邻四个二进制位分为一组。组内将下属的两个两位数相加，就可以得到整个组内二进制$1$的个数。具体来说就是把两个两位数移到组内右侧，相加。即让右移$2$位再与$11_2$相与的结果，和不右移与$11_2$相与的结果相加。
以此类推。。。
第三步运算，合并了相邻八个二进制位中$1$的个数。
第四步运算，合并了相邻十六个二进制位中$1$的个数。
第五步运算，统计完成。
代码中的$t1,t2,t3,t4,t5$是为了消除逻辑右移中符号位带来$1$的影响。

函数实现：

int bitCount(int x) {
  int t1=0x55|(0x55<<8);
  int t2=0x33|(0x33<<8);
  int t3=0x0F|(0x0F<<8);
  int t4=0xFF|(0xFF<<16);
  int t5=0xFF|(0xFF<<8);
  t1=t1|(t1<<16);
  t2=t2|(t2<<16);
  t3=t3|(t3<<16);
  x=(x&t1)+((x>>1)&t1);
  x=(x&t2)+((x>>2)&t2);
  x=(x&t3)+((x>>4)&t3);
  x=(x&t4)+((x>>8)&t4);
  x=(x&t5)+((x>>16)&t5);
  return x;
}

5、bang函数

函数要求：

实现分析：

$0$有个独有的特性“取相反数不会改变符号”。
所以当$x$与其相反数相或时，只有当$x=0$时符号位才为正，否则符号位为负。
但是这里直接判符号位不可行，因为不能用$!$。

换个方向，当$x$与其相反数相或时，若右移31位，只有当$x=0$时值为$0$，否则值一定为$0xFFFFFFFF$。如此再加上$1$就满足题目要求了。

函数实现：

int bang(int x) {
  return (((~x+1)|x)>>31)+1;
}

6、 tmin函数

函数要求：

实现分析：

众所周知，二进制补码没有负数的概念。
于是肯定是$-0$，即$1<<31$。

函数实现：

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

7、 fitsBits函数

函数要求：

实现分析：

如果$x$能表示为$n$位二进制补码整数，它的范围一定在右$n$以内。
那么将其左移$32-n$位再右移$32-n$位时，就没有溢出/数字损失，其大小不会改变。
最后判断左右移后的数是否与原数相等即可，判断方法是相异或。

然后发现题目不提供减号。。。不过根据补码里相反数定义$-x=\sim x+1$，$32-n=32+\sim n+1=33+\sim n$。

函数实现：

int fitsBits(int x, int n) {
  int t=33+~n;//32-n
  int ans=x<<t>>t;
  return !(ans^x);//异或可以用来判断是否相等
}

8、divpwr2函数

函数要求：

实现分析：

问题还是出在逻辑右移补符号位。。。
这里我分情况讨论。
若$x$为正数，直接$x>>n$。
若$x$为负数，$(x+(1<<n)-1)>>n$就是答案。
换掉减号：$0=\sim0+1$，故$-1=\sim0$。

函数实现：

int divpwr2(int x, int n) {
  int tag=x>>31;  
  return (x+(((1<<n)+~0)&tag))>>n;
}

9、 negate函数

函数要求：

实现分析：

根据教材里补码相反数定义得$-x=\sim x+1$。

函数实现：

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

10、isPositive函数

函数要求：

实现分析：

直接判断大于0不好弄，但是判断$0$和负数还是很简单的。
于是从反面考虑，用$!x$判断$x$是否为$0$,用$x>>31$取出符号位来判断是否为负数.
这两个都不是，那就是正数了QAQ。

函数实现：

int isPositive(int x) {
  return !(!x|(x>>31));
}

11、isLessOrEqual函数

函数要求：

实现分析：

这里的坑在于可能溢出。
毕竟可以搞极大正数减极大负数。
于是分情况讨论。
如果符号位相同，直接减。
如果符号位不同，则变为判断$x$的符号位是否为$1$。

还有判断时应该计算$y-x$而不是$x-y$，因为$y=x$和$y>x$是同号且同结果的。

函数实现：

int isLessOrEqual(int x, int y) {
  int tt=(y+~x+1>>31)&1;
  int tx=(x>>31)&1;
  int ty=(y>>31)&1;//小心极端情况
  return ((tx^ty)&tx)|(!(tx^ty)&!tt);
}

12、 ilog2函数

函数要求：

实现分析：

本题实际上是判断$x$的最高位在哪里。
然后发现$x$一定是正数且符号数最多$90$，可暴力累加。

以上想法过于暴力不可取，我想了一个机智一点的算法：二分查找。
$t$是一个范围基准点
第一次搜索，范围大小$32$，判断$x$是否越过了中位数$16$。如果越过了，就在左半边找，$t+16$，否则在右半边找。
第二次搜索，范围大小$16$，判断$x$是否越过了中位数$24/8$。如果越过则去左半边，$t+8$，否则去右半边。
以此类推。。。
（双感叹号！！可以把一切正数变为1）

函数实现：

int ilog2(int x) {
  int t=(!!(x>>16))<<4;
  t=t+((!!(x>>8+t))<<3);
  t=t+((!!(x>>4+t))<<2);
  t=t+((!!(x>>2+t))<<1);
  t=t+(!!(x>>1+t));
  return t;
}

四、实验总结

本次实验中$T3、T4、T5、T8$非独立完成，需予以重点关注。
$T3$的问题出在：
不知道如何使得$t$覆盖到符号位。然而后来发现：逻辑右移后高位全变0，符号位就在数据最高位的左边一位。
$T4$的问题出在：
没想到这种过于高妙的分治方法。
$T5$的问题出在：
没想到，相对于其它数，0有个独有特性“取反不变号”。
$T8$的问题出在：
不知道当$x$为负数时该怎么处理，最后发现是书上$P73$的结论。
这些问题均通过向巨佬同学请教、上网搜索得以解决。

建议：希望实验文档内容能与bits.c内容统一起来。我倾向于多加几道题，这样更有利于同学们增强代码能力。