本文是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-devsudo apt-get install libc6-devsudo 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更小。

expfracMmaxEMinE
非规格化00 100.frac-127-148
规格化非001.0127-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学习材料。**