CSAPP Data Lab实验报告

1.isAsciiDight(int x)

实现代码：

1
2
3
int isAsciiDigit(int x) {
    return(!((x+~48+1)>>31))&!!((x+~58+1)>>31);
}

实现思想：

题目要求当参数x大于等于48小于等于57的时候返回1，否则返回0。

于是我们将x减去48并将其右移31位保留其符号位，此时若x减去48大于等于0则符号位为0因此要将其进行取反；同样，将x减去58并将其右移31位，此时真好同上面那种情况相反，因此要对符号位取两次反，最后再取与运算获得结果。

2. int anyEvenBit(int x)

实现代码：

1
2
3
4
5
int anyEvenBit(int x) {
    int t=0x55 | (0x55<<8);
    int mask=t | (t<<16);
    return !!(x&mask);
}

实现思想：

题目要求当参数x有任何偶数位设置为1时返回1，否则返回0。

因此我们构造一个掩码，令该掩码的偶数位全为1，奇数位全为0，再令输入的参数x和该掩码进行与运算，若x中有偶数位被设置为1的话则与之后必不为0，因此两次取反返回。

3. int copyLSB(int x)

实现代码：

1
2
3
int copyLSB(int x) {
    return ((x<<31)>>31);
}

实现思想：

本题要求设置所有位为参数x的最低位，所以先左移31位再右移31位进行符号位扩展。

4. int leastBitPos(int x)

实现代码：

1
2
3
int leastBitPos(int x) {
    return x&(~x+1);
}

实现思想：

本题要求返回参数x最低设置为1的数。

我们先将x按位取反，取反后的数与原数据正好每一位都相反，我们再将该数加1，则此数会向前进一位，此时当且仅当原数的最低取取1位和取反后数据该位都为1，因此进行与运算后得到结果。

int divpwr2(int x, int n)

实现代码：

1
2
3
4
5
int divpwr2(int x, int n) {
    int sign =(x>>31)&1;
    int bias = (sign<<n)+~sign +1;
    return (x+bias)>>n;
}

实现思路：

实验要求返回所给参数x/2^n的结果。

首先判断所给参数x的标志位，将x右移31位再和1进行与运算，若是正数则为0，负数则为1。

然后就是设置正数和负数的取整问题。当x为正数的时候，右移后向下取整，和题目要求相同，但是当x为负数时，也是向下取整，但此时题目要求要向上取整，因此要给负数加上一个偏置值再进行右移操作。因此负数要加上2^n-1来保证取整。

6.int bitCount(int x)

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int bitCount(int x) {
    int t = 0x55 + (0x55<<8);
    int mask = t + (t<<16);
    x = (x&mask) + ((x>>1)&mask);

    t = 0x33 + (0x33<<8);
    mask = t + (t<<16);
    x = (x&mask) + ((x>>2)&mask);

    t = 0xf + (0xf<<8);
    mask = t + (t<<16);
    x = (x&mask) + ((x>>4)&mask);

    mask = 0xff + (0xff<<16);
    x = (x&mask) + ((x>>8)&mask);

    mask = 0xff + (0xff<<8);
    x = (x&mask) + ((x>>16)&mask);

    return x;
}

实现思路：

问题要求返回参数x的位为1的个数。

所以我们需要一个个检查参数的每一位是否为1，并且将之累加起来。

从两位比特位入手，计算两位比特数中1的个数，就是高位与低位之和。

00: 0+0=(00)2

01: 0+1=(01)2

10: 1+0=(01)2

11: 1+1=(10)2

令一个二进制数B为b32b31…b1

则L(l,r)表示一个二进制数在l和r区间之间的1的个数。

1
2
L(l,r)= L(l,x)+ L(x+1,r) (l<=x<r)
L(l,r)= bl (l=r)

对于一个32位的整数来说，可以用动态规划的思想自底向上计算。先计算L(1,1)+L(2,2)。

先构造一个只有低位L(1,1)的数a=x&x=0x01和高位L(2,2)的数b=(x>>1)&0x01,但我们发现可以同时计算L(3,3)和L(4,4)等数。只需将构造改为：

a=x&0x55555555,b=(x>>1)&0x55555555, x=a+b

计算L(1,2)和L(3,4)以此类推：

