Lab 1: Data Lab

使用 C 语言，在限定条件下，在 bits.c 文件中实现下列函数：

（每一题的具体要求可以参考 bits.c 注释内容）

Func Name	Description	Max Ops Allowed
bitXor(x,y)	仅用 `&` 和 `~` 实现 `x xor y`	14
tmin()	返回最小的二进制补码整数	4
isTmax(x)	判断 `x` 是否为最大的二进制补码整数	10
allOddBits(x)	判断 `x` 的所有奇数位是否均为 1	12
negate(x)	不使用 `-` 运算符返回 `-x`	5
isAsciiDigit(x)	判断 `x` 是否为 ASCII 数字（`0x30 ≤ x ≤ 0x39`）	15
conditional(x,y,z)	实现 `x ? y : z` 的功能	16
isLessOrEqual(x, y)	判断 `x` 是否小于等于 `y`	24
logicalNeg(x)	不使用 `!` 运算符实现 `!x`	12
howManyBits(x)	返回表示 `x` 所需的最小位数	90
floatScale2(uf)	返回与表达式 `2 * f` 等价的二进制位表示	30
floatFloat2Int(uf)	将浮点数转换为整数	30
floatPower2(x)	返回与表达式 `2.0 ^ x` 等价的二进制位表示	30

Solution

仅用 & 和 ~ 实现 x ^ y

对 xor 式子进行变换，第一步拆开 xor 表达式为和或非形式，第二步使用德摩根律消去 | 运算

x ^ y = ~( (~ (~x & y)) & (~ (x & ~y)) )

code:

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

返回最小的二进制补码整数

要求中提到：整数常量只能设置在 0 到 255（ 0xff ），不允许使用更大的常量（如 0xffffffff）

我们知道最小的二进制补码整数是 10000000 00000000 00000000 00000000 （题设使用 32 位二进制补码表示整数），可以选择将 10000000 左移 24 位实现

code:

int tmin(void) {
	return 0x80 << 24;
}

判断 x 是否为最大的二进制补码整数

不能使用控制函数，所以不能 if

我们知道最大的二进制补码整数是 01111111 11111111 11111111 11111111 ，这个数有一个特性： +1 操作与取反操作得到相同的值。

总共有两个数符合这样的特性： Tmax 与 -1 ，所以我们先通过 !( (x+1) ^ (~x) ) 排除掉其他值，再通过 !(!(~x)) 操作排除 -1 这个值（只有 -1 取反后为 0）

当然，直接构造出 0x80000000，利用异或性质得到答案是更加简洁的选择，但是第一个函数不依赖 int 在不同环境下的位数限制，具有更好的可移植性；而第二个函数的 0x80<<24 操作只针对于 32 位 int （并且这一题禁止了移位操作，所以后者得不到分）

Note

! 的关键之处在于，它可以将所有非零数统一设置为 0，在没有 if == 操作的情况下，这很实用

判断 a,b 是否相等的一个简单操作是： !(a^b) ，相等值为 1，否则值为 0

code:

int isTmax(int x) {
	return !( (x+1) ^ (~x) ) & !(!(~x));
}

判断 x 的所有奇数位是否均为 1

也就是判断一个数和掩码 01010101 01010101 01010101 01010101 的按位或结果是否为 0xffffffff ，如果是，取反后就能得到 0，利用 ! 操作就能解答

code:

int allOddBits(int x) {
	int y = 0x55 + (0x55 << 8);
	int z = y + (y << 16);
	return !( ~(x | z) );
}

不使用 - 运算符返回 -x

对于补码数，取负操作等价为 “按位取反 + 1” ，据此给出解答

Note

取负操作 -x 的定义是使 x+(-x) 在模 $2^n$ 运算下为 0，$n$ 是数据长度

不难得到 $x+(\sim x + 1) = 2^n \equiv 0 \pmod {2^n}$

code:

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

判断 x 是否为 ASCII 数字（0x30 ≤ x ≤ 0x39）

首先得从 0x30 ~ 0x39 这几个二进制数的性质入手，这些数的二进制都满足右八位为 0011xxxx，且 xxxx 部分只能对应十六进制 0~9 （具体来说是满足 0xxx（0~~7）或者 100x（8~~9）格式的值）

