CMU 15-213 Lab1 Data Lab
课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html
课程资料：https://github.com/EugeneLiu/translationCSAPP
课程视频：https://www.bilibili.com/video/av31289365/
这一部分回顾CSAPP的Data Lab。
bitXor
| $x$ | $y$ | $x\text{^}y$ |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
不难看出
代码如下
int bitXor(int x, int y) {
return ~((~((~x) & y)) & (~((~y) & x)));
}tmin
代码如下
int tmin(void) {
int x = (1 << 31);
return x;
}isTmax
首先给出如下结论，只有当且仅当
才成立
证明：
假设
那么
另一方面
所以
等价于（其中$k\in \mathbb Z$）
利用二进制数表示的唯一性可得
即
有了如下结论，可以先利用如下代码判断x是否为-1或$\text{Tmax}$：
//判断是否为xffffffff或Tmax，如果成立，则y3为0
int y1 = x + 1;
int y2 = ~x;
int y3 = (y1 ^ y2);接着要排除-1的情形，这一点只要利用-1的表示为全1即可
//判断是否为0xffffffff，如果成立，则z2为1
//如果x为0xffffffff，则z1为0
int z1 = ~x;
int z2 = !z1;最后进行简单的操作即可，完整的代码如下
int isTmax(int x) {
//判断是否为xffffffff或Tmax，如果成立，则y3为0
int y1 = x + 1;
int y2 = ~x;
int y3 = (y1 ^ y2);
//判断是否为0xffffffff，如果成立，则z2为1
//如果x为0xffffffff，则z1为0
int z1 = ~x;
int z2 = !z1;
//生成结果，如果x为Tmax则r=False，所以要取非
int r = (z2 | y3);
r = !r;
return r;
}allOddBits
设置mask：0101,0101,…,0101，然后将x与其做异或运算，最后取非即可，代码如下
int allOddBits(int x) {
//0101,0101
int y1 = 170;
//0101,0101,0101,0101
int y2 = (y1 << 8) + y1;
//0101,0101,0101,0101,0101,0101,0101,0101
int y3 = (y2 << 16) + y2;
//取交集
int y4 = (x & y3);
//判断是否相同
int y5 = (y4 ^ y3);
return !y5;
}negate
利用第三讲的内容可知
代码如下
int negate(int x) {
return (~x) + 1;
}isAsciiDigit
分为两部分，第一部分判断4到7位（从右往左数）是否为0011，只要利用移位运算和异或运算即可：
int y1 = !((x >> 4) ^ 3);第二部分判断0到3位，注意第0位是没有影响的，所以只要判断其他几位是否为1即可：
//判断末4位范围
//判断第3位是否为1
int y2 = (x & 8) >> 3;
//判断第2位是否为1
int y3 = (x & 4) >> 2;
//判断第1位是否为1
int y4 = (x & 2) >> 1;另外不难发现如果第3位为1，则1,2位应该必然为0；如果第3位为0，则其他位置可取任意值，所以初步的代码为
int z1 = y1 & (!y2);
int z2 = y1 & y2 & (!y3) & (!y4);
int z3 = z1 | z2;但是这样会超过运算数限制，所以要对上述操作进行优化，首先不难看出y1可以提取出来，另一方面，
所以
最终得到如下代码
int z1 = (!y3) & (!y4);
int z2 = !y2;
int z3 = y1 & (z1 | z2);完整的部分如下：
int isAsciiDigit(int x) {
//范围为0011,0000到0011,1001
//判断0011部分是否相同
int y1 = !((x >> 4) ^ 3);
//判断第3位是否为1
int y2 = (x & 8) >> 3;
//判断第2位是否为1
int y3 = (x & 4) >> 2;
//判断第1位是否为1
int y4 = (x & 2) >> 1;
//如下代码会超过运算数限制
//int z1 = y1 & (!y2);
//int z2 = y1 & y2 & (!y3) & (!y4);
//int z3 = z1 | z2;
int z1 = (!y3) & (!y4);
int z2 = !y2;
int z3 = y1 & (z1 | z2);
return z3;
}conditional
首先考虑一比特的情形，不难发现输出结果可以用如下操作完成：
多个比特的情形类似，只要构造mask即可：
int conditional(int x, int y, int z) {
//声明变量
int flag, notflag, a, b, c;
//将x转换为0或1，x为0的时候转换为1，其余情形为0
flag = (!x);
//取反转换为1110,1111，x为0的时候转换为1110，其余情形为1111
flag = ~flag;
//加1转换为1111,0000，x为0的时候转换为1111，其余情形为0000
flag = flag + 1;
//取反
notflag = ~flag;
//生成结果
a = notflag & y;
b = flag & z;
c = (a | b);
return c;
}isLessOrEqual
首先判断符号位，如果符号位不同则可以直接产生结果；如果符号位相同，这时候做减法，注意此时必然不会溢出，所以减法有效，利用之前的negate方法即可完成这一步，最终将两种情形的结果合并即可：
int isLessOrEqual(int x, int y) {
int minusx, y_x, r, r0, r1, r2, mask, sx, sy;
//判断两数是否相同，相同为1，否则为0
r0 = !(x ^ y);
//模板，1000
mask = (1 << 31);
//符号位，如果为1则为0，否则为1
sx = !(x & mask);
sy = !(y & mask);
//判断符号位是否相同，如果相同返回1，否则返回0
r1 = !(sy ^ sx);
//计算-x
minusx = ~x;
minusx = minusx + 1;
//计算y-x，注意可能溢出
y_x = y + minusx;
//判断符号位是否为1，如果y >= x，则y_x为全0，否则为全1
y_x = y_x >> 31;
//生成结果
r2 = !y_x;
//如果r1=1，则返回r2；否则如果r0=1，则返回r0，其余情况返回sy
r = ((r1) & r2) | ((~r1) & (r0 | ((~r0) & sy)));
return r;
}logicalNeg
分两种情形讨论，如果$x<0$，则返回$0$；如果$x\ge 0$，则将其转换为$-x$，然后对$-x$使用之前的判断即可：
int logicalNeg(int x) {
int r1, r2, r, minusx;
//首先判断符号位，生成1000，0000
r1 = x & (1 << 31);
//右移，生成1111,0000
r1 = (r1 >> 31);
//生成1,0，如果x<0则r1=1，否则r1=0
r1 = r1 & 1;
//接着判断x>=0的情形，利用-x<=0
minusx = (~x) + 1;
//和之前一样判断符号位，如果x>0则r2=1，如果x=0则r2=0
r2 = minusx & (1 << 31);
r2 = (r2 >> 31);
r2 = r2 & 1;
//生成结果
r = r1 | r2;
r = r ^ 1;
return r;
}howManyBits
这题比较难，参考了网上的资料：https://www.cnblogs.com/ustca/p/11740382.html#12%E3%80%81howmanybits
首先考虑何时可以减少比特数，分两种情况讨论：
如果$x<0$，注意到有如下事实
假设
那么可以得到对应的$k+1$位表达
所以只需要$k+1$比特（注意需要额外的符号位）即可，最关键的一步是找到从左往右数第一个$0$的位置。
如果$x\ge 0$，显然只要忽略前导$0$即可，假设
那么同样可以得到对应的$k+1$位表达
所以仍然只需要$k+1$比特（注意需要额外的符号位）即可，最关键的一步是找到从左往右数第一个$0$的位置。
为了方便起见，对于负数$x$，我们考虑$\tilde x $，即对于负数
考虑
这一步可以由如下方式完成：
mask = (x & (1 << 31)) >> 31;
//负数则对其二进制取反，保证x为正数；如果s=1，那么mask=1111，x=~x;
x = ((~mask) & x) | (mask & (~x));所以后面的讨论中我们均考虑$x\ge0$的情形。
现在我们目标转换为找到$x$的二进制表达式中最靠左侧的$1$的位置$k$（假设下标从$1$开始），最终返回$k+1$即可，注意这里有操作数限制，所以应该使用二分查找。
首先考虑前16位，将$x$右移16位得到$x_1$，然后判断$x_1$的二进制表达式中是否含有$1$，得到$c_1$，如果$c_1=1$，那么我们需要考虑$x$的高16位，所以$x$应该右移$16$位，否则只要考虑$x$的低16位，不要需要右移即可，这一步可以由如下代码完成：
//判断前16位是否有1
c1 = !(!(x >> 16));
//如果c1=1则m1=16，否则为0
m1 = (c1 << 4);
x = x >> m1;其余部分同理，完整的代码如下：
int howManyBits(int x) {
int mask, m1, m2, m3, m4, m5, m6, c1, c2, c3, c4, c5, c6, res;
mask = (x & (1 << 31)) >> 31;
//负数则对其二进制取反，保证x为正数；如果s=1，那么mask=1111，x=~x;
x = ((~mask) & x) | (mask & (~x));
//利用二分查找找到第一个1的位置
res = 0;
//判断前16位是否有1
c1 = !(!(x >> 16));
//如果c1=1则m1=16，否则为0
m1 = (c1 << 4);
x = x >> m1;
//同理判断剩余部分
c2 = !(!(x >> 8));
m2 = (c2 << 3);
x = x >> m2;
c3 = !(!(x >> 4));
m3 = (c3 << 2);
x = x >> m3;
c4 = !(!(x >> 2));
m4 = (c4 << 1);
x = x >> m4;
c5 = !(!(x >> 1));
m5 = (c5 << 1);
x = x >> m5;
//最后一位特殊处理
c6 = x & 1;
m6 = c6;
//注意要增加1
res = m1 + m2 + m3 + m4 + m5 + m6 + 1;
return res;
}floatScale2
回顾浮点数的数值表示：
以及比特形式：
首先提取上述三个部分：
unsigned r;
int s, exp, frac, mask1, mask2, a;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);然后根据exp的值分情形判断。
情形1，exp全1，则根据要求输出uf：
if (exp == mask1){
//nan，无穷大
r = uf;
}情形2，exp全0，这种情况为非规格的浮点数，此时要对frac左移1位（乘2），然后判断frac最高位是否为1，如果为$1$，则将exp增加1,注意此时为转变为规格的情形，frac部分解释为1.xxxx2，所以frac部分无需处理，代码如下：
else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}然后判断frac最高位为1的情形相对复杂，需要看一个具体例子，以8位浮点数为例，假设浮点数为
注意此浮点数（非规格情形）为
按照上述代码生成的结果为
注意此时为规格情形，$M=1$，所以该浮点数的值为
情形3，exp不是全0也不是全1，这种情形比较简单，直接让exp加1即可：
else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}完整的代码如下：
unsigned floatScale2(unsigned uf) {
unsigned r;
int s, exp, frac, mask1, mask2, a;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);
if (exp == mask1){
//nan，无穷大
r = uf;
}else if (exp == 0){
//非规格
frac = frac << 1;
//计算第一位
a = frac >> 23;
if (a == 1){
exp = exp + 1;
}
r = (s << 31) | (exp << 23) | frac;
}else{
exp = exp + 1;
r = (s << 31) | (exp << 23) | frac;
}
return r;
}floatFloat2Int
第一步和上一题一样，提取s,exp,frac部分：
int r, s, exp, E, frac, mask1, mask2, ofr;
ofr = 0x80000000u;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);然后根据exp的值分情形判断。
情形1，exp全1，输出ofr：
if (exp == mask1){
//nan，无穷大
r = ofr;
}情形2，exp全0，这种情况的结果为$\pm 0.f_1f_2\ldots$，所以无论正负，均舍入到$0$：
else if (exp == 0){
//非规格
r = 0;
}情形3，exp不是全0也不是全1，首先计算$M\times 2^{23}$，注意这里要增加一个前置的1；然后计算实际的E，调整指数即可，这里要考虑溢出的情形；最后根据符号调整结果：
else{
//当前结果为M*2^23
//规格情形需要增加前置1
r = (1 << 23) | frac;
//实际结果为M*2^E
E = exp - 127;
if (E > 23){
while (E > 23){
E--;
r = r << 1;
if (r < 0){
r = ofr;
break;
}
}
}else{
while (E < 23){
E++;
r = r >> 1;
}
}
if (s == 1 && r != ofr){
r = -r;
}
}完整的代码如下：
int floatFloat2Int(unsigned uf) {
int r, s, exp, E, frac, mask1, mask2, ofr;
ofr = 0x80000000u;
//1111,1111
mask1 = 255;
mask2 = 0x7fffff;
//8位
exp = (uf >> 23) & mask1;
//23位
frac = uf & mask2;
//s
s = (uf >> 31);
//判断
if (exp == mask1){
//nan，无穷大
r = ofr;
}else if (exp == 0){
//非规格
r = 0;
}else{
//当前结果为M*2^23
//规格情形需要增加前置1
r = (1 << 23) | frac;
//实际结果为M*2^E
E = exp - 127;
if (E > 23){
while (E > 23){
E--;
r = r << 1;
if (r < 0){
r = ofr;
break;
}
}
}else{
while (E < 23){
E++;
r = r >> 1;
}
}
if (s == 1 && r != ofr){
r = -r;
}
}
return r;
}floatPower2
注意我们只要计算exp部分即可，其余部分全置为$0$，首先计算exp：
//计算exp
exp = x + 127;注意exp的范围为0到255，范围之外要特殊处理，完整的代码如下：
unsigned floatPower2(int x) {
int exp;
unsigned r;
//计算exp
exp = x + 127;
if (exp < 0){
r = 0;
}else if (exp > 255){
r = 0x7f800000;
}else{
r = exp << 23;
}
return r;
}