Coderdiao's Homepage

Back
25 min
ics /
class /
note

ICS · Lab1 - Datalab

ICS Lab1 Datalab 回顾
Views: Loading

这篇文章是 2026秋ICS（计算机系统导论） Lab1 Datalab 回顾。虽然Lab1是ICS课程中相对难度最小的Lab，但其中充斥着的海量课上、书上没有涉及到的位运算小trick使得本Lab并没有那么简单。每次开课时Lab具体内容都会发生变化，本文在此记录2026秋季学期情况，仅供参考。

Lab1由三部分组成：Bit Manipulation（位操作）、Two’s Complement Arithmatic（补码运算）、Floating-point Operations（浮点数操作）。前两部分的操作限制非常严格，不允许条件语句或循环语句，禁止比较运算符等——几乎只支持位运算符。最后一部分要求相对宽松，上述几项均支持，但宏、函数等仍然被禁止使用。

除实现对应功能外，Lab还对每个函数的操作符总数有限制，若超过限制将影响评分。

另外，本Lab禁止使用大于 0xff 的字面量。

1. 位操作#

大多数题目对操作符的限制是：允许 ! ~ & ^ | + << >>.

1.1. bitXor#

题目要求：仅使用 ~ 和 & 实现 ^.

参数与返回值：参数为两个有符号整型 x 和 y, 返回有符号整型，即 x^y 的结果。

最大操作次数限制：14

思路：

一方面，我们可以使用离散数学中的德摩根律。另一方面，我们可以直观考虑，x^y 对应的语义是“x和y必定一真一假”，这也就是 (~x)&y|x&(~y) 。为规避 |，我们只需要把两部分分别取反后取 & 并整体取反。

代码实现：

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

1.2. leastBitPos#

题目要求：提取参数二进制表示中最低位的 1.

参数与返回值：参数为有符号整型 x。返回有符号整型，是标记最低位 1 的掩码，如果 x==0，返回 0。

最大操作次数限制：6

思路：

我们期望获得一个仅有最低有效位为 1，剩余部分全为 0 的掩码。如果逐位枚举，显然不可能在6个操作符内完成。

考虑 ~，一次 ~ 就可以将全部 0 翻转为 1。对于参数，我们假设其为如下形式：

(高位，具体内容并不重要)100000000
                      ↑
	        期望提取位
plaintext

那么经过 ~ 后，将会被翻转为：

(高位按位取反)011111111
plaintext

此时如果再 +1：

(高位按位取反)100000000
plaintext

可以看出，把这个结果与原数按位与，即得到结果。

代码实现：

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

1.3. getByte#

题目要求：提取参数某一字节（从低字节到高字节依次为0-3）。

参数与返回值：有符号整型 x 和 n 分别表示原数和需要提取的字节编号。

最大限制操作数：6

思路：

如何提取指定位置的位表示？我们自然会想到掩码。如何确定掩码的位置？由于固定提取长度是两个字节，且一定提取整字节，因此我们只需要让掩码左移到合适的字节处再按位与即可。

但我们需要返回这个字节对应的表示，而不是简单把剩下位置零，因此不如右移 x。

代码实现：

int getByte(int x, int n){
	return (x>>(n<<3))&0xff;
}
c

1.4. logicalShift#

题目要求：实现有符号整型的逻辑右移。

参数与返回值：参数 x 为有符号整型，n 为右移量，返回其逻辑右移后的值。其中 0≤n≤31.0 \le n \le 31.

最大限制操作数：16

思路：

显然我们需要右移后通过合适的掩码消除掉符号位。如何构建掩码？自然是：

以右移后的首位为界限，左侧全部为0，右侧（含本位置）全部为1。

然后把算术右移后的参数和掩码按位与就好了。

代码实现：

int logicalShift(int x, int n){
	int mask = ~(((1 << 31) >> n) << 1); // 这里不右移(n-1)位单纯是由于禁止使用-
}
c

1.5. grayToBinary#

