深入理解计算机系统CMU-15213 CSAPP（二）：DataLab

在国庆假期最后一天拾起一下一年前没做完的事情，尝试继续完成CSAPP的Lab，同时每个lab中都会结合原书补充一些细节知识。

实验目的

DataLab主要围绕数据表示设计，涉及到数据的按位运算和浮点数转化等知识，设计者希望我们修改bits.c文件中的函数，使得函数实现相应的目的。此外，每个函数会限制要用的运算符和数量，根据要求完成即可。当完成此节，你会对位运算刮目相看。尤其推荐通过其中的浮点数实验和本文描述了解浮点数存储细节，我相信这是没有之一的最详细和科学的描述。如有不当，欢迎指正。

具体实现

与和非实现异或

根据异或的卡诺图，可知：A^B = (A & ~B) | (~A & B)

而根据与或关系的转换：C | D = ~(~C & ~D)

所以有：A^B = ~(~(A & ~B) & \~(~A & B))

故有：

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

至此第一个函数完成了，通过以下指令检查正确性，编译警告可以忽略：

1
2
3

make 
./btest  #计算总分
# or ./btest -f bitXor  #单独验证bitXor函数是否正确

后续的函数验证方法同理。

返回最小的二进制整数补码

最小二进制整数补码对应表示范围最小值，int是32位的，表示范围为，因此答案就是，对应补码为1左移31位，即：

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

整数原码/反码/补码

原码最高位为符号位(0正1负)，其余位为对应二进制值，对于n位的原码，其表示范围是，例如四位的二进制码只能表示-7到7，例如：

-5	5	-0	+0
1101	0101	1000	0000

当看到1000时，在四位原码中表示的不是8，而是+0，对应的0000表示-0，所以0在原码中有了两种表示，这在运算中非常不便，其运算特点是：

正数间的加减法没问题，只要确保不overflow就好；
正数和负数或者负数与负数之间的运算，需要判断符号，异号相减，同号相加。
相反数相加错误，例如-5 + 5 = 1010，不等于正0或者负0；

因为符号决定了需要相减还是相加，换言之需要独立地设计加法和减法电路，导致设计规模过大，因此原码之后还引入了反码的概念，对于正数，原码等同于反码，对于负数，反码就是在原码基础上，符号位不变，数据位按位取反得到的编码，其表示范围同原码，如：

-5	5	-0	+0
1010	0101	1111	0000

通过引入反码，相反数相加等于-0。然而：其负数和正数相加结果作为相减结果仍然是错误的，例如5(0101) + (-3)(1100) = 0001(1)。

距离正确的结果就差1。

二进制编码中，原码和反码都不能很好进行算术运算，因此出现了补码编码方法。对于正数，补码等于反码等于原码，对于负数，补码就是反码结果加1：

-5	5	0	-8
1011	0101	0000	1000

而且：

补码的零没有正负之分，在四位编码中，用全0即0000表示，符号位为1其余全9如1000在原码表示负0，在补码中均表示为负最小值。
因为-0的转化，负数表示范围比原码多了1个，即。
整数之间加减法运算均可以通过二进制加法完成。
负数扩展位数只需要高位补1，例如四位二进制的-5表示为1011，八位对应为11111011，以此类推。
二进制-十进制转化计算简单，例如1011，等同于。
补码求相反数只要将其补码取反加1。如0101（5）取反加1为1011(-5)，同理1011（-5）取反加1为0101(5)。

正因为有了这些特性，补码成为二进制计算通用的编码。

补码相反数

正数和负数补码变成相反数都是逐位取反加一：注意区分逐位取反(~)和逻辑非(!)：逻辑非只会输出0和1，例如!0 = 1，!0x01 = 0：

1
2
3

int negate(int x) {
  return ~x+1;
}

逻辑门实现比较符

后面的实验之所以显得有点困难，是因为不能直接使用比较运算符，现在我们先实现等于、小于等于、大于等于作为辅助函数：

等于是较为简单的，使用异或取逻辑非即可：

1
2
3

int equal(int x, int y){
  return !(x^y);
}

对于小于等于，这也是题目之一，要实现x<=y，可以构造y-x >= 0，即保证y-x的结果符号位是正数(对应补码0)，但注意，因为y-x如果是两个异号的数，是有可能产生overflow结果的，因此我们先比较符号位，如果sx和sy异号，那么只要sx符号位为1即可，否则同号情况才计算y-x的符号位是否0(正数或0，因此y-x大于等于0)。