总结一下就是这个数 x 必须能与 00110xxx 与 0011100x 中的某一项匹配。对于匹配 00110xxx，我们可以先将 x 右移三位，然后与 00110 进行比较（ 0011100x 同理）

code:

int isAsciiDigit(int x) {
	return !( (x >> 3) ^ (0x06) ) | !( (x >> 1) ^ (0x1c) );
}

实现三目运算符 x ? y : z 的功能

等价于：if(x != 0) {return y;} else {return z;}

注意到对任意 32 位整数 a， 0 & a == 0 且 0xffffffff & a == a ，我希望构造一个函数 f(x) ，满足 x==0 时 f(x) == 0；x != 0 时 f(x) == 0xffffffff ，这样的话我就可以通过这个函数构造三目运算符，大致原理是：

return f(x) & y | ~f(x) & z

考虑 !x 操作只会将 x 变为 0 或 1 ，而这两个数减去一恰好对应 0xffffffff 与 0 ，这就解决了构造函数的问题：f(x) = (!x) - 1 （题目要求只能用加号，所以这里还需要构造 -1 ）

code:

int conditional(int x, int y, int z) {
	int c = !x + (~0);					// 也可以写成 ~(!!x) + 1
	return (c & y) | (~c & z);
}

判断 x 是否小于等于 y

如果 x <= y 返回 1，否则返回 0

容易发现： x <= y 有两种情况：x 负 y 非负；或者 x y 同正负且满足 y-x 符号位为 0

return ( (x,y 同号) & !((y-x) >> 31) ) | (x负且y非负)

Note

为什么要加上对 x y 符号的讨论？

防止溢出情况改变了符号位

~~另外我写不出来可移植性好的函数（能同时适用于 32 位和 64 位的函数）~~

code:

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

不使用 ! 运算符实现 !x

! 的运算解释：如果 x 非零，则 !x = 0，否则 x == 0 → !x = 1

注意到对于任意非零数 x ，x 与 -x 总有一个符号位为 1，而 x == 0 时 x == -x == 0，符号位为 0 ，根据这个符号位差异就可以写出函数

Note

C 语言对于有符号数采用算术右移，所以 x != 0 时右移 31 位结果为 -1

code:

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

返回能完整表示 `x` 所需的最小位数

/*  Examples: howManyBits(12) = 5					(0 1100)
 *            howManyBits(298) = 10					(0 100101010)
 *            howManyBits(-5) = 4					(1 011)
 *            howManyBits(0)  = 1					(0)
 *            howManyBits(-1) = 1					(1)
 *            howManyBits(0x80000000) = 32			(1 + 31*0)
 */

int 部分题目的最难题，甚至给了最多 90 步的限制，是场恶战

首先 x 的值为 0 和 -1 都是特殊情况（只需要符号位表示），先留意一下

对于一般情况，如果 x 是正数，那么关键目的是要尝试找到最高有效位（该位为 1 ，其左侧全为 0 ），最小位数 = 最高有效位 + 一位符号位

如果 x 是负数，不能直接用上面的方案找最高有效位，因为补码额外有一个值为 1 的符号位，使得最终结果比正确结果多出一，因此必须先取绝对值化。这里可以选择对 x 取反，~x 和 x 的所需最小位数是相同的（比如 1011 取反后为 0100 ，所需最小位数都是 4 位），注意 -1 是特例。

如何判断一个数是不是负数？检查符号位：

int sign = x >> 31;
x = (sign & ~x) | (~sign & x);	// 这里是三目运算符的一个运用

统一了 x 的正负性之后，符号位不再影响最高有效位的寻找。这里考虑二分查找找到最高有效位，下面是伪代码：

int Max = 0; 					// 记录最高有效位的数值
if (x 的高 16 位全为零){
	x = x << 16 >> 16;			// 只保留低 16 位，因为高 16 位已经没有信息提供了
}
else {							// 也就是说最高有效位出现在高 16 位中
	x = x >> 16;				// 把高 16 位当作低 16 位储存
	Max = Max + 16;				// 后 16 位都贡献了最高有效位
}

if (x 的高 8 位全为零){			// 对剩下的部分继续二分寻找
	x = x << 8 >> 8;
}
else {
	x = x >> 8;
	Max = Max + 8;
}

