首页 > 其他分享 >CSAPP Lab-1 DATALAB

CSAPP Lab-1 DATALAB

时间:2024-04-24 13:36:30浏览次数:25  
标签:CSAPP return 题意 int DATALAB Lab 运算符 uf 操作数

本文原发于 2023-09-02 15:32:57 于我的 hexo 博客,现迁移至此。

最近看完了 CSAPP 整本书,发现官网上还有 11 次实验可以做。

UPD:好像只有 9 个,因为有两个是旧版本的,可以被新版的替代掉。

UPD:好像只有 8 个,performance 也算是旧的实验了,但是没有明确指出。

Lab 地址:http://csapp.cs.cmu.edu/3e/labs.html

bitXor(x,y)

题意

任务:\(x\) 异或 \(y\)(x ^ y

允许使用的运算符:~ &

操作数限制:\(14\)

Solution

对于每一位分别考虑。假设 \(P, Q\) 分别是 \(x, y\) 的某一个对应位,那么这一位上的异或和就是

\[\begin{aligned} P \oplus Q &= \overline{P}Q + P\overline{Q}\\ &= \overline{\overline{\overline{P}Q}\ \overline{P\overline{Q}}} \end{aligned} \]

Code

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

共 \(8\) 次操作。

tmin()

题意

任务:二进制补码下最小的 int 类型的数

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(4\)

Solution

这个题目非常简单,答案就是 \(-2^{31}\),在 int 补码下是 \(1\) 后面接 \(31\) 个零,只有最高位为 \(1\),也就是 1 << 31

Code

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

共 \(1\) 次操作。

isTmax(x)

题意

任务:判断 \(x\) 是不是补码表示下最大的 int 类型数。

允许使用的运算符:! ~ & ^ | +

操作数限制:\(10\)

Solution

我的做法比较奇怪吧。

最大的 int 类型数也就是 \(2^{31} - 1\)(0x7fffffff)。

如果 \(x\) 满足要求,那么 \(x+1\) 就是 \(-2^{32}\)(0x80000000),等于 ~x。可以使用 ~((x + 1) ^ x) = 0 来判断。

但是需要注意的是,\(-1\)(0xffffffff)也满足这个性质,因此需要特判这种情况。可以使用 !(x + 1) = 1 来判断。

因此综合起来,用 \(a\) 表示 \(x+1\),最后的答案就是 !((~(a ^ x)) | !a)

Code

int isTmax(int x) {
  int a = x + 1;
  return !((~(a ^ x)) | !a);
}

共 \(6\) 次操作。

allOddBits(x)

题意

任务:判断 \(x\) 的奇数位是否都是 \(1\)。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(12\)

Solution

这题难住了我不短的时间。

其实是一开始没有想到直接构造出所有奇数位的掩码。

题目限制只能使用 \(0\) 和 \(255\) 之间的整数,所以可以使用 0xAA10101010)扩展两次得到 \(32\) 位的奇数位掩码。

假设 a = 0xAA,那么使用 (a << 8) + a 即可得到 \(16\) 位奇数位掩码,将结果存进 \(a\) 中,再使用 msk = (a << 16) + a 即可得到完整 \(32\) 位的掩码。

使用 x & msk 就是 \(x\) 所有奇数位,使用 ^ 与 \(msk\) 进行对比,异或结果为 \(0\) 说明相同,再取非即可得到答案。

Code

int allOddBits(int x) {
  int msk = (0xAA << 8) + 0xAA;
  msk = (msk << 16) + msk;
  return !((x & msk) ^ msk);
}

共 \(7\) 次操作。

negate(x)

题意

任务:返回 \(-x\) 的补码。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(5\)

Solution

经典问题,答案就是取反再加 \(1\),也就是 \((~x) + 1\),不解释。

Code

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

共 \(2\) 次操作。

isAsciDigit(x)

题意