题目要求：根据题目给出的方式返回进行前缀异或计算后的结果

前缀异或定义为：对于二进制表示 g,g, 结果 xx 满足 x[i]=g[i]^g[i+1]⋯g[MSB].x[i] = g[i] \text{\textasciicircum} g[i+1] \cdots g[MSB]. 这里MSB是最高位。

提示：32位数的前缀异或可以利用递归思想，在 log2log_2 量级的步数通过倍增左移/右移距离完成。

参数限制：被操作数 x 非负。

最大限制操作数：20

思路：

我们跟随提示的思路，考虑 x^(x>>1) 的效果。下面展示了右移后的变化

g[31] g[30] g[29] ... g[1] g[0]
0     g[31] g[30] ... g[2] g[1]
plaintext

我们注意到，操作后对于 0≤i≤31,0 \le i \le 31, 同一位上 g[i] 与 g[i-1] 进行了异或。

再考虑原来 g[31] 这一位（其实是一个符号位对应原位的示例），算术右移保障了补上的符号位必为0，如果 g[31]==1，经过异或后其依然保持；同样地，如果 g[31]==0 ，异或后也保持。

类似地，考虑将新的 x 进行 x^(x>>2) 的操作，

g[31] g[31]^g[30] g[30]^g[29] ... g[1]^g[0]
0     0           g[31]       ... g[3]^g[2]
plaintext

对于低位而言，这就达成了连续四位相异或的效果。对于高位，刚才我们已经说明，^0 并不会改变其本身。

因此只需要每次倍增右移距离并持续进行 ^= 即可。

代码实现：

int grayToBinary(int x){
	x ^= (x >> 1);
	x ^= (x >> 2);
	x ^= (x >> 4);
	x ^= (x >> 8);
	x ^= (x >> 16);
	return x;
}
c

1.6. bitCount#

题目要求：计算所给数二进制表示中 1 的个数

最大操作数限制：40

思路：

一个朴素的想法是逐位逻辑右移+和末位掩码按位与，但很显然，在40次操作的限制下，这绝对不可行。

对于枚举不可行的位运算练习题，大多数情况下都只能尝试分治了。我们考虑一个很小的情况。对于4位的二进制数，如何统计其中的 1 的个数？

如果这个问题可以分拆为两个2位数，问题便会更简单。因此我们尝试使用掩码 0101。这个掩码的作用是提取偶数位上的 1（如果我们将最低位视作第0位）。

然后我们需要将奇数位的情形也汇总进来。为此，我们只需要将原数右移一位并于源码按位与即可提取奇数位的 1 。

把这两次提取的结果相加，我们会发现，在第0+1和2+3位构成的两个两位内，两位二进制代表的值就是这两位内 1 的个数！

因此我们可以把这种做法通过改换掩码的0-1间隔为1、2、4、etc. 解决问题。

需要注意的是，Lab不允许大于 0xff 的字面量，我们只能通过位运算和按位或拼接巨大的掩码。

代码实现：

2. 补码算术#

如无特殊注明，本部分运算限制同上部分。

2.1. isEqual#

题目要求：判断两个有符号整型是否相等

参数和返回值：参数为两个有符号整型，返回值为 1，如果 x==y；为 0，如果反之。

最大操作数限制：5

思路：

不允许使用比较运算符判断相等，我们自然而然地会想到 ^。CSAPP上曾提到，^ 在布尔代数环上可以类比加法。在这个意义下，元素 a 的逆元就是其自身。

代码实现：

int isEqual(int x, int y){
	return !(x^y);
}
c

2.2. divpwr2#

题目要求：计算参数除以 2 的 n 次幂的值，特别地，要求向零舍入

参数和返回值：参数分别为原数和指数，返回计算后结果，参数范围 0≤n≤30.0 \le n \le 30.

最大操作数限制：15

思路：

既然是除以 2n2^n，很自然地可以联想到右移。但算术右移并不是向零舍入，而是单纯向下取整（高位由于符号位右移，值不变；末几位由于可能出现的 1 会直接被右移丢弃，故值更小）。

