CSAPP_DataLab

2023-11-24 15:29:34

Data Lab

//难度4

  • logicalNeg - implement the ! operator, using all of
  • the legal operators except !
  • Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
  • Legal ops: ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 4

//实现逻辑非，限制操作：~ & ^ | + << >>

//法一
int logicalNeg(int x) {
  int sign = 1<<31;
  int all1 = ~0;
  return ((((~x)|sign)+1)>>31)+1 & (x^sign)>>31 ; //((x^sign)>>31)
}

/*
思路：
实现逻辑非！，即实现0输出1，非0输出0。
首先要分割0和非0部分，办法是0将保持为0，非0全部转换为负数使其符号位为1。，
用 ~x 翻转，~0 = -1，非0保持不变 ；
(~x) | sign)，使-1不变，非0数全部转换为负数且最大值为-2，但注意到x=sign经运算后也为-1，用&(x^sign)>>31剔除，同时，使x=0时，第0位为1；
((~x) | sign)+1)，使-1变0，负数最大值此时为-1；
((~x) | sign)+1)>>31，0不变，负数全为-1；
((((~x) | sign)+1)>>31)+1，0变1，-1全变为0；
((((~x) | sign)+1)>>31)+1 & (x^sign)>>31，x=0时，（左边1 & 右边-1）输出1；x为非0数时，（左边0 & 右边任何数）输出0；
*/

法二：
int logicalNeg(int x) {
  return ((x|(~x+1))>>31)+1；
}

/*
思路：
利用补码（取反+1）的性质，0和Tmin的补码为本身，其它数值的补码为其相反数；
0与其补码按位或之后，其值为全0，Tmin与其补码、其它数值与其补码，按位或之后，符号位为1；
然后>>31，0不变，Tmin、其它数值为全1即-1；
而后+1，0变为1，Tmin、其它数值为0；
*/

  • 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

//求一个数最少要用多少位表示

//这道题想了很久，因为允许90个ops，就慢慢找规律，最终想出最高位和次最高位相异时，该数的位数可以确定，
//但实际只能从1位到32位一个个判断，总共操作接近300ops，只能翻起答案来= =，知道会用重复判断的方法，没想到是二分法这么巧妙

int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign = x>>31;
  x = (sign&~x)|(~sign&x);//x为正数不变；x为负数按位取反，其符号位变为0，可将负数当作正数来求其所需最少的表达位数

// 二分法，不断缩小范围
  b16 = !!(x>>16)<<4;//高十六位是否有1
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = !!(x>>8)<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = !!(x>>4)<<2;//剩余位高4位是否有1
  x = x>>b4;//如果有（至少需要16+8+4=28位），则右移4位
  b2 = !!(x>>2)<<1;//剩余位高2位是否有1
  x = x>>b2;//如果有（至少需要16+8+4+2=30位），则右移2位
  b1 = !!(x>>1);//剩余位高1位是否有1
  x = x>>b1;// 如果有（至少需要16+8+4+2+1=31位），则右移位
  b0 = x;//b0为x，数值为1或者0
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

/*
思路：
如果是一个正数，则需要找到它最高为1的是第几位（假设该位是第n位），再加上符号位0（计数为1），那么它最少需要n+1位来表示；
如果是一个负数，则需要找到它最高为0的是第几位（假设该位是第m位），那么它最少需要m位来表示
*/

//float

//一开始是真的懵，想来是浮点数位级表示学得比较模糊

  • floatScale2 - Return bit-level equivalent of expression 2*f for
  • floating point argument f.
  • Both the argument and result are passed as unsigned int's, but
  • they are to be interpreted as the bit-level representation of
  • single-precision floating point values.
  • When argument is NaN, return argument
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4

