课程主页：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;
}