CSAPP 2e Data Lab 笔记
本文最后更新于 251 天前,其中的信息可能已经有所发展或是发生改变。

本人环境:Ubuntu 22.04 LTS amd64,GCC 11.2.0,GNU Make 4.3

前言

这是《深入理解计算机系统》的第一个Lab,要求以指定的方式完成某种计算,通过填写函数实现。

不要忘了阅读bits.c开头的Integer Coding Rules和Floating Point Coding Rules,以及每题开头的要求,它规定了使用者可以执行的操作。

用二进制的思想,而不是十进制的思想,对完成题目有很大的帮助。

本笔记离不开参考资料的支持,我特意将其放至开头:

参考资料

  1. https://github.com/Exely/CSAPP-Labs/blob/master/notes/datalab.md
  2. https://www.luogu.com.cn/blog/ACdreamer/lun-wei-yun-suan-chang-shuo-you-hua-di-sao-cao-zuo
  3. https://zhuanlan.zhihu.com/p/353348665
  4. https://blog.csdn.net/zjwreal/article/details/80925956

1. bitAnd

int bitAnd(int x, int y)
{
  // Just discrete mathematics. XY=\overline{X+Y}.
  return ~((~x) | (~y));
}

计算x&y,但只能用~|运算符。

离散数学的基础关系代数知识,由德摩根律,$XY=\overline{X+Y}$。

2. getByte

int getByte(int x, int n)
{
  int mask = 0xff;               // Leave only the last 2 bytes
  return (x >> (n << 3) & mask); // Right move 8n bits, i.e. n bytes
}

从$x$中获取第$n$位。

不要把int x当成一个整型了,直接想象它的二进制码。如果将指定位的左右两边全都去掉,这个数不就等于想要的单个位了吗?

去掉右边的数很容易,直接右移$8n$位,这样想要的部分就直接到了最低位。而要去掉多余的高位,需要让它与mask按位与,来将高位置0。

那,mask是个什么来头?先说说子网掩码:如果有两个IP地址,将它们分别与子网掩码做按位与运算,若结果相同,则这两个IP地址在同一个网段中。mask有类似的功能,具体来说,这里的mask转换为二进制是1111 1111 1111 1111,如果作为一个int类型,前24位皆为0。将这个数与任何一个int进行按位与,结果就是将前24位全部置0的原数,因为$0\&x=0$,$1\&x=x$,其中$x=0\ or\ 1$。后面我们还会使用这个设计。

3. logicalShift

int logicalShift(int x, int n)
{
  int topMask = 0x1 << (32 + ~n); // 32+~n=31-n, to get the top mask
  int lowerMask = (0x1 << (32 + ~n)) + ~0;
  return (x >> n) & (topMask | lowerMask);
}

对$x$向右进行逻辑移位$n$位。移位运算符采用的算术移位,在右移时补充的值与符号位相同,而算术移位一律补0。

像上题一样,我们可以算术移$n$位,然后使用一个掩码来让补上的部分强制置0。这里参考了参考资料1的做法,简略来说就是为了避免未定义的行为,分别构建了高位和低位的掩码。具体的可以直接看原文。

很多题目中是不允许我们使用减法的,我们可以使用取反加一的办法直接得到补码,如上面代码中$31-n=32+~n$。这个方法在下面也经常用到。

4. bitCount

int bitCount(int x)
{
  int mask = (0x55) | ((0x55) << 8); // 0x00005555
  mask = mask | (mask << 16);        // 0x55555555
  x = (x & mask) + (x >> 1 & mask);  // 2-bit sum
  mask = (0x33) | ((0x33) << 8);     // 0x00003333
  mask = mask | (mask << 16);        // 0x33333333
  x = (x & mask) + (x >> 2 & mask);  // 4-bit sum
  mask = (0x0f) | (0x0f << 8);       // 0x00000f0f
  mask = mask | (mask << 16);        // 0x0f0f0f0f
  x = (x & mask) + (x >> 4 & mask);  // 8-bit sum
  mask = (0xff) | (0xff << 16);      // 0x00ff00ff
  x = (x & mask) + (x >> 8 & mask);  // 16-bit sum
  mask = (0xff) | (0xff << 8);       // 0x0000ffff
  x = (x & mask) + (x >> 16 & mask); // 32-bit sum
  return x;
}

