这个学期开始啃CSAPP–这本计算机名著了,打算来补一波基础。这本书从表层到底层概述了计算机系统的方方面面,读着相当舒服,让人放不下来。而这本书最吸引人的就是官方配套的9个lab,CMU的学生们说这本书有趣,令人兴奋,主要就是因为这些lab练习,它们不仅有趣,而且也有完好的评分机制和严格的检查,能让读者对自己的阅读进行一个自我检测。写这一系列博客一方面是为了整理自己做lab中遇到的问题和习题解答,另一方面也是每周督促自己进一步阅读,早日战胜这整本书。
Data lab是本书中的第一个lab,内容对应书本第二章,涉及到整数补码和单精度浮点数的位表示。通过在很严格的要求下用位运算完成15个函数,来熟悉理解和掌握相关的数据表示和转换的方法。

整个CSAPP所有的实验的自学讲义和实验材料我已经放在了我的github上面,你可以在这里找到:CS-APP3e-labs

Data Lab 简介

Github地址:Data Lab

这个lab主要在数的位级表示上做文章,通过在很严格的限制下(如,限定操作符的使用数量和种类,禁止调用函数,宏定义等等)利用&, |, ^等等位运算操作符,来实现各种各样与数有关的功能,来让学生熟悉整数和浮点数的位级表示和处理。

说实话,这个lab做起来还是十分有趣的,这些严格限制的函数就像一个个谜题,通过你巧妙的方式,规避溢出等问题,去实现各种基本功能。不过,在整个实验的过程中,还是很有些烧脑的,有些题目还是很有点难度,这次大概整了两天半,卡了一道题(bitCount),最终还是查了下答案。

文件组成和检测机制

  • bits.c:我们需要写的文件,十五个函数和任务要求在这里面
  • Makefile:编译整个lab工程的Makefile
  • btest:对写好的函数进行完全的测试
  • dlc:检测写好的程序是否符合额外的要求,是否有语法错误,参数为一个文件
  • ishow:给出整数的十六进制,有符号和无符号类型的值
  • fshow:给出单精度浮点数的十六进制表示,符号位,阶码,尾数的值

每次写好新的函数后,我们通过make命令编译文件,通过运行btest来检测我们函数的正确性,通过运行dlc bits.c来检测我们的函数是否满足额外的要求。最后两个算是官方给我们的辅助工具。

Data Lab 实验环境

首先实验环境是已经定好了的:

  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.
  1. 使用整数的二进制补码,32位的整数
  2. >> 为算术右移
  3. 将整数移动超过自身size的时候结果不可预测

目前来说现在的计算机都能满足这些要求,唯一需要注意的是,有些同学可能会在编译时遇到无法编译的问题,查看Makefile文件后发现编译的命令里面有一个-m32的参数,而如果你的gcc编译器是64位的,就会出现错误。(笔者就是这样)解决的方法为安装32位的gcc,以下是在笔者的Archlinux-64位的系统上的解决方法:

  1. 编辑 /etc/pacman.conf,去掉如下一行的注释
[multilib]
Include = /etc/pacman.d/mirrorlist
  1. 安装gcc-multilib
sudo pacman -S gcc-multilib

注意这里可能会与已经存在的gcc发生冲突,需要删掉已有的gcc。

注意:在最新版的Arch系统中,gcc-multilib已经和gcc已经合并为一个包,你只需要安装lib32-gcc-libs即可

第一部分:整数题目

首先看格式要求,原文如下:

INTEGER CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to thent, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.

 following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

一共两种语句,声明和赋值,同类型的语句放在一起

接下来是额外的限制要求:


Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
    
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.

翻译一下:

每一个表达式需要符合以下的要求:

  1. 整数常量只能在 0 ~ 255(0xff)之间
  2. 是函数的参数或者local变量
  3. 使用操作符 ! ~ & ^ | + « »

禁止使用:

  1. 使用任何流程控制语句,如if, do, while, for, switch等
  2. 使用宏定义
  3. 自行定义额外的函数
  4. 调用函数
  5. 使用其他的操作符,如&& || - ?:等
  6. 使用强制转换
  7. 使用除了int以外的其它数据类型,如数组,结构体,联合等

看起来还是十分严格的,四则运算只有加号,不过我们可以用 ~x + 1来表示 -x

