CSAPP Lab1. Datalab.md

CSAPP Lab1. Datalab.md

tk_sky 66 2022-09-03

Datalab是第二章信息表示法的实验,主要涉及各种数据类型表示方法的应用。

这个lab需要按照要求用严格的代码规范完成。lab附带评分的程序。

1. bitXor

手写按位异或,只允许用&和~(按位取反)。

异或就是位不相等的时候才是0,也就是他们既不都是1,也不都是0.

都不是1,就是~(x&y)。都不是0,就是~(~x & ~y)

int bitXor(int x, int y) {
  return ~(x&y) & ~(~x&~y) ;
}

2. tmin

求最小的二进制补码。最小的补码就是符号位是1,其他全是0,这样就是$$2^{31}-0$$了。

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

3. isTmax

给一个数,问是不是最大的二进制补码。

对int来说,二进制补码的最大值当然是符号位是0其他全是1,也就是$$2^{位数-1}$$。

题目只允许使用:! ~ & ^ | +

由于不允许使用循环结构,自然不能一位一位的用|或者&去试。这时候异或^和取反~就成了我们最有用的工具。

考虑返回1的情况,如011,01111,0111111,再考虑返回0的情况,如0110,11110,我们发现最大补码的特点是第一位是0,其他位都是1. 要用到异或,这时候应该用可以用的加法+来使得异或可以发挥用处。

由于最大补码只有第一位是0,所以+1后一定变成如1000,其他任意情况都不满足这一性质。1000和他本身0111是相反的。于是就写成~x==(x+1) 。但题目不允许用==,考虑到a^a==0, 于是可以改成:!(~x^(x+1))

但这里有个例外要写特判。-1(1111)+1以后为0,也满足我们的判断条件。所以要特判把-1排除掉。

怎么排除-1呢?-1+1当然==0了。注意到这里允许用!运算符,!x可以用来检测x是否为0. 于是用两个!即可排除-1(x+1=0)的情况。

return !(~x ^ (x+1)) & !!(x+1);

4. allOddBits

给一个数,判断是否他的二进制偶数位都是1. 判断的范围是int范围。

既然范围是$$2^{32}$$,那只需要设a=10101010101010101010101010101010(32位),然后判断a&x是否等于a就行了。

这里等于还是用异或来判断。将a转换成十进制输入程序:2863311530。

int allOddBits(int x) {
  int a = 2863311530;
  return !((x&a)^a);
}

5. negate

给一个数,输出他的相反数,当然不能用-。

考虑到补码编码,是用除了最高位的值减掉只看最高位表示的值,1可表示为0001,-1可表示为1111. 于是容易看出-1 = ~1 + 1。 推广一下,得到-a = ~a + 1

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

6. isAsciiDigit

判断给定x是否 0x30<=x<=0x39。

其实就判断是否x-0x30 和 0x39-x 都>=0就行了。

如何判断>=0呢,对补码编码,最高位的那个bit就表示了正(或0)负。于是只要让他&(10000...(即0x80000000,只有第一位是1,或-2147483648,即int表示的最小值)),就可以取到那一个特定位的值了。这个技巧还是蛮常用的。这里不给用减号,但前面正好写了negate(),当然要用了。

int isAsciiDigit(int x) {
  int a = x+ negate(0x30);
  int b = 0x39 + negate(x);
  int c = -2147483648;
  return !(a&c) & !(b&c);
}

貌似其他博客不是我这样做的,不过我觉得这样做挺简单的。

7. conditional

要求用位运算实现三目运算符一样的效果。

即:if x == 0 then return z else return y

不能用条件分支,那肯定需要用+来连接两个部分,每个部分在不相关的时候用位运算置0.

用位运算怎么置0呢,当然是x & 0 = 0了。那另外那边怎么保持原样呢?

其实刚刚我们就发现,-1的二进制表示是111111...111。于是x & -1 = x

这里可以用!!x和!x得到对应的1和0,再利用上面的negate()就可以得到-1和0了。

int conditional(int x, int y, int z) {
  return (y&negate(!!x)) + (z&negate(!x));
}

一行解决,貌似比我看到的题解都简单。

8. isLessOrEqual

判断两个数是否小于等于。

上面我们写过判断>=了,把符号交换一下就可以复用了。

int isLessOrEqual(int x, int y) {
  int a = y + negate(x);
  int b = -2147483648;
  return !(a&b);
}

题目没有讲数据范围,如果数据范围大的话可能会爆int(事实上评测下来没有)。如果要写的很完善,可以额外写一个逻辑判断溢出(本不该发生改变的符号产生改变)。

9. logicalNeg

实现!运算符。即if x == 0 then return 1 else return 0

考虑以下事实:

对补码,正数与零的最高位为0,而负数的最高位为1;

在negate(取相反数)操作时,正数和负数的最高位都会变换,而零在操作时最高位不会变换。

于是我们可以对x取相反数,将0和正数区分开来;而0和负数在表示上本质不同,很容易区分他们。

右移时,若最高位为1,则填充的bit为1,否则为0。于是得到技巧:

要得到最高位,可使x>>31,若值为-1(1111...11),则最高位为1;若值为0,则最高位为0。