任务:判断 \(x\) 对应的 ASCII 码是不是数字字符(也就是 0x30 到 0x39` 之间)。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(15\)

题解

首先判断高 \(28\) 位是不是 0x3。使用 !((x >> 4) ^ 3 判断。

然后判断低 \(4\) 位是不是 1001 及以下。考虑到不合法的分别有 1010, 1011, 1100, 1110, 1111 这些数,满足第 \(3\) 位(最低位为第 \(0\) 位)为 \(1\),且第 \(2, 3\) 位至少有一位为 \(1\)。只要这两个条件有一个不满足就可以认为合法。

第 \(3\) 位不为 \(1\) 可以用 !(x & 8) 判断。

第 \(2, 3\) 位不存在一位为 \(1\) 可以用 !(x & 6) 判断(6 = 0110)。

Code

int isAsciiDigit(int x) {
  int pre = !((x >> 4) ^ 3);
  return pre & (!(x & 8) | !(x & 6));
}

共 \(9\) 次操作。

conditional(x, y, z)

题意

任务:返回 C 语言 x ? y : z 的结果。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(16\)

Solution

假设我们可以把 \(x\) 扩展成一个 \(k\),满足如果 \(x\) 为真,那么 k = 111...1,否则 \(k = 000...0\),那么我们可以把答案表示成 (k & y) | ((~k) & z)

考虑怎么扩展。我们可以用 \(!x\) 得到 \(x\) 的逻辑值的非,只有末位可能为 \(1\),高位全部为 \(0\),作为初始的 \(k\),然后倍增构造。

使用 k = (k << 1) | k 构造两位版本,然后 k = (k << 2) | k 构造四位,以此类推,即可得到完整的 \(k\)。

当然,最后得到的 \(k\) 与我们之前假设的相反,为 !x 的扩展,因此答案表达式也需要稍作改变。

Code

int conditional(int x, int y, int z) {
  int k = !x;
  k = k | (k << 1);
  k = k | (k << 2);
  k = k | (k << 4);
  k = k | (k << 8);
  k = k | (k << 16);
  return ((~k) & y) | (k & z);
}

共 \(15\) 次操作。

isLessOrEqual(x, y)

题意

任务:判断 int 类型下 \(x\) 是否小于等于 \(y\)。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(24\)

Solution

一般来说,只需要判断 \(x - y\) 的正负性即可。\(x - y\) 可以使用 \(x\) 加上 \(-y\) 的补码得到,也就是 x + (~y) + 1。如果 \(x - y = 0\) 需要特殊判断。

但是,如果 \(x - y\) 发生溢出,那么这样判断就会不准确了。因此我们可以先判断 \(x, y\) 各自的符号,只有在同号的时候我们才判断 \(x-y\)。如果 \(x, y\) 符号位不同,可以直接判断结果。

一个数的符号位可以通过 (x >> 31) & 1 获得。

具体地,假设 \(z = x - y\),nx, ny, nz 分别为 \(x, y, z\) 的符号位,f1 表示 \(x - y = 0\) 的逻辑值。那么如果 \(f1\) 为真,或者 \(x\) 负 \(y\) 正(nx & !ny)答案就是 1,此外,除非 nxny 相同(nx ^ !ny)才会需要 \(z\) 的符号位。

结果就是 f1 | (nx & !ny) | ((nx ^ !ny) & z),其中 !ny 重复使用,可以增加一个中间变量来节省操作数。

Code

int isLessOrEqual(int x, int y) {
  int nx = (x >> 31) & 1;
  int ny = (y >> 31) & 1;
  int nny = !ny;
  int z = x + (~y) + 1;
  int f1 = !z;
  z = (z >> 31) & 1;
  return f1 | (nx & nny) | ((nx ^ nny) & z);
}

共 \(16\) 次操作。

logicalNeg(x)

题意

任务:使用逻辑非,即 !x

允许使用的运算符:~ & ^ | + << >>

操作数限制:\(12\)

Solution

和之前 conditional 这个题中构造 \(k\) 的过程很相似,不是要反过来做。

每次我们把 \(x\) 高位的一半和低位的一半做按位或(|),然后假装 \(x\) 少了一半位,那么当 \(x\) 只剩一位的时候,\(x\) 就是所有位的或了。

那么只需要将末位取出,然后 ^ 1 构造出非。

Code

int logicalNeg(int x) {
  x = (x >> 16) | x;
  x = (x >> 8) | x;
  x = (x >> 4) | x;
  x = (x >> 2) | x;
  x = (x >> 1) | x;
  return (x & 1) ^ 1;
}

共 \(12\) 次操作。

howManyBits(x)

题意

任务:返回补码形式下,表达 \(x\) 最少需要多少位。

允许使用的运算符:! ~ & ^ | + << >>

操作数限制:\(90\)

Solution

愣是读题读了半天才理解……这里说的补码形式是,一个二进制串最高位为符号位,剩下的使用补码构造。

那么如果 \(x\) 是负数,我们将之取反,得到的结果不变。

然后我们只需要找到最高的一个 \(1\) 的位置,倍增统计即可。

具体地,假设 \(x\) 现在是 \(32\) 位,我们取出最高的 \(16\) 位,判断是否全是 \(0\),如果是的话就将 \(x\) 设置为低 \(16\) 位,否则将答案加上 \(16\) 然后将 \(x\) 设置为高 \(16\) 位。

位数折半,重复以上过程直到最后一位做完。

答案再上加 \(1\) 的符号位即可。

Code

int howManyBits(int x) {
  int f, p;
  int ans = 0;
  int s = x >> 31;
  x = (~s & x) | (s & ~x);
  f = !!(x >> 16), p = f << 4;
  ans = ans + p, x = x >> p;
  f = !!(x >> 8), p = f << 3;
  ans = ans + p, x = x >> p;
  f = !!(x >> 4), p = f << 2;
  ans = ans + p, x = x >> p;
  f = !!(x >> 2), p = f << 1;
  ans = ans + p, x = x >> p;
  f = !!(x >> 1), p = f;
  ans = ans + p, x = x >> p;
  f = x, p = f;
  ans = ans + p + 1;
  return ans;
}

共 \(37\) 次操作。

floatScale2(uf)

题意

任务:以 unsigned 类型给出一个 \(32\) 位浮点数 \(uf\) 的位级表示,求出 \(uf \cdot 2\) 的位级表示。

允许使用的运算符:所有整数操作符,包括 &&, ||if, while

操作数限制:\(30\)

Solution

首先用下面的代码求出符号、尾数和阶码。

int s = uf & (1 << 31);
int f = uf & 0x7fffff;
int e = (uf >> 23) & 0xFF;

如果为特殊值(无穷大和 NaN),那么保持不变返回即可。

如果为非规格数,uf << 1 即可得到符号位之外的正确结果(如果尾数部分溢出了会刚好溢出到阶码中),接上符号位即可得到答案。

如果为规格数,那么将阶码 \(+1\),如果阶码变成了 0xFF,答案就是无穷大,否则将符号、新的阶码和尾数拼接即可。

Code

unsigned floatScale2(unsigned uf) {
  int s = uf & (1 << 31);
  int f = uf & 0x7fffff;
  int e = (uf >> 23) & 0xFF;
  if (e == 0xFF) return uf;
  if (e == 0) return (uf << 1) | s;
  ++e;
  if (e == 0xFF) return s | 0x7f800000;
  return s | (e << 23) | f;
}

共 \(14\) 次操作。

floatFloat2Int(uf)

题意

任务:以 unsigned 类型给出一个 \(32\) 位浮点数 \(uf\) 的位级表示,求出 (int)uf 的结果。

允许使用的运算符:所有整数操作符,包括 &&, ||if, while

操作数限制:\(30\)

Solution

将阶码 \(- 127\) 得到真正的指数 e

如果 \(e < 0\),那么说明 \(|uf| < 1\),答案是 \(0\)。

如果 \(e \geq 31\),那么说明 \(|uf| \geq 2^{31}\),超过了 int 的表示范围,返回题目要求的 0x80000000u。(ps:不用特判 \(uf = -2^{31}\) 的情况,因为 0x80000000u 刚好就是对应的值)

否则,我们取出尾数,再在最前面加上一个 \(1\)(浮点表示法中被省略的 \(1\)),就是尾数表示的值乘上 \(2^{23}\)。根据浮点数的结构,依据 \(e\) 和 \(23\) 的大小将尾数左右移即可。如果 \(e \geq 23\),那么将尾数左移 \(e - 23\) 位,否则右移 \(23 - e\) 位。

Code

int floatFloat2Int(unsigned uf) {
  int s = uf & (1 << 31);
  int f = (uf & 0x7fffff) | 0x800000;
  int e = ((uf >> 23) & 0xFF) - 127;
  if (e < 0) return 0;
  if (e >= 31) return 0x80000000u;
  if (e >= 23) f <<= e - 23;
  else f >>= 23 - e;
  if (s) f = -f;
  return f;
}

共 \(15\) 次操作。

floatPower2(x)

题意

任务:\(2^x\) 的浮点数位级表示。

允许使用的运算符:所有整数操作符,包括 &&, ||if, while

操作数限制:\(30\)

Solution

浮点数阶码的表示范围是 \(-126\) 到 \(127\)。

如果 \(x > 127\),那么答案就是无穷大。

否则,如果 \(x \geq -126\),那么可以用规格数表示,将 \(x + 127\) 嵌进 \(23\) 到 \(30\) 位上即可((x + 127) << 23)。

否则,如果 \(x \geq -126 - 23 = -149\),那么 \(x\) 可以用非规格数表示,因为非规格数尾数部分第 \(i\) 位表示 \(2^{i - 23} \times 2^{-126}\),因此答案就是 1 << (x + 149)

否则无法表示,返回 \(0\)。

Code

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

共 \(9\) 次操作。

ps:这个问题测试数据好像特别多,在时间限制内评测不完,需要在 btest.c 中将 TIMEOUT_LIMIT 宏改大一些,比如 \(20\)。

标签:CSAPP,return,题意,int,DATALAB,Lab,运算符,uf,操作数
From: https://www.cnblogs.com/hankeke303/p/18155069/csapp-datalab

相关文章

  • CSAPP Lab-3 ATTACKLAB
    书接上回,这次做到了第三个Lab啦。任务描述这一个Lab的任务就更有意思了,实验给了我们两个程序,每个程序都会让我们输入一行字符串,而它们是通过下面这个函数来读取的:unsignedgetbuf(){ charbuf[BUFFER_SIZE]; Gets(buf); return1;}其中,Gets函数和C库的gets函数......
  • CSAPP Lab-4 Architecture Lab
    本次实验是有关书上第四章设计的Y86-64处理器的,实验分为三个部分,分别是编写几个简单的Y86-64程序、使用一条新指令扩展SEQ模拟器以及优化Y86-64的基准测试程序和处理器设计。实验准备需要简单复习一下Y86-64的指令集架构以及处理器架构呢。指令集架构指令集:指令功......
  • CSAPP Lab5 Cache Lab
    到实验5啦!这次的实验是有关高速缓存的。让我们先来复习一下高速缓存的基础知识吧!复习高速缓存的结构在一个存储器地址有\(m\)位的系统上,一共有\(M=2^m\)个地址。假设高速缓存被组织成一个有\(S=2^s\)个高速缓存组的数组,其中每个组包括\(E\)个高速缓存行,每行存......
  • CSAPP Lab6 Shell Lab
    本次实验的任务很清晰,实现一个简单的UnixShell。需要用到基础的进程控制、信号处理等知识。简单来说,实验已经提供了一些简单的功能,我们需要在此基础上,实现下面的功能:eval:解析和解释命令行的主例程。[70行]builtin_cmd:识别并解释内置命令quit(退出)、fg(前台运行某个作业)、bg(后......
  • CSAPP Lab-2 BOMBLAB
    第二个Lab就比较有趣了。这一个Lab的任务是,我们得到了一个bomb炸弹程序,这个炸弹程序有\(6\)个phase,每个phase都会读取我们的输入,判断我们的输入是否符合要求,如果正确这个phase的炸弹就会被拆除,否则炸弹就会爆炸。我们需要借助各种工具,对程序进行反汇编等等,获得能够......
  • 伯克利大学 CS61B Lab配置教程
    基本过程:首先将伯克利大学的代码框架下载到自己的电脑,然后我们直接在框架里修改就行将自己的代码上传到github上,然后使用伯克利大学的Gradescope评测自己写的代码下载代码在自己电脑桌面新建一个文件夹,这里我命名为:cs61b,打开gitbash,使用cd进入我们新创建的文件夹,注意路径......
  • 读《我和Labview》5条件结构和顺序结构
    5条件结构和顺序结构条件结构布尔类型条件选择结构其它数据类型的条件选择是否要设置默认分支?合理设置悬着条件隧道避免把控件放在条件结构内选择函数顺序结构程序执行顺序创建顺序结构层叠式顺序结构平铺式顺序结构无形胜有形的最高境界6用户自定义控件7控件的局......
  • Linux服务器中Docker部署的GitLab镜像访问出现500错误
    一背景这几天发现在Linux服务器中Docker部署的GitLab镜像访问出现500错误,在重启服务器后大概10分钟再次出现该情况,后面登录服务器一步步排查最终解决问题,现在将解决问题的过程做一个总结。二过程分析首先第一步就是看看我们Docker目录下文件占用的情况,因为我们的Linux服务......
  • 如何将Docker中GitLab数据备份到宿主Linux上
    一宿主机准备存放备份文件的目录建议以年月日进行命名使用putty.exe或者PowerShell登录远程服务器cdshare(如果没有当前目录请创建该共享目录)mkdir20220930(在共享目录下创建备份文件夹)二进入Docker容器内部备份数据1.执行命令sudodockerexec-itgitlab/bin/......
  • feign调用接口报错No qualifying bean of type '***HttpMessageConverters' available
    在整合springcloudgeateway时,调用了feign接口,报错Noqualifyingbeanoftype'org.springframework.boot.autoconfigure.http.HttpMessageConverters'available报错信息feign.codec.EncodeException:Noqualifyingbeanoftype'org.springframework.boot.autocon......