接下来我就开始逐一讲解个个函数。

bitAnd

  • 功能要求:实现 x & y
  • 操作符限制:~ |
  • 最大操作符数量:8
  • 分值:1

第一题送分,考察逻辑里的德摩根法则,对表达式(x & y)前面取两个按位反,然后把一个拿进去,就是~(~x | ~y)

int bitAnd(int x, int y) {
  return ~(~x | ~y);
}

getByte

  • 功能要求:获得x的第n个字节
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:6
  • 分值:2

第二题也是送分,思路略。

int getByte(int x, int n) {
  return (x >> (n << 3)) & 0xFF;
}

logicalShift

  • 功能要求:实现逻辑右移
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:20
  • 分值:3

这一题要求实现逻辑右移,思路是设计一个掩码,用来将x右移n位之后,左边补上的位置为0。

int logicalShift(int x, int n) {
  int mask = (~(~0 << n) << 31) >> n;
  return (x >> n) & ~(mask << 1);
}

bitCount

  • 功能要求:统计x的位级表示中有多少个1
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:40
  • 分值:4

这一题就有难度了,自己就卡在这里,最终在一篇讲位运算的博客里找到了一个类似的问题,仿照写出了本题的答案。

咱们用8位时候的一个简单的例子来入手,考虑这三个掩码:0x55, 0x33, 0x0f

任取一个8位整数,例如 x = 01101011, 我们将它每两位看做一组,接下来做位运算 x & 0x55, 这样就记下了 1, 3, 5, 7位的1, 然后是 (x >> 1) & 0x55,这样就记下了 2, 4, 6, 8位的1。

所以我们只需要 x = x & 0x55 + (x >> 1) & 0x55,现在第 1-2, 3-4, 5-6, 7-8位上的数就表明这两位中1的个数。

类似的,接下来把每四位看做一组,利用掩码 0x33重复操作可以得到 1-4, 7-8位上的数分别表明这四位中1的个数。

最后利用掩码 0x0f,就搞定了整个8位中1的个数。

对于32位的本题,掩码可以设计为:0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0x0000ffff

由于题目还有操作符限制,所以在构造掩码时要想着如何减少操作符。

int bitCount(int x) {
  int mask1 = 0x55 + (0x55 << 8);
  int mask2 = 0x33 + (0x33 << 8);
  int mask3 = 0x0f + (0x0f << 8);
  int mask4 = 0xff + (0xff << 16);
  int mask5 = 0xff + (0xff << 8);
  mask1 += mask1 << 16;
  mask2 += mask2 << 16;
  mask3 += mask3 << 16;  
  x = (x & mask1) + ((x >> 1) & mask1);
  x = (x & mask2) + ((x >> 2) & mask2);
  x = (x & mask3) + ((x >> 4) & mask3);
  x = (x & mask4) + ((x >> 8) & mask4);
  x = (x & mask5) + ((x >> 16) & mask5);
  return x;
}

bang

  • 功能要求:用位运算实现 !
  • 操作符限制:~ & ^ | + « »
  • 最大操作符数量:12
  • 分值:4

这一题我开始也是卡了好久才想到突破口。!操作符判断是否是0,那么自然应该去从0与众不同的性质上去着手,开始我从移位上去考虑了几种方法,结果发现都处理不好溢出的问题。然而0有一个很简单的特性:-0 = 0,即符号位不变,仍然是0,但除此以外的任何数,取相反数都是一正一负,他们的符号位总有一个是1,于是我们从符号位入手,去解决此题。

int bang(int x) {
  int y = x | (~x + 1);
  return ((y >> 31) & 0x01) ^ 0x01;
}

tmin

  • 功能要求:返回最小的补码数
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:4
  • 分值:4

突然乱入的送分题,不就是构造0x80000000嘛。

int tmin(void) {
  return 1 << 31;
}

fitsBits

  • 功能要求:判断x是否可以用n位补码表示,是返回1,否则返回0
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:15
  • 分值:2

这个题也很简单,先左移 32 - n 位,再右移 32 - n位,若仍然和原数相等,就表明没有溢出,也就是可以被表示了。

int fitsBits(int x, int n) {
  int left = 33 + ~n;
  return !((x << left >> left) ^ x);
}

