datalab实验是CSAPP中关于整数和浮点数的位运算的实验，对于我们理解位运算和整数，浮点数的位级表示有着很好的帮助。

实验目的

修改bits.c的C语言代码，使其通过所有在不违反任何编码准则的情况下，在btest中进行测试，进一步熟悉整型及浮点数的位表达形式，实现常用二进制运算的常用方法。

实验环境

个人电脑PC，linux环境，dlc编译环境

实验内容及操作步骤

实验内容

(1).替换bits.c中各个函数中的return，实现相应功能，并通过btest测试，具体格式如下：
int Funct(arg1, arg2, …) {
/* brief description of how your implementation works */
int var1 = Expr1;
int varM = ExprM;
varJ = ExprJ;
…
varN = ExprN;
return ExprR;
}
(2).补充函数要求如下：
每一个“Expr”只能使用如下规则：
①　数字只能使用0到255（0xff），不能使用像0xffffffff这样大的数字
②　函数参数和局部变量(没有全局变量)
③　一元运算目：! ~
④　二元运算目：& ^ | + << >>
下面的操作不被允许：
①　使用任何控制结构，如if, do, while, for, switch等。
②　定义或使用任何宏。
③　在此文件中定义任何其他函数。
④　调用任何库函数。
⑤　使用任何其他的操作，如&&, ||, -, or ?:
⑥　使用任何形式的casting
⑦　使用除int以外的任何数据类型。这意味着你不能使用数组、结构等。
对于需要你执行浮点运算的问题，编码规则较不严格。允许使用循环和条件控制也可以同时使用int和unsigned。可以使用任意整数和无符号常量。

操作步骤

(1).首先将代码包datalab-handout复制到Ubuntu系统中（复制之前需要安装好vmware-tools）,接下来的实验都是在该文件目录下进行。
(2).补充bits.c中的所有函数，并遵循实验内容中提到的补充规则，另外需要注意编码过程中运算符的合法性和最大操作符数。
(3).实现代码如下

• 函数1

要求
bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
代码实现
int bitAnd(int x, int y) {
  return ~((~x) | (~y));
}

代码解释：实现x和y的按位与运算，由于有运算符数量的限制，这里可以采用德摩根律进行转化后再求解，即x & y=~~(x&y)=~((~x)|(~y))。

• 函数2

要求
getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
代码实现
int getByte(int x, int n) {
    return (x>>(n<<3))&0xff;
}

代码解释：首先将所取字节移动到最右边，再和0xff相与使得前面3个字节清零。

• 函数3

要求
logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
代码实现
int logicalShift(int x, int n) {
  int mask=(((~(1<<31))>>n)<<1)+1;
  return mask&(x>>n);
}

代码解释：逻辑右移是左端补0，算术右移是填充符号位，这里直接将x右移得到的是算术右移的结果，这里需要产生一个掩码mask来消除算术右移n的符号位，采用的办法是0相与消除符号位，其余部分和1相与不变。

• 函数4

要求
bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
代码实现
int bitCount(int x) {
  int count; 
    int tmp1 = (0x55)|(0x55<<8); 
    int mask1 = (tmp1)|(tmp1<<16); 
    int tmp2 = (0x33)|(0x33<<8); 
    int mask2 = (tmp2)|(tmp2<<16); 
    int tmp3 = (0x0f)|(0x0f<<8); 
    int mask3 = (tmp3)|(tmp3<<16); 
    int mask4 = (0xff)|(0xff<<16); 
    int mask5 = (0xff)|(0xff<<8); 
    count = (x&mask1)+((x>>1)&mask1); 
    count = (count&mask2)+((count>>2)&mask2); 
    count = (count + (count >> 4)) & mask3; 
    count = (count + (count >> 8)) & mask4; 
    count = (count + (count >> 16)) & mask5; 
    return count; 
}

代码解释：输入一个整型数字，输出该数字二进制表示中有多少个1，可以通过二分法进行查找进行记录，先计算每两位中1的个数，并用对应的2位来进行存储，然后计算每四位中1的个数，用对应的4位进行存储，最后得到16位中1的个数，即x中1的个数

• 函数5

要求
bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
代码实现
int bang(int x) {
  return ~((x|(~x+1))>>31)& 1;
}