a=x&0x33333333, b=(x>>1)&0x33333333, `x=a+b

7. int conditional(int x, int y, int z)

实现代码：

1
2
3
4
int conditional(int x, int y, int z) {
  x = (!!x)<<31>>31;
  return (y&x)|(z&~x);
}

实现思路：

题目要求该函数实现三元运算符，若x为真，则返回y,否则返回z。

若x的取值为0x00000000或0xFFFFFFFF。则答案为(x&y)|(~x&z)。

若x！=0时，将x=0xFFFFFFFF。x = (!!x)<<31>>31。

8. int isNonNegative(int x)

实现代码：

1
2
3
int isNonNegative(int x) {
    return !(x>>31);
}

实现思路：

判断最高位。

9.int isGreater(int x, int y)

实现代码：

1
2
3
4
5
6
7
int isGreater(int x, int y) {
    int sign_x=x>>31;
    int sign_y=y>>31;
    int equal=!(sign_x^sign_y)&((~y+x)>>31);
    int notequal=sign_x&!sign_y;
    return !(equal|notequal);
}

实现思路：

题目要求如果x>y返回1否则返回0。

以下情况会返回1：

当x>0,y<0，或者当x和y符号相同时mark_ = ~((x^y)>>31)，满足x+~y+1>0，x!=y时，equl_ = !!(x^y)=1，x+~y+1>=0时，(~(x+~y+1))>>31 = 0xffffffff

10.int absVal(int x)

实现代码：

1
2
3
4
int absVal(int x) {
  int sign=x>>31;
  return (x^sign)+(sign&1);
}

实现思路：

返回x的绝对值。

首先判断x的符号位，即右移31位。

倘若为正数，则返回值不变；则先用x与sign异或再加上sign与1与运算。

倘若为负数则异或后（即按位取反减1）后要再加上。

11. int isPower2(int x)

实现代码：

1
2
3
4
5
6
int isPower2(int x) {
    int sign1=!(x>>31);
    int sign2=!!x;
    int sign3=!(x&(x+~0));
    return (sign1&sign2&sign3);
}

实现思路：

题目要求如果参数x是2的权重返回1，否则返回0（负数都返回0）。

首先sign1判断x是正数还是负数，sign2判断x是否为0。若x为2的倍数，则x的位中则只有一位为1，因此当x为2的倍数时x和（x-1）按位与的结果必然为0，否则为1，因此将!(x&(x+~0))作为sign3最后取与运算则得到结果。

12.unsigned float_neg(unsigned uf)

实现代码：

1
2
3
4
unsigned float_neg(unsigned uf) {
    if((uf&0x7fffffff)>0x7f800000)return uf;
    return uf^0x80000000;
}

实现思路：

直接使用>判断即可，但需要注意+0/-0还有NaN这两种特殊情况。

判断NaN时，指数段为0xff，小数段不全为0，(uf&0x7fffffff) > 0x7f800000。

13.unsigned float_i2f(int x)

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned float_i2f(int x) {
  int s_ = x&0x80000000;
  int n_ = 30;
  if(!x) return 0;
  if(x==0x80000000) return 0xcf000000;
  if(s_) x = ~x+1;
  while(!(x&(1<<n_))) n_--;
  if(n_<=23) x<<=(23-n_);
  else{
    x+=(1<<(n_-24));
    if(x<<(55-n_)) ;else x&=(0xffffffff<<(n_-22));
    if(x&(1<<n_))  ;else n_++;
    x >>= (n_-23);
  }
  x=x&0x007fffff;
  n_=(n_+127)<<23;
  return x|n_|s_;
}

实现思路：

分三部分处理，获取符号位s_ = x&0x80000000，若为负数-x，变为正数，则0x80000000为特殊情况分开处理，考虑特殊情况，0x0和0x80000000，这两种情况直接返回0和0xcf000000。

获取最高位的1所在位置，while(!(x&(1<<n_))) n_--;。

若n_ <= 23这个数需要向左移动到小数部分起始位置（将1放在第23位上），if(n_<=23) x<<=(23-n_);。

若n_ > 23这个数需要向右移动到小数部分起始位置（将1放在第23位上），这时候需要考虑移出部分的舍入问题，若移出部分大于0.5则向上舍入，若小于0.5则向下舍去，若等于0.5则向偶数舍入。

先将>=0.5情况等同考虑，向上舍入x+=(1<<(n_-24))。若==0.5时，舍入情况若为奇数，我们需要-1操作变为偶数，即将最低位的1变为0，x&=(0xffffffff<<(n_-22))，若向上舍入时最高位产生了进位，还需要加上进位if(x&(1<<n_)) ;else n_++;。之后拼接浮点数即可。