divpwr2

  • 功能要求:计算x/(2^n)向0取整的值
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:15
  • 分值:2

这到题目在CS:APP第二章内有详细的取整原理说明,正数直接可以右移n位,负数需要加上偏移量 2^n - 1。那么问题的关键在于如何不使用判断语句实现两种情况。

考虑到正数和负数的符号位不同,他们右移31位之后得到的分别是全0和全1的数,我们拿它或上任何一个数a得到b,就可以实现x为正数时,b = 0,x为负数时,b = a。

于是我们可以得到如下的结果:

int divpwr2(int x, int n) {
  int bias = (x >> 31) & ((1 << n) + (~0));
  return (x + bias) >> n;
}

negate

  • 功能要求:实现 -x
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:5
  • 分值:2

划水题,直接过。

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

isPositive

  • 功能要求:判断x是否大于0,若成立返回1,否则返回0
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:8
  • 分值:3

负数的符号位是1,利用这一性质,判断x的符号位是否为0,同时为了把0的情形也归入进去,增加或上 !x 即可。

int isPositive(int x) {
  int sgn = (x >> 31) & 0x01;
  return !(sgn | !x);
}

isLessOrEqual

  • 功能要求:判断是否 x<=y,若成立返回1,否则返回0
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:24
  • 分值:3

本题要求判断 x<=y,第一反映就是要判断 y - x >= 0,这个问题就是上一题,很好解决。关键在于处理 y - x 溢出的问题,因为此时我们得到的结果是相反的。

那么,y - x 何时会溢出呢,分析发现只有当 x, y异号时,y - x 才会有溢出的可能,所以我们单独把这两种情况拿出来分析:

  • 若x正y负,结果不成立
  • 若x负y正,结果成立

所以我们直接取出x和y的符号位,用^来进行判断,最后把逻辑写进一个式子就好。

int isLessOrEqual(int x, int y) {
  int xsgn = (x >> 31) & 0x01;
  int ysgn = (y >> 31) & 0x01;
  return (((ysgn ^ 1) & (xsgn ^ 0)) | !(((y + ~x + 1) >> 31) & 0x01)) & !((ysgn ^ 0) & (xsgn ^ 1));
}

ilog2

  • 功能要求:返回log2(x)向下取整的结果,x取值为正数
  • 操作符限制:! ~ & ^ | + « »
  • 最大操作符数量:90
  • 分值:3

注意到这里x的取值是正数,故我们不需要考虑负数符号位的问题。本题求这个log2(x)向下取整,实际上就是求最高位1的位数,一个很自然的想法就是把最高位1之后的位全部填充位1,接下来应用上面的bitCount的过程就好(最后要减去1),本题的限制是90个操作符,把bitCount的过程搬过来也是够的。

填充的方法可以用不断的右移取或来实现,代码如下:

int ilog2(int x) {
  int mask1 = 0x55 + (0x55 << 8);
  int mask2 = 0x33 + (0x33 << 8);
  int mask3 = 0x0f + (0x0f << 8);
  int mask4 = 0xff + (0xff << 16);
  int mask5 = 0xff + (0xff << 8);
  mask1 += mask1 << 16;
  mask2 += mask2 << 16;
  mask3 += mask3 << 16;
  x |= x >>1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x = (x & mask1) + ((x >> 1) & mask1);
  x = (x & mask2) + ((x >> 2) & mask2);
  x = (x & mask3) + ((x >> 4) & mask3);
  x = (x & mask4) + ((x >> 8) & mask4);
  x = (x & mask5) + ((x >> 16) & mask5);
  return x + ~0;
}

第二部分:浮点数题目

首先看限制要求,原文如下:

FLOATING POINT CODING RULES

For the problems that require you to implent floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
     that you are allowed to use for your implementation of the function. 
     The max operator count is checked by dlc. Note that '=' is not 
     counted; you may use as many of these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. Use the BDD checker to formally verify your functions
  5. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies 
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.

这里的限制就轻松了许多,这里只翻译一下和整数题目相比不同的地方

  • 可以使用流程控制语句,如if while switch等
  • 使用任意大小的整数
  • 使用int 和 unsigned 类型
  • 使用任意的操作符,如 || &&等

浮点数的题目,主要难点就在于对浮点数的位级表示的理解,这里我就不详细讲了,这不是重点。