回忆CSAPP上对整型除法的处理，是通过给负数加上偏置解决的。具体地，为保证 x/y 向零舍入，对于负数，实际会计算 (x+(y-1))/y。我们可以通过带余除法证明。

此处如何在不允许使用条件语句的前提下判断符号？需要引入符号掩码的概念。也即 x>>31。由于算术右移的定义，若 x<0 则掩码全 1，否则全 0。

另外，由于本题不允许使用 -，我们需要把 -1 表示成 ~0。

代码实现：

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

2.3. sign#

题目要求：作为一个符号函数，对负值返回 -1，正值 1，0返回 0

最大操作数限制：10

思路：

直觉告诉我们，我们可以用判断是否非零+判断符号两步解决问题。

STEP1. 判断是否非零：这里有一个很经典的方式 !!n，其可以把 int 完全映射到 {0,1}\{0, 1\} 上。也就是非零时为 1，零返回 0。

STEP2. 判断符号：我们不妨利用符号掩码。注意到负数的符号掩码代表的 int 值本身就是 -1，于是我们灵机一动，使用 (x>>31)|!!x。

*注意到对于正数，全零的掩码对于按位或并不会影响 !!x 的值；对于 0，两侧均为0，并不影响。

2.4. addOK#

题目要求：检测有符号整型的相加是否会导致溢出

参数和返回值：参数为两个有符号整型，返回值为 1（表示溢出） 或 0（表示未溢出）

最大操作数限制：20

思路：

回忆有符号整型加法规则，我们知道，有符号整型加法发生溢出当且仅当结果 >Tmax 或 <Tmin。前者会回绕到负数，后者会回绕到正数。如果两个有符号整型符号异号，那么无论二者大小，都不会溢出。

因此，溢出   ⟺  \iff 两个正数相加得到负数或两个负数相加得到正数。

注意由于位运算优先级问题，我们可能需要非常多括号，不要缺少括号。

代码实现：

int addOK(int x, int y){
	return (((x>>31)^(y>>31))|(~((x>>31)^((x+y)>>31))));
}
c

2.5. absVal#

题目要求：返回输入有符号整型的绝对值

参数范围：-Tmax ≤x≤\le x \le Tmax.

最大操作数限制：10

思路：

我们需要实现的功能也即：非负数 -> 返回自身；正数 -> 返回相反数

对于有符号整型，相反数也即 (~x)+1。于是问题只剩下：如何在不允许使用条件语句的前提下进行分类？

自然的想法是借助符号掩码 x>>31。我们注意到，对非负数而言，有如下性质：x^(x>>31)==x，对于负数而言，则有如下性质：x^(x>>31)==(~x)

因此我们只需要找到一个计算方式，使得负数得到1，非负数得到0即可。(x>>31)&1 复合该要求。

代码实现：

int absVal(int x){
	return ((x^(x>>31))+((x>>31)&1));
}
c

2.6. satSub#

题目要求：对于不溢出的有符号整型减法，正常操作。对于正溢出的减法，返回 Tmax；对于负溢出的减法，返回 Tmin.

最大操作数限制：30

思路：

首先回忆有符号整型减法法则：如果两个有符号整型符号相同或有一者为0，一定不会溢出。如果二者符号不同，正数减负数得到负数或负数减正数得到正数，则表明溢出了。

我们可以首先通过符号掩码和上述规则判断是否溢出，然后具体判断是正溢出/负溢出，最后把三种可能返回情形合并。

“合并”可能有些不直观。但在这里，我们如果把所有的“标志”都设置为全 1 或全 0 的，那么可以把按位运算类比逻辑运算。因此返回值即变成了【不溢出的计算结果】或【正溢出的最小int】或【负溢出的最大int】

这里需要注意的是，由于不允许运算符 -，我们应当使用 (~y)+1 代替 -y。

代码实现：