// 此处省略一部分查找过程

if (x 的高 1 位为零) {
	x = x << 1 >> 1;
}
else {
	x = x >> 1;
	Max = Max + 1;
}

Max = Max + (x != 0);			// 最后计算剩下的一位的贡献

现在我们需要考虑如何实现上面的伪代码，我们聚焦于这一部分内容的实现：

if (x 的高 16 位全为零){
	x = x << 16 >> 16;			// 只保留低 16 位，因为高 16 位已经没有信息提供了
}
else {							// 也就是说最高有效位出现在高 16 位中
	x = x >> 16;
	Max = Max + 16;				// 后 16 位都贡献了最高有效位
}

给出这一部分的 C 语言实现：

int check = !!(x & 0xffff0000);		// 高 16 位全零时值为 0，否则值为 1；
Max = Max + (check << 4);			// 将 0 1 映射到了 0 16，这恰好满足对 Max 的增加情况
x = x >> (check << 4);				// 如果高 16 位不为 0，那就把高 16 位移到低 16 位的位置，否则不改变 x 的值

Note

为什么要这么移动 x ？

这几次查找用到的掩码值分别为 0xffff0000 0x0000ff00 0x000000f0 0b1100 0b10 ，你可以从掩码的构造发现移位的目的

结合最开始提到的 x 的值为 0 和 -1 的特殊情况，可以给出代码

code:

int howManyBits(int x) {
	int sign = x >> 31;					// 算术右移
	int check = 0;						// dlc 程序要求变量必须在最开始声明
	int Max = 0;
	x = (sign & ~x) | (~sign & x);

	check = !!(x & ((0xff + (0xff << 8)) << 16) );	// 题目限制常量不大于0xff，需要额外构造
	Max = Max | (check << 4);			// 这里用 | 代替了 +，因为每次 Max 的变化都只涉及单一数位
	x = x >> (check << 4);
	check = !!(x & (0xff << 8) );
	Max = Max | (check << 3);
	x = x >> (check << 3);
	check = !!(x & 0xf0);
	Max = Max | (check << 2);
	x = x >> (check << 2);
	check = !!(x & 0xc);
	Max = Max | (check << 1);
	x = x >> (check << 1);
	check = !!(x & 0x2);
	Max = Max | check;
	x = x >> check;
	Max = Max + !!(x | 0);
    
	return (!x & 1) | (~!x & Max+1);	// 对 x == -1 进行了特判（发现 x == 0 不需要特判） 
}

（接下来的三道题放开了 if while 控制语句，|| && == 的使用）

Note

IEEE 754 标准的单精度浮点数：1bit 符号位 + 8bits 指数位 + 23bits 尾数位

返回与表达式 2 * f 等价的二进制位表示

把 f 理解为单精度浮点数，对于 NaN Inf 直接输出原数，对于规格化数将指数部分加 1，对于非规格化数将尾数部分左移一位。需要注意的是，对于非规格化数的底数左移，可能会使其变成规格化数，实际上直接将尾数部分左移即可，没有特殊影响

（~~从代码可读性来说，应该采用 sign | exp | frac 的分割方案分别处理，而不是用一堆常数~~）

code:

unsigned floatScale2(unsigned uf) {
	// 提取指数位
	unsigned exp = (uf >> 23) & 0xff;
	// 特殊值
	if(exp == 0xff){
		return uf;
	}
	// 非规格化数
	if(exp == 0){
		return (uf & 0x80000000) | ((uf & 0x007fffff) << 1);
	}
	// 规格化数
	{
		return (uf & 0x807fffff) | ((uf & 0x7f800000) + 0x00800000);
	}
}

将浮点数 f 转换为整数

对于 NaN Inf 输出 0x80000000u ，对于其他 f，进行强制类型转换为 int 操作

对于非规格化数，其表示范围非常小（指数 E = -126），所以转换为 int 后一定近似为 0

对于规格化数，指数 E = exp - 127 ，当 E >= 31 时，这个数一定超过了 int 范围，输出 0x80000000u ；当 E < 0 时， |f| < 1，考虑到强制类型转换是向零舍入（也就是抹去小数点），转换为 int 后一定近似为 0 （这一情况可以与非规格化数的情况合并处理）

