CSAPP实验1:DataLab

发表于 | 分类于 |

实验简介

​ Data LAB 目的是熟悉位运算

要求：

  • 只修改bit.c
  • 使用 btest 进行验证
  • 每次修改完之后都要make clean再make
  • 整数部分：要求只能使用规定的操作符并且不能使用循环、条件语句
  • 在函数开始时声明所有变量，只能使用局部变量
  • 不能使用其他函数/宏/int外的类型/类型转换
  • int都是默认二进制补码编码 2’s complement，32bit
  • 要考虑数据溢出的情况，比如相减，同号才能相减，否则结果出错

Tips：

  • # ./btest -f [函数名]，检验某个函数 ./btest 检验所有函数

  • 关注int型的表示范围 -2^31~2^31-1以及一些特殊的数字的补码编码 -2^31：0x80 00 00 00 -1：0xff ff ff ff

  • 一个数的相反数是 ~x+1

  • 在float的实验中要对该数是不是规格化分情况
  • 逻辑右移不带符号，>>是算术右移，带符号
  • 0的特性，若x=0, ~x+1和x的符号位都为0。而其他情况则至少有一个数符号位为1。（也可能两个符号位都为1的情况，如x=0x80 00 00 00

个人认为最难的是ilog2

文件说明

Github地址：Data Lab

  • bit.c：实现缓存模拟器的文件
    • Examples：表示用例‘
    • Legal ops：允许的操作符
    • Max ops：最多操作数
    • Rating：难度系数

在每一次更新之后，首先用make生成文件，之后用相应的test跑分即可

整形

logicalShift

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 val = ~(1<<31) ; // 0x7f ff ff ff 
  val = ((val >> n) <<1)+1;
  return  val & (x>>n);
}

逻辑右移：需要去掉负数带来的符号位。产生一个数，前n-1位0，之后全为1，和算数右移后的数进行按位与操作，使左边n-1位为0。

bitCount

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * 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 mask = ((0x01<<8|0x01)<<8|0x01)<<8|0x01 ;
  int val = mask & x;
  val += mask & x>>1;
  val += mask & x>>2;
  val += mask & x>>3;
  val += mask & x>>4;
  val += mask & x>>5;
  val += mask & x>>6;
  val += mask & x>>7;
  val += val>>16;
  val += val>>8;
  return val&0xff;
}

要求：计算32进制数x中1的个数

思路：如果依次检测，ops必然超过。可以每次检测4位，然后再进行累加。先初始化mask=0x01010101，用来检测x>>i的0,8,16,24位是否为1然后x顺序移动重复上述检测，一共8次。相当于将一个32位分成4段同时进行，结果存储在分别四段的8位中。整合：将前16位加到后16位上，然后把8~16位加到低8位。取最低8位为最后结果。

mark

bang