统计$x$所有二进制位中$1$的数目。

首先想到的是参考资料2中”2.2 统计true的数目“部分的解法,总体的思想是二分法,通过不断合并相邻两个分区的1数量,得到整体1的数量。与上面的代码不同,它直接将五个掩码写进了程序。

int popcount(unsigned int x)
{
    x=(x&0x55555555)+(x>>1&0x55555555);
    x=(x&0x33333333)+(x>>2&0x33333333);
    x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
    x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
    x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
    return x;
}

0x55555555转化为二进制,可以很容易得出它作为掩码的作用是只留下一个数中偶数位的部分(从0开始),其他置0,而函数中第一个语句的作用,就是将奇数位移到右边的偶数位上相加,并得出结果。第$n$位的值也可以看作第$n$位这个区间有多少个1,合并后。就是两位加起来有多少个1。

然后,第二行的作用是将第0-1位的1个数与第2-3位合并,以此类推,得到0-3位、4-7位,然后在第三行再进行合并……最后,将0-15位和16-31位合并,就是整个整型数的1个数。

配合下面的图可能能够更好地理解:

图源参考资料2,侵删

但是如果你想在datalab中这么填,是通不过测试的,因为十六进制常数的范围是$0x00$~$0xff$,也就是说如此大的掩码是无法直接使用的。所以,我们需要自行从两位16进制数构造8位16进制数。拿第一个mask举例:

int mask = (0x55) | ((0x55) << 8); // 0x00005555
mask = mask | (mask << 16);        // 0x55555555

2位16进制能充当8位二进制。先通过按位与和左移8位(二进制)的操作,生成低4位十六进制,然后再通过左移和按位与的操作,将其复制到高4位一份。这样,掩码就构建好了。如将其压缩到一句中,分别给予左移24、16、8、0位,则运算符数量会超过限制。

5. bang

int bang(int x)
{
  x = (x >> 16) | x;
  x = (x >> 8) | x;
  x = (x >> 4) | x;
  x = (x >> 2) | x;
  x = (x >> 1) | x;
  return ~x & 0x1;
}

在不使用$!$的情况下计算非$x$。

非运算表现为,如果$x$不为0,则结果为1,否则结果为0。也就是说,只要有任何一个二进制位为1,取非得到的结果就是0,那么我们就可以将$x$的所有位“压缩“到第0位。如果$x$中含有1,那么第0位就会是1。

最后一个语句是将$x$按位取反,然后只留最后一位。这样返回的就是取非的结果了。

6. tmin

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

返回补码的最小值。

int型能表示的最大正数是$2^{31}-1$,而$2^{31}$可以故意让其上溢出,就可以得到补码的最小值了。

7. fitsBits

int fitsBits(int x, int n)
{
  int moveBits = 33 + ~n;                   // Equals to 32-n
  int result = (x << moveBits) >> moveBits; // Left move, and then right move
  return !(x ^ result);                     // If okay, result should be equal to x
}

如果$x$能够用$n$位补码表示,返回1。

如果你使用新版本Linux,可能会导致无法通过btest测试,换别人的正解代码也一样。如果遇到此问题,请使用老版本,实测Ubuntu 12.04 LTS(Linux 3.10)可用。此处的不同可能与下面的汇编代码不同有关:

既然题目想知道$x$能否用$n$位补码表示,那么就创造一个$n$位补码的环境。具体地来讲,就是向左移,直到从第31位到原数最低位就是$n$位。

如果这个数并不能用$n$位补码表示,那么原数字的高位就会被“挤掉”,而这样的数再右移,无法再恢复被挤掉的数字。如果能如此表示,那么这个数本身并不会受到任何损失;算术右移同样位数之后,就可以恢复原来的状态。

最后再将其与原数异或取反,就可以得到结果。

8. divpwr2

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

返回$x/2^n$,向零舍入。

右移运算会向下舍入,而题目要求负数向上舍入。CSAPP书中的解决方法是为负数添加一个bias(偏置)值$2^k-1$,这样右移的时候就可以向上舍入了。x>>31正是为了判断正负,提取了符号位。