int res=x+(~y)+1;
int msx=x>>31,msy=y>>31,msr=(res)>>31;
int int_min=1<<31,int_max=~int_min;
int overflow=msx^msr;
int pos_overflow=overflow&(~msx),neg_overflow=overflow&msx;
return (~overflow&res)|(pos_overflow&int_min)|(neg_overflow&int_max);
c

3. 浮点数#

这一部分相对最为麻烦，且题目描述也比较晦涩不明。所有题目均为使用 unsigned 代替 float 二进制表示，基于 float 原理进行操作的题目。

需要注意的是，这部分的限制宽松许多。条件语句、循环语句（虽然未必必须使用）、逻辑运算符都是允许的。

3.1. float_twice#

题目要求：计算给定浮点数乘以2的二进制表示

参数与返回值：参数为无符号整型 uf，是给定浮点数的二进制表示。返回值为无符号整型，是 *2 后的结果的二进制表示。需要注意的是，如果原数为 NaN，则直接返回。

最大操作数限制：30

思路：

处理浮点数的题目有一个十分公式化的操作，也就是通过三部分掩码分别提取符号位、指数部分和分数部分。前两者的掩码容易构造，但分数部分不太显然。这里有两种思路，其一是使用短字面量和按位或拼接，其二是利用类似于第一部分中我们提取最低有效位的思路，通过左移和恰当的加法获得合适的掩码。

然后我们回忆浮点数的三种类型并分别处理之。这主要通过指数部分进行分类。

当指数部分全 0 时，对应denormalized，我们假定分数部分的十进制值为 0.p0.p ，则这部分表示的数值是 0.p×2−126.0.p \times 2^{-126}. 因此，乘以2后，我们只需要左移1位 frac。这里需要注意，由于该情况下 exp 为0，因此直接拼接符号位和 frac 即可。

当指数部分为 0xff 时，对应special，注意无论 -inf/+inf/NaN 再进行与常数的运算都不应当发生变化，因此不需要任何操作。

当指数部分为 0xfe 时，虽然对应normalized，但这时实际值的绝对值已经位于 [2127,2128)[2^{127},2^{128}) 之间。乘以2后，全部溢出。因此返回对应符号的 inf 即可。

最后，针对不溢出的normal情形，我们不需要改动 frac 和 sign，只需要将 exp 对应方幂数 +1 即可。

这道题的返回值和参数值都是 unsigned，在 C 中，声明字面量时最好在其后加 u，明确其为 unsigned。当然，对于涉及右移操作的情形，则必须加 u。

代码实现：

unsigned float_twice(unsigned uf){
	unsigned ms=1u<<31,me=(0xffu<<23),mf=(1u<<23)+(~0u);
	unsigned sign=uf&ms,exp=uf&me,frac=uf&mf;
	if(exp==0) return sign|(frac<<1);
	if(exp==0xffu) return uf;
	if(exp==0xfeu) return sign|(0xffu<<23);
	return uf+(1u<<23);
}
c

3.2. float_f2i#

题目要求：返回浮点数强制转换为有符号整型后的值

参数与返回值：参数为无符号整型 f，返回值为有符号整型 (int)f。

如果参数为 NaN 或 -/+inf，则返回 0x80000000u。

最大操作数限制：30

思路：

回顾基本知识，我们知道 int 的取值范围是 [−231,231−1][-2^{31}, 2^{31}-1]，而 float 则是 (−2128,2128)(-2^{128},2^{128})（不准确，这里我们当然可以使用求和形式表达或者利用等比数列求和稍加化简，但仅作示意）。因此对于 exp 位对应实际权值绝对值 ≥31\ge 31 的浮点型，应当直接返回 (1<<31).

exp 位是有偏置的，对于normalized，大小为 127。经过计算可知，0x9e 对应的exp 值是 158，实际指数为 31，是上述界限。

再考虑浮点型绝对值很小的情形，根据 (int) 强制类型转换的规则，<1<1 的浮点型应当返回 0. 计算可得，0x7e 对应的实际指数是 -1，在这之下的所有数都应该返回 0。