代码解释：不使用!而实现!功能。第一步~x+1求补码，与x本身进行相或后得到最高有效位，如果大于0那么最高有效位必为1，将该数逻辑右移31位后得到要么全零要么全1的数，然后与1相与得到一个相反的值就可以实现！的操作。

• 函数6

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

代码解释：0x80000000的补码是其本身，这里直接将1左移31位即可。

• 函数7

要求
fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1    0101   1100 100
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
代码实现
int fitsBits(int x, int n) {
  int shift=32+(~n)+1;
  return !(x^((x<<shift)>>shift));//*左移32-n位，再右移32-n位，最后和原数比较*/
}

代码解释：对于正数来说，从第32位到第n位必须全是0，因此左移（32-n）位再右移（32-n）位一定和原数相同，如果不相同，一定是因为第32位到第n位有至少一个1。对于负数，也是类似的情形，从32位到第n位必须全是1，这里定义一个移位数shift,将左移右移之后的结果和原数x比较，相同则可表示。另解!(((x >> (n+(~0))) + 1)>>1)

• 函数8

divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
代码实现
int divpwr2(int x, int n) {
    return (x+((x>>31)&((1<<n)+(~0))))>>n;//x需要加上一个偏移量m=x>0?x:x+2^k-1

代码解释：x除以2的n次方，实际上直接右移n位即可，面对负数时需要加上一个偏移量2^n-1。详细解释可以参看《深入理解计算机系统》（第2版）37页。

• 函数9

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

代码解释：取x的相反数，用0-x也就是0+x的补码，所以直接返回~x+1即可。

• 函数10

要求
isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
代码实现
int isPositive(int x) {
  return !(x>>31|(!x)); //符号位取反 
}

代码解释：如果x大于0则返回1，否则返回0，因此直接判断符号位，但需要特殊考虑0。

• 函数11

要求
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 x_f=(x>>31),y_f=(y>>31);//获得x,y的符号
  int judge1=(!((y+(~x)+1) >>31));//同号，y-x,看符号位
  int judge2=x_f&1; //异号，如果x>=0,说明 x>y
  int sign=x_f^y_f;
  return (!sign & judge1)|(sign &judge2);
}

代码解释：首先对x,y进行符号位的判断，如果x,y异号的话，x>=0,则说明x>y,返回0，如果x,y同号直接进行相减判断符号即可。

• 函数12

要求
ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
代码实现
int ilog2(int x) {
  int bitsNumber=0;
    bitsNumber=(!!(x>>16))<<4;//确定a 
    bitsNumber=bitsNumber+((!!(x>>(bitsNumber+8)))<<3);//确定b 
    bitsNumber=bitsNumber+((!!(x>>(bitsNumber+4)))<<2);//确定c 
    bitsNumber=bitsNumber+((!!(x>>(bitsNumber+2)))<<1);//确定d 
    bitsNumber=bitsNumber+(!!(x>>(bitsNumber+1)));//确定e 
    return bitsNumber;
}

代码解释：求log2(x)，即判断多少位二进制表示。先将x右移16位i，若大于0，则先得到(10000)=16,否则得到0。 在现有数值的基础上依次相加。x在现有bitsNumber的基础上依次加8、4、2，相当于一个二分的过程， 每一步都是相同操作，即将x右移指定位数，由结果是否为0，决定bitsNumber继续加几。

以下开始处理浮点数，实现规则比整数要松一些，允许使用循环和条件控制也可以同时使用int和unsigned。可以使用任意整数和无符号常量。

• 函数13

要求
float_neg - Return bit-level equivalent of expression -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 representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 代码实现
 unsigned float_neg(unsigned uf) {
   if((uf & 0x7f800000)==0x7f800000 &&(uf !=0x7f800000)&& (uf!=0xff800000))
   {
       return uf;
   }
   else return uf^0x80000000;
}

代码解释：首先判断浮点数是否为nan，如果为nan则返回本身，否则返回-f。判断浮点数可以采用f和0x7f80000相与的结果来判断。

• 函数14

