CSAPP之Data

[TOC]

1.bitXor

根据书上练习题上的^操作

xor(a,b) =~a&b | a&~b 

以及德摩根定律

$$
¬(P∨Q)⟺
(
¬
P
)
∧
(
¬
Q
)
$$

xor(a,b)= ~a&b|a&~b = ~(~(~a&b|a&~b)) = ~(~(~a&b)&~(a&~b))

所以

int bitXor(int x, int y) {
  return ~(~(~x&y)&~(x&~y));
}

2.tmin

返回补码最小值，且题目环境为32位

计算0x80000000

int tmin(void) {
  //-214783648
  //-2^(32-1)
  return 1 << 31;
}

3.isTmax

判断是否为补码最大值，是返回1，不是返回0

0111 1111 1111 1111 1111 1111 1111 1111 # 二进制
7    f    f    f    f    f    f    f    # 十六进制

tmin + tmax + 1 = 0;
由题意
x = 011111111
x+1 = 100000000
~(x+1) = 0111111111
x ^ ~(x+1) == 0 ? 1 : 0;

排除特例x = 11111111111...
x + 1 = 000000000...
~(x+1) = 11111111111...
利用 !!~x == 0 

int isTmax(int x) {
    //2^31-1
   return (!(x ^ ~(x+1))) & (!!~x);
}

4.allOddBits

4位 -> 1010 -> 0xA
(num & 0xA) ^ 0xA !=0 -> num不等于0xA
构造32位的mask
AA = A | (A << 4);
AAAA = AA | (AA << 8);
mask = AAAA | (AAAA << 16);

wp如下

int allOddBits(int x) {
    int A = 0xA;
    int AA = A | (A << 4); //8位
    int AAAA = AA | (AA << 8); //16位
    int mask = AAAA | (AAAA << 16); //32位
    return !((x & mask) ^ mask);
}

5.negate

正数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

/* negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
    return ~x + 1;
}

6.isAsciiDigit

0x30 -> 110000
0x39 -> 111001

判断
//(x - 0x30 >= 0) && (0x39 - x >= 0)
利用上面的取反操作，+变-运算
利用mask = 1 << 31; // 0x80000000
mask和上面的表达式做&运算，取符号位判断正负，

int isAsciiDigit(int x) {
  //(x - 0x30 >= 0) && (0x39 - x >= 0)
  int mask = 1 << 31;
  return !((x+(~0x30 + 1)) & mask) & !((0x39 + (~x + 1)) & mask);
}

7.conditional

首先将x的bool值转换掩码，为全0或者全1

int mask = ~!!x + 1;

若x为非0，mask为-1，位为全1，mask&y返回y，~mask&z返回0

int conditional(int x, int y, int z) {
    int mask = !!x;
    mask = ~mask + 1;
    return (mask & y) | (~mask & z);
}

8.isLessOrEqual

分情况讨论
1.x == y
int cond1 = !(x^y);
2.符号相反
先取出符号位判断
int signX = x >> 31 & 1;
int signY = y >> 31 & 1;
fir. x- y+
int cond2 = signX & (!signY);//1
sec. x+ y-
int cond3 = (!signX) & signY;//1
3.符号相同
int mask = 1 << 31;
int cond4 = ((x + (~y+1)) & mask);//1

这个感觉有点啰嗦了。。但是可以理解一下

这个题改了半天，个人感觉下面的做法更好理解一点。。

int isLessOrEqual(int x, int y) {
    //求个差值
    int sub = y + (~x + 1);
    //求个差符号位,负数为1
    int mask = 1 << 31;//0x80000000
    int flag = (sub & mask) >> 31;
    //求两数的符号位
    int signX = (x >> 31);
    int signY = (y >> 31);
    //符号相同返回0，符号不同返回1
    int cmp = ((signY ^ signX) >> 31) & 1;
    //1.若符号相同,则符号位应该为0
    //2.若符号不同，signX应为1
    return (!cmp & !flag) | (cmp & signX);
}

9.logicalNeg

*	logicalNeg - implement the ! operator, using all of the legal operators except !
*   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1

我们可以将题意理解为

if(x!=0)
return 0;
else
return 1;

于是我们就该想怎么判断x!=0;

try：
int a = 0101;
int -a = 1011;
int sign = 1

wp如下

int logicalNeg(int x) {
     int negX = ~x + 1;
     int sign = (negX | x) >> 31;
     return sign + 1;
}

10.howMantBits

这一题怎么说。。题目没看懂，前前后后也花了好久理解题意和wp，

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  	//通过这两步，若x为0就返回1位，是正数就保留，是负数就按位取反，这样同时去掉了符号位1，找到首位0
    int flag = x >> 31;
    x = (flag & (~x)) | ((~flag) & x);

    int b16, b8, b4, b2 ,b1, b0;

    b16 = (!!(x >> 16)) << 4;//16
    x >>= b16;

    b8 = (!!(x >> 8)) << 3;//8
    x >>= b8;

    b4 = (!!(x >> 4)) << 2;//4
    x >>= b4;

    b2 = (!!(x >> 2)) << 1;//2
    x >>= b2;

    b1 = (!!(x >> 1));
    x >>= b1;
    
    b0 = x;

    int result = b0 + b1 + b2 + b4 + b8 + b16 + 1;
    return result;
}

下面就是一种寻找高位的二分法，最后再加上符号位一个1。

https://binac.io/posts/csapp-data-lab/#fn:3

11.floatScale2

unsigned floatScale2(unsigned uf) {
      //exp, sign, frac
      unsigned sign = (uf >> 31) & 1;
      unsigned exp = (uf >> 23) & 0xFF;//0xF=1111 表示4位
      unsigned frac = uf & 0x7FFFFF;

      //0
      if(exp == 0 && frac == 0)
      {
        return uf;
      }

      //infinity or NaN
      if(exp == 0xFF)
      {
        return uf;
      }

      //denormalize
      if(exp == 0)
      {
        //E = exp -127;
        frac <<= 1;
        return (sign << 31) | frac;
      }

      //normalize
      exp++;
      //E = exp -127;
      return (sign << 31) | (exp << 23) | frac;
}

这题看看书的IEEE浮点数表示，在进行分类讨论

12.floatFloat2Int

这个就直接写注释里了

int floatFloat2Int(unsigned uf) {
    //exp, sign, frac
    unsigned sign = (uf >> 31) & 1;
    unsigned exp = (uf >> 23) & 0xFF;//0xF=1111 表示4位
    unsigned frac = uf & 0x7FFFFF;

    //0
    if(exp == 0 && frac == 0)
    {
      return 0;
    }

    //infinity or NaN
    if(exp == 0xFF)
    {  
      return 0x80000000; 
    }

    //denormalize
    if(exp == 0)
    {
      //M 0.11111(2) 很小
      //E = 1 - 127 = -126(原书上的，当为非规格化，E = 1 - Bias);
      return 0;
    }

    //normalize
    int E = exp - 127;
    frac = frac | (1 << 23);
    //1<= M < 2;

    if(E > 31) //1.xxxxx
    {
      return 0x80000000; 
    } else if(E < 0)
    {
      return 0;
    }

    if(E >= 23)
    {
      frac <<= (E - 23);
    }else
    {
      frac >>= (23 - E);
    }

    if(sign)
    {
      return ~frac + 1;
    }
    else
    {
      return frac;
    }
    

}

13.floatPower2

unsigned floatPower2(int x) {
    if(x < -149)
    {
      return 0;
    }else if(x < -126)
    {
      int shift = 23 + (x + 126);
      return 1 << shift;
    }else if(x <= 127)
    {
      int exp = x + 127;
      return exp << 23;
    }else if(x > 127)
    {
      return 0xFF << 23;
    }   
}
要把time_out改为20。。。

总结：

太菜了，有的题目看不懂，也不会做。怎么说，只能慢慢学，有空多复习，温故而知新。