最后考虑非平凡的normalized情形。我们首先把 frac 部分隐含的 1 拼接上来，然后分情况讨论（由于涉及左/右移）。如果实际指数 ≥23\ge 23，那么需要左移；反之右移。在返回前，还需要额外处理符号问题。前述过程已经得到对应 int 的绝对值，我们只需要对负数取负即可。

代码实现：

int float_f2i(unsigned uf){
	unsigned ms=1<<31,me=0xff<<23,mf=(1<<23)+(~0);
	unsigned sign=uf&ms,exp=uf&me,frac=uf&mf;
	unsigned ret=(1<<23)|frac,pw=exp-127;
	if(exp>=0x9e) return (1<<31);
	if(exp<=0x7e) return 0;
	if(pw>=23) ret<<=(pw-23);
	else ret>>=(23-pw);
	if(!sign) return ret;
	else return -ret;
}
c

3.3. float_negpwr2#

题目要求：返回 2−x2^{-x} 对应的二进制表示

参数和返回值：参数为 有符号 整型，返回无符号整型，为结果的二进制表示。对于denormalized，返回0；溢出，返回 +inf。

最大操作数限制：20

思路：

首先考虑返回 inf 的情形。这时有 −x≥128-x \ge 128 即 x≤−128x \le -128. 由于要求返回 +inf 故为 0xff<<23.

其次考虑返回 0 的情形。这时对应 −x≤−150-x \le -150 即 x≥150x \ge 150.（x=149  ⟺  f=0x00000001.x = 149 \iff f = 0x00000001.）

然后考虑normalized中不需要 frac 位参与的情形，也就是 x≥0x \ge 0. 这时只需要把 x 加上偏置后的值左移到 exp 位上即可。

最后考虑normalized中需要 frac 位参与的情形，也就是 x<0x < 0 时。由于 frac 位的左起第 kk 位代表 2−k2^{-k}，计算位数后左移即可。

需要注意的是，exp 位编码的权值 E 与 x 的换算关系是 E=(−x)+biasE = (-x) + bias 即 E=127−xE = 127 - x（for normalized）。

代码实现：

unsigned float_negpwr2(int x){
	int exp=127-x;
	if(x>=150) return 0;
	if(x<=-128) return (0xff<<23);
	if(x<=127) return exp<<23;
	return (1<<(149-exp));
}
c

3.4. float_greater#

题目要求：比较两个浮点型的大小，如果涉及 NaN，返回假。

参数与返回值：参数为两个无符号整型，为两个参与比较的浮点数的二进制表示；返回值为0/1，表示 x > y 为假/为真。

最大操作数限制：45

思路：

在不能类型转换的前提下，我们必须考虑分别提取三部分，然后通过合理的，运用这三部分的比较规则确定大小。

首先排除一些特殊情况：含有 NaN / inf。对于前者，直接返回 0；后者，根据 inf 是 x or y 来决定返回值。

然后，比较的优先级转化为符号 →\to 指数 →\to 分数。我们首先分类讨论符号是否相同。符号掩码按位与后全 0 的一侧一定大于全 1 的一侧。

符号相同后，我们讨论 exp 位，这就要分正/负比较。对于前者，越大越好；对于后者，越小越好。最后我们讨论前两者全相同的情形，这与 exp 位的比较类似。

当然我坚信本人使用的运算符共有36个之多的暴力方法一定有极大优化空间，不过在完成作业意义上，这并没有任何用处。

代码实现：

到这里，ICS最简单的Lab终于告一段落。笔者也正式感受到了这门声名远扬超级课程之威力。当然，也有魅力。

ICS · Lab1 - Datalab
https://cdd-2333.github.io/blog/ics-lab1-datalab
Author Coderdiao
Published at September 15, 2026
Copyright CC BY-NC-SA 4.0

离散数学基础 · 01.2 - 二元关系

数据结构与算法A · 02 - 图的最短路径