要求
float_i2f - Return bit-level equivalent of expression (float) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
代码实现
unsigned float_i2f(int x) {
    unsigned shiftLeft=0;  
    unsigned afterShift, tmp, flag;  
    unsigned absX=x;  
    unsigned sign=0;  
    //special case  
    if (x==0) return 0;  
    //if x < 0, sign = 1000...,abs_x = -x  
    if (x<0)  
    {  
        sign=0x80000000;  
        absX=-x;  
    }  
    afterShift=absX;  
    //count shift_left and after_shift  
    while (1)  
   {  
        tmp=afterShift;  
        afterShift<<=1;  
        shiftLeft++;  
        if (tmp & 0x80000000) break;  
   }    
    if ((afterShift & 0x01ff)>0x0100)  
        flag=1;  
    else if ((afterShift & 0x03ff)==0x0300)  
        flag=1;  
    else  
        flag=0;  
    return sign + (afterShift>>9) + ((159-shiftLeft)<<23) + flag;  
}

代码解释：将整形转化为无符号浮点数，即求浮点数。先取的符号位，再将剩余部分全部取为正数形式，即absx，即可以得到无符号的数值。然后将有数字的部分直接移动到最高位，记录移动的位数，再将其移动9位（因尾数只要23即可）。对于阶码部分，由于记录的是小数点从31位右数到第一个1，但实际上需要处理的是从第0位到第一位，所以E=32-shiftleft，bias为127，加上为159，if部分做舍入处理

• 函数15

要求
float_twice - 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 float_twice(unsigned uf) {
   unsigned f=uf;  
        /* Computer 2*f. If f is a NaN, then return f. */  
    if ((f & 0x7F800000) == 0){  
        //shift one bit to left  
                f = ((f & 0x007FFFFF)<<1) | (0x80000000 & f);  
    }  
    else if ((f & 0x7F800000) != 0x7F800000){  
        /* Float has a special exponent. */  
        /* Increment exponent, effectively multiplying by 2. */  
        f =f+0x00800000;  
    }  
    return f;  
}

代码解释：将无符号浮点数乘2，对无阶码小数，对其尾部乘2即可，即直接左移一位，但要提前记录符号位。对于规格化数，直接对其阶码+1即可

(4).使用dlc编译器来检查解决方案是否符合编码规则，并用btest来测试编写程序的正确性。

实验结果及分析

(1).使用dlc检测bits.c是否有错误

结果显示没有错误，说明代码编写规范。
(2).使用dlc的-e选项检查各个操作数是否符合要求

(3).使用btest检验函数实现代码的功能正确性，先使用make编译生成btest可执行文件（这里用make,对当前目录下所有程序进行编译）

(4).调用btest命令检查bits.c中所有函数功能的正确性，以便下一步查找错误原因，执行./btest bits.c后结果如下：

这是经过调试之后的测试结果，所有功能得到验证。
(5).测试结束后或者每次用btest测试时，需使用make clean删除生成的可执行文件。

(6).测试btest其它功能
./btest:测试所有函数的正确性，并输出错误信息
./btest –h：打印出相关提示信息。

./btest –g :测试所有函数在不返回错误信息的紧凑型模式

./btest –f float_twice:测试某特定的函数

./ishow x; ./fshow y:显示整数和浮点数的位级表示。

收获和体会

(1).通过该实验进一步熟悉了整型及浮点数的位表达形式，实现常用二进制运算的常用方法。
(2).对基本的二进制运算的总结
按位与（&）：参与运算的数字转换为二进制，而后逐位对应进行运算。
按位或（|）：参与运算的数字转换为二进制，对应位相或。
异或（^）: 参与运算的数字转换为二进制，对应位相异或，规则两位相同为0，不同为1。异或运算能够实现伟翻转，高效交换两个变量的值等功能。
按位非（_{）：将一个数按位取反,即}0 = 1,~1 = 0。
逻辑非（！）：将真值结果取反，如！5=0，！0=1。
(3).算术移位和逻辑移位的区别
左移：x<<y表示将x左移y位，左边的位全部丢弃，在右边全部补0。
右移：x>>y表示将x右移y位，右边的位全部丢弃，对于逻辑移位，左边补0，对于算术移位，左边填充符号位。
(4).实验过程中遇到不会做的题目，通过上网查阅资料，回顾课本知识点，体会到了C语言中使用二进制运算也可以实现很多功能，如两个数的大小比较，不用循环统计二进制数据中1的个数，获取某一字节等等，对相整数和浮点数的位级表示等相关知识也有一定的提升。

参考博客