于是我们可以用 negate(x)| x 来区分。对于正数,其值为1xxxx..xx | 0xxx..xx,对于负数,其值也为0xxx..xx | 1xxx..xx ,结果都为1xx..xx。于是我们右移31位,他们的结果都是-1;对于0,其值始终为0.

这样我们再最后给他+1,就达到为0返回1,其他返回0的效果了。

int logicalNeg(int x) {
  return ( (negate(x)| x) >>31) +1 ;
}

10. howManyBits

求最高的一位有效位是多少。

这题有点奇怪,其实就是暴力位移了以后判断,要优化的话也就走一个倍增,不知道有没有更好的做法。

首先要处理负数,如果是负数就按位取反。原理是决定负数补码表示的值的位是左边数第一个0。例如1101和11101表示的值是一样的。按位取反以后0就变成1,1变成0,就和正数的处理方法一样了。取符号sign为0或1,结合&和|,就很好处理了。

接下来就暴力的倍增,设变量left16 left8 left4 left2 left1 left0,分别表示剩下的x位中是否有1。从16开始,每次进行一下位移,来检测剩下16位中是否有1.如果有,则右移16位,同时记录在变量上;如果没有则不移动。然后再到8,4,...以此类推。

最后把记录的移动的位数加起来,再+1(符号位也要算在内)就行了。

int howManyBits(int x) {
  int left16,left8,left4,left2,left1,left0;
  int sign = x>>31;
  x = (sign & ~x) | (~sign & x);
  left16 = (!!(x>>16))<<4;
  x>>=left16;
  left8 = (!!(x>>8))<<3;
  x>>=left8;
  left4 = (!!(x>>4))<<2;
  x>>=left4;
  left2 = (!!(x>>2))<<1;
  x>>=left2;
  left1 = !!(x>>1);
  x>>=left1;
  left0 = x;
  return left16 + left8 + left4 + left2 + left1 + left0 + 1;
}

11. floutScale2

这题用整数模拟浮点数结构,要求把浮点数*2.

首先题目要求判断是否是NaN,如果是的话就直接return。

32位单精度浮点数由1位符号位s,8位阶码(指数),23位尾数按顺序组成。

对于NaN和无穷,就是exp全是1的情况,按题目要求直接return uf。

下面要考虑两种编码形式。

规格化编码,即exp!=0时,用于编码>1的数。这时候flac的值=1+M(实际表示的尾数),所以不能直接乘2,而应该给阶码exp+1(相当于给指数+1)。

非规格化编码,即exp==0,用于编码<1的数。这时候flac的值就是M,因为编码的是<1的数,所以不能随便加exp。直接对M*2.

unsigned floatScale2(unsigned uf) {
  unsigned s,exp,frac;
  s = (uf>>31)&1;
  exp = (uf&0x7f800000)>>23;
  frac = uf&0x7fffff;
  unsigned ans;
  if(exp == 0xff) return uf;
  if(exp == 0) ans = (s<<31) | (exp<<23) | frac<<1;
  else ans = (s<<31) | ((exp+1)<<23) | frac;
  return ans;
}

12. floatFloat2Int

题意是将给定浮点数表示转换成整数。

转换浮点数到整数的时候要注意到浮点数能表示的范围比int大得多,如果超出范围要按照题意返回0x80000000u。什么时候超出范围?E>=31的时候,int就32位,指数这么大换算到int里肯定超范围了。

剩下的都是规格化表示了。由于int是要舍掉小数精度的,由于尾数部分是23位,而E是阶数,如果E<23的话那尾数部分是不能全部位于小数点左边的,所以要右移(23-E)(不能在小数点左边的部分)舍掉。如果>=23的,就将阶数正常乘上去(左移)即可。

最后再处理下符号,return的时候改一下就行了。另外要注意在操作尾数之前要先把尾数隐含的头部的那个1给他补上。

int floatFloat2Int(unsigned uf) {
  unsigned s,exp,frac;
  s = (uf>>31)&1;
  exp = (uf&0x7f800000)>>23;
  frac = uf&0x7fffff;
  int ans;
  int E = exp-127;

  if(E<0) return 0;
  if(E>=31) return 0x80000000u;
  ans = frac | 1<<23;
  if(E<23) ans>>=(23-E);
  else ans<<=(E-23);

  if(s) return -ans;
  else return ans;
}

13. floatPower2

题意:求$$2^x$$,要用浮点数表示。

这题难点主要在于判断各种范围。

首先浮点数的范围是$$2{-149}\ 到\ 2{127} $$,其中上界是由exp的最大值决定的,下界是由非规格数的最小值决定的。

参考图:

如果超出上界,返回无限(11110000..00),如果超出下界,返回0.

对于x<-126的情况,要拿非规格化数来表示;其他情况就拿规格化数来表示就好了。

构建规格化数,只需要改exp部分即可。非规格数就改flac部分。

unsigned floatPower2(int x) {
    if(x<-149) return 0;
    if(x>127) return 0xff<<23;
    if(x<-126) return 1<<(x+149);
    return (x+127)<<23;
}

13个小任务做完,顺利拿到满分。