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

6次阅读

共计 6749 个字符，预计需要花费 17 分钟才能阅读完成。

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

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

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

编译时会报如下谬误。

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

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

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

德摩根律，也叫反演。

/* 
 * 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);
}

补码的最小值 0x80000000

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

判断是否是补码的最大值。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);
}

这个题目还是比较简单的，采纳掩码形式解决。首先要结构掩码，应用移位运算符结构出奇数位全 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);
}

补码实际上是一个阿贝尔群, 对于 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;}

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);

}

把 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 - 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）}

逻辑非就是非 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;
}

负数的补码：负数最高位的 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;
}

参考上图了解下。不了解的回去看下 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);
}

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;
  }
}

依据浮点数求值公式：$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 学习材料。**

正文完

c

发表至： c#

2020-12-06

0

关于c:CS139-C-项目

关于c:LeetCode刷题学习704二分查找

关于c++:SkeyePlayer-RTSP-Windows播放器抓图代码重构

关于c#:基于C和MYSQL数据库实现的课程自动考试系统

关于javascript:ArrayLike-Objects-详解

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

筹备工作

题目

bitXor

思路

代码

tmin

思路

代码

isTmax

思路

代码

allOddBits

思路

代码

negate

思路

代码

isAsciiDigit

思路

代码

conditional

思路

代码

isLessOrEqual

思路

代码

logicalNeg

思路

代码

howManyBits

思路

floatScale2

思路

代码

floatFloat2Int

思路

代码

floatPower2

思路

代码

测试后果

总结

站内搜索