9. negate

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

返回$-x$。

计算补码,取反加一。

10. isPositive

int isPositive(int x)
{
  return !(!(x)) & !((x >> 31) & 1);
}

如果$x$是一个正数,返回1。

正数的符号位是0,但符号位是0的也可能是0。内部先判断”是否$x \le 0$“,然后取非,就得到了是否为正数。

11. isLessOrEqual

int isLessOrEqual(int x, int y)
{
  int val = ((x + ~y) >> 31) & 1;
  x = x >> 31;
  y = y >> 31;
  return ((x & 1) | !y) & (((x & 1) & !y) | (val));
}

val取的是$x-y-1$的符号位,如果$x>y$才会为0(因为整型,$x \ge y+1$),否则为1。1是掩码,防止为负时右移补出来一堆不需要的1。

然后是取x和y的符号位,掩不掩都行。

最后还要判断溢出的情况,如果$x<0,\ y>0$则直接返回1。

12. ilog2

int ilog2(int x)
{
  int mask;

  x = (x >> 1) | x;
  x = (x >> 2) | x;
  x = (x >> 4) | x;
  x = (x >> 8) | x;
  x = (x >> 16) | x;

  mask = (0x55) | ((0x55) << 8);     // 0x00005555
  mask = mask | (mask << 16);        // 0x55555555
  x = (x & mask) + (x >> 1 & mask);  // 2-bit sum
  mask = (0x33) | ((0x33) << 8);     // 0x00003333
  mask = mask | (mask << 16);        // 0x33333333
  x = (x & mask) + (x >> 2 & mask);  // 4-bit sum
  mask = (0x0f) | (0x0f << 8);       // 0x00000f0f
  mask = mask | (mask << 16);        // 0x0f0f0f0f
  x = (x & mask) + (x >> 4 & mask);  // 8-bit sum
  mask = (0xff) | (0xff << 16);      // 0x00ff00ff
  x = (x & mask) + (x >> 8 & mask);  // 16-bit sum
  mask = (0xff) | (0xff << 8);       // 0x0000ffff
  x = (x & mask) + (x >> 16 & mask); // 32-bit sum
  return x + ~0;
}

求$log_2x$向下取整的值。

借鉴了参考资料3的做法,思路更加清晰,容易理解。首先我们知道,一个数以二进制表示,最高1位所对应的2的次方,就是$log_2x$向下取整的值。举个例子来说,$(45)_{10}=(101101)_2=(1 \times 2^5+0 \times 2^4+1 \times 2^3+1 \times 2^2+0 \times 2^1+1 \times 2^0)_{10}$,那么就有$log_2 45 = log_2 32 + log_2 \frac{45}{32}=5+x$,其中x肯定是一个小于1的数。那么,一个可行的思路就是找到最高位的1是第几位减一,但直接逐位右移再判断并不是可行的方法,因为较低位也可能为0,可能统计不到真正的最高位就以为是最高位了。所以,我们先把非最高位全都设成1,然后再统计1的个数即可。

先是类似于第5题 “Bang”的做法,将高位“折”下来。与第五题不同,这里移动的位数从低到高,因为先移16位的话,并不能保证高16位中能够正确地设1;相反的,第5题使用这种顺序则是可以的。

然后是第4题“bitCount”的做法,统计有多少个1,就可以得知最高位的1是第几位(从1开始计)。不过,由于第1位代表$2^0$,最后还要将结果减一。


以下三道题全都是浮点数的题了。虽然参数看似并不是浮点数类型,但是二进制表示上,仍然是一个浮点数。某种程度上,这也是在鼓励学习者用二进制的方式思考问题。这三道题相比之前的限制条件更少,比如运算符都可以用了,还可以使用条件和循环控制语句。

13. float_neg

unsigned float_neg(unsigned uf)
{
  int c = 0x00ffffff;
  if ((~(uf << 1)) < c)
  {
    return uf;
  }
  else
  {
    return uf ^ (0x80000000);
  }
}

本题要求返回参数的相反数。如果参数是INF,则返回参数本身。