对于规格化数，指数 E 在 [0,30] 之间，此时我们可以开始构造整数了：

$$ (-1)^S \times 1.xxx \times 2^E $$

考虑非负数情况 S == 0（负数需要额外取反加一），先取尾数部分 frac = uf & 0x007fffff; ，规格化补上前导 1： frac = frac | 0x00800000 。得到完整的规格化尾数之后，根据 E 的值进行位移：以 23 为位移分界线（尾数长度，也就是说在不移位的情况下，此时的 frac 表示的就是指数为 23 的结果），指数超过 23 说明需要左移，低于 23 说明需要右移（同时起到向零舍入的作用）

最终加上符号位判断 sign ? -frac : frac ，完成实现

code:

int floatFloat2Int(unsigned uf) {
	unsigned exp = (uf >> 23) & 0xff;
	unsigned frac = uf & 0x007fffff;
	unsigned sign = uf >> 31;
	if(exp > 157){
		return 0x80000000u;
	}
	if(exp < 127){
		return 0;
	}
	frac = frac | 0x00800000;
	if(exp > 150){
		frac = frac << (exp - 150);
	}
	else {
		frac = frac >> (150 - exp);
	}
    
	if (sign){
		return ~frac + 1;
	}
	else {
		return frac;
	}
}

返回与表达式 2.0 ^ x 等价的二进制位表示

“如果结果太小无法用非规格化数表示，则返回 0。如果结果太大，则返回 +INF ”

最小的非规格化数（正数）是 0x1 ，对应的值为 $2^{-23} \times 2^{-126} = 2 ^{-149}$，所以 x < -149 时返回 0 ；非规格化数的 x 的取值范围是 [-149, -127] ；规格化数的取值范围是 [-126, 127] ，x > 127 时返回 +INF = 0x7F800000

非规格化数采用 1 << (x + 149) 构造；规格化数采用 (x + 127) << 23 构造

code:

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

---

附： driver.pl 评测结果

Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops     Puzzle
1       1       0       2       8       bitXor
1       1       0       2       1       tmin
1       1       0       2       8       isTmax
2       2       0       2       7       allOddBits
2       2       0       2       2       negate
3       3       0       2       7       isAsciiDigit
3       3       0       2       7       conditional
3       3       0       2       14      isLessOrEqual
4       4       0       2       5       logicalNeg
4       4       0       2       54      howManyBits
4       4       0       2       12      floatScale2
4       4       0       2       14      floatFloat2Int
4       4       0       2       9       floatPower2

Score = 62/62 [36/36 Corr + 26/26 Perf] (148 total operators)

附：实验相关说明

Important

评分工具

btest：检查 bits.c 中函数的正确性。

dlc：检查代码是否符合规则。

driver.pl：计算总分。

额外的特殊提醒

不要在 bits.c 中添加 #include <stdio.h> ！

dlc 对变量声明的顺序要求严格，必须在代码块的开头声明所有变量（遵循旧的 C 语言标准）

整数编码规则（前十题）

替换每个函数中的 return 语句，用一行或多行 C 代码实现该函数。

每个表达式 `Expr` 只能包含以下内容：（比如 `int var1 = Expr1;` 中的 `Expr1` 就是一个表达式）

整数常量：0 到 255（0xff），不允许使用更大的常量（如 0xffffffff）。
函数参数和局部变量：不能使用全局变量。
一元整数运算：!（逻辑非）、~（按位取反）。
二元整数运算：&（按位与）、^（按位异或）、|（按位或）、+（加法）、<<（左移）、>>（右移）。

每个 Expr 可以包含多个运算符，不限制每行只能有一个运算符。

不能使用的：

控制结构：如 if、do、while、for、switch 等。
宏定义：不能定义或使用宏。
额外函数：不能在本文件中定义其他函数。
函数调用：不能调用任何函数。
其他运算符：如 &&、||、-、?:（三元运算符）。
类型转换：不能使用任何形式的强制类型转换。
其他数据类型：只能使用 int，不能使用数组、结构体或联合体

机器假设

