乐趣区

关于c:深入理解计算机系统实验一-Data-Lab

jiezi

本文是 CSAPP 第二章的配套试验，通过应用无限的运算符来实现负数，正数，浮点数的位级示意。通过实现这 13 个函数，能够使咱们更好的了解计算机中数据的编码方式。

筹备工作

  首先去官网 Lab Assignments 取得试验相干的文件（也能够加我 QQ 获取教学视频、PPT 等内容）在每个试验文件的 README 中都具体介绍了如何批改程序，编译程序等。倡议仔细阅读，有不明确的能够留言，看到后会及时回复。

  我的编译环境：Ubuntu 16.04，gcc 5.4.0。

  编译时会报如下谬误。

<img src=”https://gitee.com/dongxingbo/Picture/raw/master//%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F/datalab_%E6%8A%A5%E9%94%991.png” alt=”image-20201026150615228″ />

  执行以下命令，装置 64 位包。

sudo apt-get purge libc6-dev
sudo apt-get install libc6-dev
sudo apt-get install libc6-dev-i386

  再次编译，没有报错，失常。

题目

bitXor

思路

  德摩根律，也叫反演。

代码

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {return ~(x & y) & ~(~x & ~y);
}

tmin

思路

  补码的最小值 0x80000000

代码

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {return 1<<31;}

isTmax

思路

  判断是否是补码的最大值。32 位补码的最大值为 0x7fffffff，与其异或，

代码

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 2
 */
int isTmax(int x) {return !(x^0x7fffffff);
}

allOddBits

思路

  这个题目还是比较简单的，采纳掩码形式解决。首先要结构掩码，应用移位运算符结构出奇数位全 1 的数 mask，而后获取输出 x 值的奇数位，其余位清零（mask&x），而后与 mask 进行异或操作，若雷同则最终后果为 0，而后返回其值的逻辑非。

代码

/* 办法一
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {int mask = 0xAA+(0xAA<<8);
  mask=mask+(mask<<16);
  return !((mask&x)^mask);
}
/* 办法二
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {return !(~x&0xaaaaaaaa);
}

negate

思路

  补码实际上是一个阿贝尔群, 对于 x，- x 是其补码，所以 - x 能够通过对 x 取反加 1 失去

代码

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

isAsciiDigit

思路

  x 别离与 ’0’ 和‘9’作差，而后依据作差的后果判断符号位的为 0 还是 1 即可

代码

/*

 * isAsciiDigit -return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')

 *   Example: isAsciiDigit(0x35) = 1.

 *            isAsciiDigit(0x3a) = 0.

 *            isAsciiDigit(0x05) = 0.

 *   Legal ops: ! ~ & ^ | + << >>

 *   Max ops: 15

 *   Rating: 3

 */

int isAsciiDigit(int x) {return(!((x+~48+1)>>31))&!!((x+~58+1)>>31);

}

conditional

思路

  把 x 转换为全 0 或者全 1。这里留神下，0 的补码是 0，位示意全 0。1 的补码是 -1，位示意全 1。当 x 转为全 0 和全 1 时，再 (x&y) 或者 (~x&z) 时，肯定有一个成立。返回的就是 y 或者 z 的值

代码

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(3,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  x = !!x;
  x = ~x+1;// 求补码
  return (x&y)|(~x&z);
}

isLessOrEqual

思路

  通过位运算实现比拟两个数的大小，无非两种状况：一是符号不同负数为大，二是符号雷同看差值符号。

代码

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  int negX=~x+1;//-x
  int addX=negX+y;//y-x
  int checkSign = addX>>31&1; //y- x 的符号
  int leftBit = 1<<31;// 最大位为 1 的 32 位有符号数
  int xLeft = x&leftBit;// x 的符号
  int yLeft = y&leftBit;// y 的符号
  int bitXor = xLeft ^ yLeft;// x 和 y 符号雷同标记位，雷同为 0 不同为 1
  bitXor = (bitXor>>31)&1;// 符号雷同标记位格式化为 0 或 1
  return ((!bitXor)&(!checkSign))|(bitXor&(xLeft>>31));// 返回 1 有两种状况：符号雷同标记位为 0（雷同）位与 y-x 的符号为 0（y-x>=0）后果为 1；符号雷同标记位为 1（不同）位与 x 的符号位为 1（x<0）}

logicalNeg

思路

  逻辑非就是非 0 为 1，非非 0 为 0。利用其补码（取反加一）的性质，除了 0 和最小数 ( 符号位为 1，其余为 0 )，外其余数都是互为相反数关系（符号位取位或为 1）。0 和最小数的补码是自身，不过 0 的符号位与其补码符号位位或为 0，最小数的为 1。利用这一点失去解决办法。

代码