/* 
 * 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) {  // x <= y
  int sx = (x >> 31) & 0x01;
  int sy = (y >> 31) & 0x01;
  int sign = sx ^ sy;  //若sign=1，异号，要求sx必须为负数(符号位1)

  int diff = (((y + (~x + 1)) >> 31) & 0x01);
  return (sign & sx) | (!sign & ! diff);
}

大于等于逻辑类似，当然可以只用小于等于：

int isMoreOrEqual(int x, int y){  // x >= y
  int sx = (x >> 31) & 0x01;
  int sy = (y >> 31) & 0x01;
  int sign = sx^sy;
  
  int diff = (((x + (~y+1)) >> 31) & 0x01);
  return (sign & sy) | (!sign & !diff);
}

是否为指定ASCII码

比较运算符有了，直接用：

/* 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 isMoreOrEqual(x, 0x30) & isLessOrEqual(x, 0x39);
}

实现三目运算符

即实现 x != 0 ? y : z，关键是根据0和非0生成全1掩码和全0掩码：

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

结合三目运算符和比较运算符，基本可以完成剩下的逻辑，当然复用从来是偷懒的思想，一定存在更简单方法，下面仅作参考。

判断最大int补码

int类型数值的最大补码为0符号位加上31个1，直接判断即可：

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

判断是否奇数位都是1

还是判断相等：

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  return equal(x, (0xAAAAAAAA | x));
}

用逻辑非外的逻辑门实现逻辑非

实现逻辑非，即非0数都会输出0，0输出1：这里注意，这里的是int类型，符号位temp >> 31，不是0x000..001，而是0xFFF...FFF，因为int类型负数补码右移高位自动补1，而不是补0，所以sign取反再取最低一位：

//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 negX = ~x + 1;
  int temp = x | negX;
  int sign = temp >> 31;   // x=0, sign = 0x0000...0000；x!=0, sign = 0xFFFF...FFFF
  return (~sign) & 0x01;  
}

计算补码最少需要表示的位数

如10就足够表示-2，无需110，或者111110，同理01即可表示1，无需00001，可见对于正数，只需要找到最高位的1加上符号位计数即可，负数可以逐位取反按正数查找，遍历逻辑如下，for循环仅仅为了简化写法，对逻辑没影响，不算违规：

/* 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 = conditional(x>>31, ~x , x);
  //printf("%x\n", x);
  int res = 0;
  for(int i=0; i<=30; i++){
    int bit = (x & 0x01);  
    res = conditional(bit, i+1, res);  //存在1则更新计数
    x = x>>1;
  }
  return res + 1;
}

进一步的可以简化为二分法：直接检查高16位，如果含1直接看高16位的高八位，以此类推，效率更快：

int howManyBits(int x) {
  x = conditional(x>>31, ~x , x);
  int move = 16;
  int res = 0;
  while(move > 0){
    int bits = !!(x>>move);   //高move位含1
    x = conditional(bits, x>>move, x);
    res += conditional(bits, move, 0);  //若含1，则统计高位
    move /= 2;
  }
  return res + 1 + !!x;  //x可能只有一个1，需要再判断一次，故加!!x
}

至此基本逻辑题就完了，后面的浮点数是一题都不会，所以先refresh一下浮点数存储原理，以下。

浮点数存储原理

float的32位存储分成1位符号数、8位指数和23位的尾数，例如，当存储小数6.5时，整数部分整除取余、小数部分乘二取整，化成二进制表示为110.1，即，所以符号数、指数、尾数部分分别存入0、129以及101，其中129为指数2加上127的偏置(bias)。

偏置

这样的偏置是为了表示负指数，当然使用补码也可以表示负指数，但是补码以1开头表示负数，直观上是一个比正指数还大的指数，比较反直觉，因此IEEE还是采用了偏置法来存储指数，具体方法为：

对于float，用8位存储指数，因此其能够表示的指数个数是256个，其中剔除掉255(全1)用于表示无穷数，再剔除掉0(全0)代表0，剩下1 - 254，两侧减去127，所以归化到正负数范围恰好为-126 - 127(float指数有效范围)，因此为了避免出现负指数，所有指数存储前都会加上127。

这里另一个细节是：为什么IEEE不采用128偏置，即-127到126来表示指数范围，这看起来还是对称的，而且符合补码那种负数范围比正数大1的范围习惯，但是128偏置带来一个严重问题就是表示最小值的倒数范围落在最大值以外，即float的数值空间是不封闭的，两种方法的表示范围如下：

偏置127和128情况可见127偏置的最小值倒数是落在最大范围以内的，当然招致另一个疑惑是，127偏置的最大值倒数不是落在最小值范围以外吗，注意，float的指数存储虽然最小只可以取-126，但是其还有23个尾数，分别对应到$2^{-23}，所以其指数最小实际上对应了-149，因此使用127偏置的数值空间是封闭的。

而对于double也是同理，用了1位符号位、11位指数、52位尾数，因此表示的指数个数是2048个，同理剔除0和2047用于表示0和无穷，1 - 2046归化到-1022 - 1023(double指数有效范围)，因此double的偏置是1023。

化成十进制，float的表示范围约为，有效精度约在7位小数内()，double表示范围为，有效精度在15位小数内();

非规格数(subnormal number)、规格数(normal number)、特殊数(non number)

上述剔除的指数全零和全1的两种状态其实是两种特殊数，其中：

指数区全为1的为特殊数，只能用于表示无穷或者NAN，当超出上述表示范围，内存会将该指数记为无穷，而如果是那种非正常数值结果（包括虚数），例如对-1开平方，则记为NAN(Not A Number)，当然也有支持复数计算的库，不讨论。
指数区既非全0也为全1的为规格数，这部分的数也占整个范围的大部分，而且比起非规格数远离零点。
指数区全0的为非规格数，这部分的数用于表示0或者非常接近0的数。注意，非规格数人为地规定不能使用偏置计算，例如float指数区全0，按偏置计算应该指数对应了-127次方，因为-127加上偏置127才是存储全0，而实际上指数区全0，对应的是-126次方，所以flaot对应最小的非规格数是而不是。继续挖一个细节，既然八位指数存储全0和存储1都能表示指数-126，是否意味着两种表示的数重叠了？答案是否定的，唯一的区别是指数区全0时，解析的数不会隐含1，例如指数区全0，而尾数是1（即），此时表示的是，而如果指数区为1，表示的是。

求浮点数的双倍

分三种情况，如果是特殊数，无穷的双倍函数无穷，直接返回；如果是指数为0，只需要将尾数左移一位相当于乘2；其他情况，只需要将指数+1，即乘了2的1次幂，双倍，以下：

/* 
 * 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) {
  unsigned sign = (0x01 << 31) & uf;
  unsigned exp = 0xff & (uf >> 23); 
  unsigned frac = 0x007fffff & uf;
  
  if(exp == 255)  //无穷，还是无穷
    return uf;
  else if(exp == 0)  //指数为0，尾数直接左移乘2即可；
    return  sign | ((exp) << 23) | frac << 1;
  else{   //指数不为0，指数加1，即乘2即可
    return sign | (exp+1)<<23 | frac;
  }
}

float转换到int

方法注释给出，值得注意的是这里的int是实际数值，输入的unsigned是补码，所以看到数值计算，要左移实际的指数位factExp，乘上符号位这样的操作而不是直接拼接成补码：

/* 
 * 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) {
  unsigned sign = uf & (0x01<<31);
  unsigned exp = 0xff & (uf >> 23);
  unsigned frac = uf & 0x007fffff;
  
  int factExp = exp - 127; //实际指数
  if(exp == 255 || factExp > 31) //无穷数或者超出int指数范围
    return (0x01 << 31);
  else if(factExp < 0)   //指数小于0，即小于等于-1，最大整数不会超过1，直接对齐到0
    return 0;
  else{   //指数范围在0到31中，均是规格数
    int num = (0x01<<23) | frac;   //注意，规格数都隐含1，即1.frac × 2^{factExp}，尾数需要加上1(虽然btest测试没有cover这个)
    int value = (factExp-23 > 0) ? num<<(factExp-23) : num >> (23-factExp); //加上1是23位小数，需要右移23，如果fracExp不能抵消，就右移差值，否则左移
    value *= (!!sign==0) ? 1 : -1;
    return value;
  }
}

求次幂

注意，x允许实际允许范围是-149到127，与上题不同，这里返回的unsigned，所以规格数只需要加127左移23放到指数存储区即可，而非规格数是不隐含1的，只需要将对应的尾数置位1即可，如果你对这个答案不理解，说明没有完全明白上述浮点数存储的描述：

/* 
 * 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
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
  if(x > 127)   //超过127，无法表示
    return 0x7f800000;
  else if(x >= -126)  //-126-127，正常表示
    return (x+127) << 23;
  else if(x > -149)  //小于-126，指数全0非规格数为-126，尾数最小可以表示-23，故-149可表示
    return 1 << (x + 149);
  else{
    return 0;
  }
}

功能测试：

1 2	make ./btest

结果：

功能评估不会自动检查字符是否符合题目要求，但上述答案因为使用了函数调用、变量、循环等不能完全满足要求，但全过了一下这些都是可以内联展开的，对我而言可以接受，不通过也不优化了，结果：

1	./dlc bits.c

完整commit: 见finish DataLab。

Q&A

遇到floatPower2测试超时：

修改测试超时时间：./btest -f floatPower2 -T 20

参考链接：