难度主要在判断INF上。INF的特征是指数域全为1,尾数域不全为0。一个可行的思路是通过比较指数域和尾数域的大小来区分是否为INF,但符号位会干扰比较,虽然理论上可以使用四个端点值分别比较大小得出结论,但未免有点不优雅。所以,这里向左移一位把符号位去掉,取反,然后和c比较大小。现在,前8位是取反的指数域,后23位是取反的尾数域,最后一位是左移补上的0。如果它是NaN,则此时前4位必然是0,后24位必然小于0xffffff(或者0xfffffe)。这样,只需要一次比较就可以搞定,非常优雅(确信)。

否则,就将最高位也就是符号位与1异或,就相当于取反了。

14. float_i2f

unsigned float_i2f(int x)
{
  int sign, exp = 0, frac = 0, i = 0;

  if (x == 0) // Two special situations, cannot be calculated normally
  {
    return 0;
  }
  if (x == 0x80000000)
  {
    return 0xcf000000;
  }

  sign = (x >> 31) & 1; // Get the sign bit & abs(x)
  if (sign)
  {
    x = -x;
  }

  i = 30; // Not 31 coz the top bit is always 0
  while (!(x >> i))
  {
    i--;
  }
  exp = i + 127; // Get the exponent. i is the E, unbiased

  x = x << (31 - i);          // Left shift to clean zeroes, right shift to fit 23 bits...
  frac = (x >> 8) & 0x7fffff; // ...to get the fraction
  x = x & 0xff;
  frac += (x > 0x80) || ((x == 0x80) && (frac & 0x01)); // Round up if fraction is greater than 0.5
  if (frac >> 23)
  {
    exp++;
    frac = frac & 0x7fffff;
  }
  return (sign << 31) | (exp << 23) | frac;
}

将一个整形转化为浮点数格式。

建议直接看参考资料4

15. float_twice

unsigned float_twice(unsigned uf)
{
  int uf_nosign;
  int sign = uf & 0x80000000;   // sign bit
  int exp = uf & 0x7f800000;    // exponent bits
  int fraction = uf & 0x7fffff; // fraction bits
  uf_nosign = uf & 0x7fffffff;  // remove sign
  if ((uf_nosign >> 23) == 0x0) // denormalized condition
  {
    uf_nosign = uf_nosign << 1 | sign;
    return uf_nosign;
  }
  if ((uf_nosign >> 23) == 0xff) // special numbers (NaN and infty)
  {
    return uf;
  }
  // if ((exp >> 23) + 1 == 0xff)
  if (exp == 0x7f000000) // exponent overflow
  {
    return sign | 0x7f800000;
  }
  // return sign | (((exp >> 23) + 1) << 23) | fraction;
  return sign | (exp + 0x800000) | fraction;
}

要求将浮点数uf乘2。如果为NaN,返回原参数。

使用了参考资料1的做法,进行了一定的优化。首先,使用不同的掩码将符号、指数域和尾数域分别取出来。然后单独算出没有符号位的$uf$,存到uf_nosign中。

第一个if语句判断的是指数域全为0的情况(需要右移23位,因为去掉尾数域之后仍然用0占位),也就是非规格化值。此时只需要将去掉符号位的uf左移一位,然后加上符号位(按位与),就可以得到想要的数。因为指数域全为0,所以即使尾数域左移导致溢出,也会表现为指数域+1而无其他危险后果,而这恰是我们想要的结果。

第二个if语句判断的是特殊值的情况。如果是NaN,直接返回uf肯定没问题,正如题目所说;如果是无限大,那么它的两倍还是无限,还是应该返回原数。

规格化的话,大体思路就是将指数域+1。第三个if语句判断的是指数域溢出的情况。因为单精度指数域只有8位,所以如果指数域+1已经是$0xff$了,就不再表示一个正常的数了(变成特殊值)。

最后,排除了所有特殊情况,就是正常的规格化值,将阶码+1,拼上符号位和尾数就可以了。

有一些运算上的简化,通过预先的运算可以节省运算符的使用量,和上方被注释掉的语句是等效的,如果不能理解,可以看被注释的语句。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