1
2
3
4
5
6
7
8
9
10
/* 
 * 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+1)^x))>>31) & 0x01;
}

要求：输出！x。即x!=0, !x =0 ; x=0, !x =1

思路：根据0的特性，若x=0, ~x+1和x的符号位都为0。而其他情况则至少有一个数符号位为1。（也可能两个符号位都为1的情况，如x=0x80 00 00 00,所以不能用^）或运算之后取反，再取符号位。

tmin

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

要求：32位二进制补码的最小整数，也就是0x80 00 00 00。（如8位整数，补码编码最小数就是-128，和128是相等的，也就是1000 0000(2)）

fitBits

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
  int shiftBits = 32 + (~n+1); // 32-n
  return !(x^((x<<shiftBits)>>shiftBits));
}

要求：判断x是否可以用n位补码来表示。考虑的是数字是否在范围内能表示，也就是移动后符号位是否会变化

先左移32-n位，再右移32-n位。即保留最后n位。再和x进行异或，若两者相同，表示x可以被表示成一个n为整数，！0为1。eg.以5为例，5 =000….. 101（2），左移27位后再右移27位得到的是 1111….101，与原来不同。而-4 = 111…100（2），移动后得到的还是111…100，同一个数。

divpwr2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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) {
  int sgn = x >> 31; // 0xffffffff or 0x0
  int mask = (1 << n )+ (~0) ; //2^n -1
  int bias = sgn & mask; //if x >= 0 bias = 0
  return (x+bias) >> n;
}

要求：求x /(2^n)，向0取整。

若是非负数，可以直接右移。如果是负数需要分情况。eg. -33 >>4 =-3 。因为负数右移的结果是，如果除以2次幂出现小数，取小于它的最大整数。所以除非是-4 -8这类后几位全为0的负数，其他的都得+1。

构造一个偏置量，因为要右移n位，如果是负数的话，加上2^n-1（后几位全0的话不变，其余的数进1）后再移位。

negate

1
2
3
4
5
6
7
8
9
10
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x+1;
}

取反加一

isPositive

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x) {
  //int nsgn = ((~x)>>31)&0x01; //nsgn = !sgn
  int nsgn = !(x>>31);
  return nsgn ^ !x ;
}

判断正数。x>0，返回1。其余返回0。主要是处理0的情况。取符号位，再取反，再和 !x 进行异或。

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * 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 sgnx = (x>>31) &0x01;
  int sgny = (y>>31) &0x01;
  int sgn = (sgnx ^ sgny) & sgnx; // x<0 ,y>=0
  int val = y + (~x +1); // y-x
  val = ((val >>31) & 0x01) | (sgnx^sgny); // x-y<0 && sgnx=sgny
  return (sgn|!val); 
}

要求：判断x<=y是否成立可以转化为判断x-y的正负。

注意：当x和y同号时，x-y不会发生溢出，判断符号位即可，当x和y异号时，x-y可能发生溢出，其结果不一定和x的符号一致。所以分解为三部分：x和y异号 / 同号 / 相等。

ilog2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * 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 bitNum =0;
  bitNum  = (!!(x>>16))<<4;
  bitNum = bitNum + ((!!(x>>(bitNum+8)))<<3);
  bitNum = bitNum + ((!!(x>>(bitNum+4)))<<2);
  bitNum = bitNum + ((!!(x>>(bitNum+2)))<<1);
  bitNum = bitNum + (!!(x>>(bitNum+1)));
  return bitNum;
}

要求：由多少位二进制可以表示。log（2）1 = 0

二分法，先右移16位后，若大于0即得到（10000）2 =16，否则得到0，判断最高位是否为0（前16位部分是否为0），若不为0，则包含2^16，同理。

其实ilog2的结果不会超过31，可以想到用5位二进制来表示，也就是分成这5步.

浮点型

浮点型数表示：

mark

float_neg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
 * 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) {
  int tmp =0,ret=0;
  ret = uf ^ 0x80000000; // sign reverse
  tmp = uf & 0x7fffffff; //
  if(tmp > 0x7f800000)   // NaN
    ret = uf;
  return ret;
}

要求：计算-x （unsigned表示的浮点型），可以使用条件语句和其他运算符，当x=NaN时，返回其NaN本身；x！=NaN时，返回-x。

非NaN的数，对最高位异或，将符号位取反。判断NaN，返回本身。

float_i2f

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
unsigned float_i2f(int x) {
  int sign = (x>>31)&0x01;
  int frac_mask = 0x7fffff; // (1<<23) -1
  int frac=0,exp=0,delta=0; 
  int i = 0; 
  if(!x)
    return x;
  else if(x==0x80000000)// -2^31
    exp = 158;          // 158 = 127 +31
  else{
    if(sign)  x=-x;     // abs(x)
    i=30;
    while(!(x>>i))
      i--;
    exp = i+127;        // exp = Bias + E
    x= x<<(31-i);       // clean all those zeroes of high bits
    frac = (x>>8) & frac_mask;//right shift 8 bits to become the fraction,sign and exp have 8 bits total
    x = x & 0xff;
    delta = x>0x80||((x==0x80 )&& (frac&0x01)); //if lowest 8 bits of x is larger than a half,or is 1.5,round up 1
    frac += delta;
    if(frac>>23){ //if after rounding fraction is larger than 23bits
      exp += 1;
      frac = frac & frac_mask;
    }
  }
  return (sign<<31)|(exp<<23)|frac;
}

要求：int转float

分别求出符号位sign，指数部分exp和小数部分frac。原来整数称x

  • 首先把特殊情况的0x0 和 0x80 00 00 00（-2^31）挑出来，因为不能用移位的办法求exp和frac。
  • 求绝对值，找出x的最高位（最左边的1），此时要从第30位找起，因为第31位是符号位。找到之后该位数就是$ v = (-1)^SM(2)^E $中的E，可以求得exp=E+127
  • 求frac：取x最高位后的23位。步骤：先去掉x高位的0，然后右移8位将最高位后的23位移到低23位。
  • 求精度：int转float型会丢失最后8位的精度（31-23=8），所以要判断x的最后八位需不需要进位，如果最后8位超过128（0x80）或者最后8位=128且frac最后一位=1，则进位。
  • 进位后：需要检查frac有没有再进位，frac>>23进行判断，如果frac进位了，那么exp+1，frac再取最后23位。把sign exp frac组合成结果

float_twice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 
 * 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) {
  int sign = uf>>31&&0x01;
  int exp = uf>>23 & 0xff;
  int frac = uf & 0x7fffff;
  if(exp!=0xff){
    if(!exp)  frac=frac<<1;
    else{
      exp += 1;
      if(exp==0xff)
        frac=0;
    }
  }
  
  return sign<<31|exp<<23|frac;
}

要求：求2*uf，uf是一个用unsigned表示的float，当遇到NaN时返回该NaN

检查是否NaN：exp==0xff

然后分两种情况：

1、exp=全0的，frac<<1,exp不变

2、exp≠全0的，exp++，检查exp==0xff，若exp==0xff，此时该数超范围（无穷大），frac=0

取符号位：uf>>31&0x01

取frac：uf&((1<<23)-1)

取exp：(uf>>23)&0xff