/* 
 * 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) {return ((x|(~x+1))>>31)+1;
}

howManyBits

思路

  负数的补码：负数最高位的 1 为第 n 个数，再加上符号位，后果为 n +1。

  正数的补码：转换为负数，同上。

/* 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) {
  int b16,b8,b4,b2,b1,b0;
  int mask = x >> 31;
  x = (mask & ~x) | (~mask & x); // 如果为负数，放弃不变；如果为正数，按位取反

  //step1: 判断高 16 为是否有 1
  b16 = !!(x >> 16) << 4; // 如果高 16 为有 1, 则 b16 = 16，否则为 0
  x >>= b16; // 如果高 16 为有 1,x 右移 16 位舍弃低 16 位, 在新的低 16 位持续查找；否则放弃不变
  //step2: 判断高 8 位是否有 1
  b8 = !!(x >> 8) << 3;
  x >>= b8;
  //step3: 高 4 位
  b4 = !!(x >> 4) << 2;
  x >>= b4;
  //step4: 高 2 位
  b2 = !!(x >> 2) << 1;
  x >>= b2;
  //step5: 高 1 位
  b1 = !!(x >> 1);
  x >>= b1;
  //step6: 低 1 位
  b0 = x;

  return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

floatScale2

思路

  参考上图了解下。不了解的回去看下 IEEE 规范浮点数格局《深刻了解计算机系统》（CSAPP）读书笔记 —— 第二章 信息的示意和解决

  次要依据输出的数值，能够分为三种状况：

  1. 输出 uf 为无穷大和 NaN，间接返回 uf

  2.uf 为 0 或无穷小，返回 2 * uf + sign

  3. 若 exp+1 == 255，返回无穷大，否则 返回 exp+1。（exp 为浮点数编码的整数局部，exp+ 1 相当于 uf * 2。）

代码

/* 
 * 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
 */
unsigned floatScale2(unsigned uf) {int exp = (uf&0x7f800000)>>23;// 取出 exp 局部
  int sign = uf&(1<<31);// 取出符号位
  if(exp==0) return uf<<1|sign;// 状况 2
  if(exp==255) return uf;// 状况 1
  exp++;
  if(exp==255) return 0x7f800000|sign;// 状况 3
  return (exp<<23)|(uf&0x807fffff);
}

floatFloat2Int

思路

  1. 非规格化，示意十分靠近 0 的数，转换为 int 值后为 0

  2. 规格化，数的散布从靠近 0 到无穷越来越稠密，当 f 不超过 int 型示意的范畴时，转换为 int；当超过 int 型示意的范畴时返回 0x80000000u

  3. 非凡，返回 0x8000000u

  在规格化的 float 转换为 int 型整数时，

  如果 E >= 31，小数点右移 31 位，此时隐含的 1 和 frac 占 32 位，另外还须要一个符号位，超出了 int 型范畴

  如果 E < 0，小数点左移 1 位后为 0.1frac，转换为 int 后为 0

  如果 0 < E < 23, 小数点左移 E 为后须要舍弃 frac 中局部位，此时间接将 frac 右移 23- E 位，抹去小数局部

  如果 23 <= E < 31，此时小数点右移后 frac 全副移到小数点以左，将 frac 左移 E -23 位，在前面补零

代码

/* 
 * 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;
  int exp = (uf >> 23) & 0xff;
  int frac = uf & 0x7fffff;

  int E = exp - 127;

  if (E < 0) // 小数
  {return 0;}
  else if (E >= 31) // 超出 int 范畴
  {return 0x80000000u;}
  else
  {frac = frac | (1 << 23);  // 加上隐含的 1

    if (E < 23)     // 舍去局部小数
    {frac >>= (23 - E);
    }
    else        // 不须要舍去小数
    {frac <<= (E - 23);
    }

    if (sign)
      return -frac;
    else
      return frac;
  }
}

floatPower2

思路

依据浮点数求值公式：$V = {(– 1)^s} \times M \times {2^E}$

1. 规格化

令 M =1(frac = 0)，xEexp-Bias，exp=x+Bias

2. 非规格化

exp = 0，在 frac 中令某一位为 1，从而可使 x 更小。

exp frac M maxE MinE
非规格化 0 0 10 0.frac -127 -148
规格化 非 0 0 1.0 127 -126

对边界状况剖析

1. 非规格化

  • 当 frac = 100 0000 0000 0000 0000 0000 时，M = 0.1b = 0.5, E = 1- Bias = -126，此时 v = 0.5 * 2.0 ^ -126 = 2.0 ^ -127
  • 当 frac = 000 0000 0000 0000 0000 0001 时，M = 0.000 0000 0000 0000 0000 0001 = 2.0 ^ -22, E = -126，此时 v = 2.0 ^ -22 * 2 ^ -126 = 2.0 ^ -148

2. 规格化

  • exp = 0xFF 时，E = exp – Bias = 127
  • exp = 1 时，E = exp – Bias = -126

代码

unsigned floatPower2(int x) {if (x > 127) //too large, return +INF
  {return (0xFF << 23);
  }
  else if (x < -148) //too small, return 0
  {return 0;}
  else if (x >= -126) //norm，计算 exp
  {
    int exp = x + 127;
    return (exp << 23);
  }
  else //denorm，令 frac 中某一位为 1
  {
    int t = 148 + x;
    return (1 << t);
  }
}

测试后果

总结

  前面的几个题目还是很烧脑的，拿到题目手足无措，次要起因还是概念了解不到位。起初又去看书，了解了下基本概念，看了下其他人的解法，题目也能够缓缓理分明了。解题过程代码也记录了下来，过段时间回来二刷可能会有新的解法。前面还有还几个试验等着我，慢慢来。欢送关注我的博客及时获取更新告诉。

  最初分享个 PPT 上看到的笑话，数绵羊~ 哈哈 ~

  养成习惯，先赞后看！如果感觉写的不错，欢送关注，点赞，珍藏，谢谢！

** 如遇到排版错乱的问题，能够通过以下链接拜访我的 CSDN。

CSDN:CSDN 搜寻“嵌入式与 Linux 那些事”

欢送欢送关注我的公众号：嵌入式与 Linux 那些事，支付秋招口试面试大礼包（华为小米等大厂面经，嵌入式知识点总结，口试题目，简历模版等）和 2000G 学习材料。**

退出移动版