float_neg

  • 返回 -f,当输入是NaN时,返回NaN
  • 最大操作符数量:10
  • 分值:2

浮点数第一个题目,送分。对于一般的数,只需要改变符号位的值就好,这里用uf += (1 << 31)来实现,对于NaN单独说一下就好。

unsigned float_neg(unsigned uf) {
  if (((uf >> 23) & 0xff) != 0xff || (uf & 0x7fffff) == 0)
    uf += (1 << 31);
  return uf;
}

float_i2f

  • 实现int到float的转换
  • 最大操作符数量:30
  • 分值:4

这一题要求实现int到float的强制转换,过程虽然有点复杂,不过CS:APP书本上讲的还是非常详细的,这里推荐一篇文章C语言中int到float的强制类型转换,可以供大家参考。

接下来详细说一下过程:

首先,整数补码表示的负数和浮点数的负数不同,浮点数的正负数除了符号位以外完全相同,所以我们第一个该做的事情,就是将负数取绝对值,同时用一个数来记录符号位。但是特别的,我们在这里要注意一下0和0x80000000,前者应该直接返回0,后者取绝对值之后没有与其对应的数。

接下来,我们要找到待转化的整数有多少位,我们将其一直左移(这里左移是因为右移会导致数据消失),左移了i位,那么它就有32 - i位。

由于浮点数的尾数只有23位,并且是1-2之间的小数部分,因此我们对x再左移一位,去掉第一位,接下来右移9位,取后23位就是我们要的小数部分。

指数部分按照定义,由 32 - i 加上偏移量 127得到。

最后将符号位,指数位,尾数位或起来就得到初步的结果。

这时我们仍然要关系舍入的问题,具体书上写的也很详细,丢掉的部分大于0.5就进1,低于0.5就舍掉,等于0.5时,在丢掉部分之前的最后以为是1就进1,否则舍掉。

我们来看怎么实现这段逻辑。首先判断最后九位是否是0x100,不是的话放心丢掉。接着判断后面八位是否全为0,不是的话放心进1,全为0的话再考虑右移9位后的最后一位是否为1,进1的情况也就是返回的结果加1,整个过程并不是太复杂。

最终完成的代码如下:

unsigned float_i2f(int x) {
  int count = 1;
  int f_sgn = (x >> 31) & 0x01;
  unsigned f = 0;
  unsigned f_exp;

  if (f_sgn == 1)
    x = ~x + 1;

  if (x == 0x80000000)
    return 0xcf000000;

  if (x == 0)
    return 0;

  while((x & 0x80000000) != 0x80000000) {
    count++;
    x <<= 1;
  }

  x <<= 1;
  f_exp = 159 - count;
  f |= (x >> 9) & 0x7fffff;
  f |= (f_exp << 23);
  f |= (f_sgn << 31);

  if ((x & 0x0100) == 0x0100) {
    if (x & 0xff)
      f += 1;
    else {
      if (f & 0x01)
        f += 1;
      }
  }
  return f;
}

float_twice

  • 返回浮点数f*2的结果
  • 最大操作符数量:30
  • 分值:4

最后一题难度不大,三种情况。如果是非规格化的数,左移一位即可,溢出也是到了指数位的最低位,并不影响。如果是规格化的数,指数位加一即可。如果是NaN,返回NaN。

unsigned float_twice(unsigned uf) {
  unsigned uf_sgn = (uf >> 31) & 0x01;
  unsigned uf_exp = (uf >> 23) & 0xff;
  if (uf_exp == 0) {
    uf <<= 1;
    uf += (uf_sgn << 31);
  }
  else if (uf_exp != 0xff) {
    uf_exp += 1;
    uf &= 0x807fffff;
    uf = uf + (uf_exp << 23);
  }
  return uf;
}

后记

最终贴上完成之后的分数

整个lab做了两天半,其中卡的时间最长的就是bitCount,这个分组计数的方法十分巧妙。其他的感觉浮点数的题目比整数的题目要好想很多,只要认真看过书本,理解了位级表示,都能很快搞定。

感觉最大的锻炼就是熟练了各种位运算的技巧,掌握了整数和浮点数的表示,学会合理规避溢出带来的问题。

接下来就向下一章和Bomb Lab进发!