//用无符号整型的位级来表示一个浮点数，同时，对浮点数乘2

  unsigned floatScale2(unsigned uf) {
  int exp = (uf&0x7f800000)>>23;//取指数exp
  int sign = uf&0x80000000;//取符号位sign
  if(exp==0) return uf<<1|sign;//输出（非规化数）*2或者0*2
  if(exp==255) return uf;//输出NaN或者INF(无穷，包括正无穷和负无穷）
  exp++; //计算（规化数）*2，
  if(exp==255) return 0x7f800000|sign;//（规化数）*2后，若指数exp全为1即INF，则输出0x7f800000|sign
  return (exp<<23)|(uf&0x807fffff);//（规化数）*2后，若指数exp不全为1就仍为规划数，则输出(exp<<23)|(uf&0x807fffff)
}

注意：
//第5行，不用exp<<1的原因是：虽然能达到*2的目的，但可能会使exp越出255，突破exp限定的8位

/*

  • floatFloat2Int - Return bit-level equivalent of expression (int) f
  • for floating point argument f.
  • Argument is passed as unsigned int, but
  • it is to be interpreted as the bit-level representation of a
  • single-precision floating point value.
  • Anything out of range (including NaN and infinity) should return
  • 0x80000000u.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4
    */
    int floatFloat2Int(unsigned uf)
    {
    int sign = (uf >> 31) & 1;//取符号位sign
    int bias = 127;//偏置值为(2(8-1)) - 1
    int exp = (uf >> 23) & 0xFF;//取指数exp
    int E = exp - bias; //指数exp的真实值,即阶码E
    int frac = uf & 0x007FFFFF;//取小数字段frac，注意符号位被剔除了
    int M = frac | 0x00800000; //将第23位置1，即阶码的最后1位置1，因为：规化数之中尾数M的范围是（1 ~ 2-ξ），必大于等于1
    int tar;
    if (sign) sign = -1;
    else sign = 1;//符合位取(-1)    0=1 或者 (-1)**1=-1 ，用以保持正数，或者转为负数
    if (E >= 31)
    return 0x80000000;
    if (E < 0)
    return 0;
    if (E >= 23)
    tar = sign * (M << (E - 23));//E大于23时，则M左移(E - 23)，同时考虑正负数
    else if (E < 23)
    tar = sign * (M >> (23 - E));//E小于23时，则M右移(23 - E)，同时考虑正负数
    return tar;
    }

//区分float型的规化数、非规化数、INF、NaN，
//INF、NaN：其E >= 31 计算阶码值2E，超出int型Tmax == 0x7fffffff，直接输出0x80000000
//非规化数：其E < 0 计算阶码值2E，为小数，直接输出0
//规化数： 其31> E >=0 计算阶码值2E，居于1~230之间，需要左右移
//左右移原理见 CSAPP P82
//其结论是：阶码E大于尾数位数（float型是23位）时，则M左移(23 - E)（最多移8位）；
// 阶码E小于尾数位数，则M右移(23 - E)（最多移23位）

//原解法对于E=23时，直接输出tar=0；对于E=31时，将其看作仍可以作M左移运算，事实上2E = 231,已经超过int型Tmax == 0x7fffffff
//但检测可以通过

//笔者做出修正
//对于E=23时，输出tar = sign*M；对于E=31时，直接输出0x80000000（本题Anything out of range return 0x80000000）

/*

  • floatPower2 - Return bit-level equivalent of the expression 2.0^x
  • (2.0 raised to the power x) for any 32-bit integer x.
  • The unsigned value that is returned should have the identical bit
  • representation as the single-precision floating-point number 2.0^x.
  • If the result is too small to be represented as a denorm, return
    1. If too large, return +INF.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
  • Max ops: 30
  • Rating: 4
    */
    unsigned floatPower2(int x) {
    unsigned INF = 0xff << 23;
    int exp = x + 127;
    if(exp >= 255) return INF;
    if(exp < -23) return 0;
    if(exp <= 0) return 0x00400000>>(~exp+1);
    return exp << 23;
    }

未完续待。。。

上一篇：习题5-1 符号函数 (10 分) 本题要求实现符号函数sign(x)。


下一篇：JQuery Tables 的应用（三）