整数表示：使用 32 位二进制补码表示整数。
右移行为：算术右移（高位补符号位）。
移位异常：如果移位量 < 0 或 > 31，行为是未定义的。

一个正确的函数实现例子：

// 计算 2^x+4 的值
int pow2plus4(int x) {
    /* 利用移位计算 2 的幂 */
    int result = (1 << x);
    result += 4;
    return result;
    // 也可以直接写：return (1 << x) + 4;
}

浮点数编码规则（后三题）

对于需要实现浮点数操作的题目，编码规则相对宽松。允许使用：

循环和条件控制（如 if、while 等）。
int 和 unsigned 数据类型。
任意整数和无符号常量。
任何算术、逻辑或比较运算符（作用于 int 或 unsigned 数据）。

明确禁止的内容

宏定义：不能定义或使用宏。
额外函数：不能在本文件中定义其他函数。
函数调用：不能调用任何函数。
类型转换：不能使用任何形式的强制类型转换。
其他数据类型：只能使用 int 或 unsigned，不能使用数组、结构体或联合体。
浮点数相关操作：
- 不能使用浮点数据类型（如 float、double）。
- 不能使用浮点运算符（如 +、* 等作用于浮点数）。
- 不能使用浮点常量（如 3.14、0.5f）。

细化到每一题的注意事项可以在 bits.c 的每一题的注释中查看

CSAPP Datalab Solution

Lab 1: Data Lab

Solution

仅用 `&` 和 `~` 实现 `x ^ y`

返回最小的二进制补码整数

判断 `x` 是否为最大的二进制补码整数

判断 `x` 的所有奇数位是否均为 1

不使用 `-` 运算符返回 `-x`

判断 `x` 是否为 ASCII 数字（`0x30 ≤ x ≤ 0x39`）

实现三目运算符 `x ? y : z` 的功能

判断 `x` 是否小于等于 `y`

不使用 `!` 运算符实现 `!x`

返回能完整表示 `x` 所需的最小位数

返回与表达式 `2 * f` 等价的二进制位表示

将浮点数 `f` 转换为整数

返回与表达式 `2.0 ^ x` 等价的二进制位表示

评分工具

额外的特殊提醒

整数编码规则（前十题）

每个表达式 `Expr` 只能包含以下内容：（比如 `int var1 = Expr1;` 中的 `Expr1` 就是一个表达式）

不能使用的：

机器假设

浮点数编码规则（后三题）

明确禁止的内容

CSAPP Datalab Solution

Lab 1: Data Lab

Solution

仅用 & 和 ~ 实现 x ^ y

返回最小的二进制补码整数

判断 x 是否为最大的二进制补码整数

判断 x 的所有奇数位是否均为 1

不使用 - 运算符返回 -x

判断 x 是否为 ASCII 数字（0x30 ≤ x ≤ 0x39）

实现三目运算符 x ? y : z 的功能

判断 x 是否小于等于 y

不使用 ! 运算符实现 !x

返回能完整表示 x 所需的最小位数

返回与表达式 2 * f 等价的二进制位表示

将浮点数 f 转换为整数

返回与表达式 2.0 ^ x 等价的二进制位表示

评分工具

额外的特殊提醒

整数编码规则（前十题）

每个表达式 Expr 只能包含以下内容：（比如 int var1 = Expr1; 中的 Expr1 就是一个表达式）

不能使用的：

机器假设

浮点数编码规则（后三题）

明确禁止的内容

仅用 `&` 和 `~` 实现 `x ^ y`

判断 `x` 是否为最大的二进制补码整数

判断 `x` 的所有奇数位是否均为 1

不使用 `-` 运算符返回 `-x`

判断 `x` 是否为 ASCII 数字（`0x30 ≤ x ≤ 0x39`）

实现三目运算符 `x ? y : z` 的功能

判断 `x` 是否小于等于 `y`

不使用 `!` 运算符实现 `!x`

返回能完整表示 `x` 所需的最小位数

返回与表达式 `2 * f` 等价的二进制位表示

将浮点数 `f` 转换为整数

返回与表达式 `2.0 ^ x` 等价的二进制位表示

每个表达式 `Expr` 只能包含以下内容：（比如 `int var1 = Expr1;` 中的 `Expr1` 就是一个表达式）