DataLab题解

CS:APP DataLab题解

Lab简述

​ 使用高度受限的C语言子集实现简单的逻辑、二进制补码和浮点数操作的函数。

Notes

  • 使用dlc compiler来检测你的代码是否符合规范
  • 每个函数使用的运算符数量会有一定的限制,不得超出该限制(=不计入统计),限制数在题目前的注释内给出
  • 使用btest验证你的代码的正确性
  • 使用BDD checker正式检验你的代码是否通过

整数部分

要求

  • 表达式内只能使用0~255(含)的整型常数,而不能使用其它整型常数如0xfffff
  • 只能使用函数参数与本地变量,不得使用全局变量
  • 允许使用的单目运算符:! ~
  • 允许使用的双目运算符:& ^ | + << >>
  • 禁止使用控制语句,如if,do,while,switch,for
  • 禁止定义或使用宏
  • 禁止声明函数
  • 禁止调用函数(也不能include头文件stdio.h)
  • 禁止使用其它操作符,如&&,||,-,?:
  • 禁止任何形式的类型转换
  • 禁止使用int以外的其它类型变量(包括数组,union,struct)
  • 测试环境
    • 采用补码表示整型,int为32位
    • 执行算术右移
    • 右移超过类型长度时无定义

题目

bitXor
题目描述

​ 计算两个数的异或x ^ y

题目限制
  • 允许使用的操作符:& ~
  • 使用操作符数量的上限:14
思路

​ 从异或的真值表直接凑出来就行

解法
int bitXor(int x, int y) {
    return ~(x & y) & ~(~x & ~y);
}
tmin
题目描述

​ 返回最小的补码数值

题目限制
  • 允许使用的操作符:! ~ & ^ | + << >>
  • 使用操作符的数量上限:4
思路

​ 最小补码值的表示为1000...00,直接将1左移适当位数即可

解法
int tmin(void) {
	return 1 << 31;
}
isTmax
题目描述

​ 判断一个数是不是Tmax(补码最大值),是时返回1,否则返回0

题目限制
  • 允许使用的操作符:! ~ & ^ | +
  • 使用操作符数量的上限:10
思路
  • 最开始没看清题目限制,写了一个(~x >> 31) & ((x+1) >> 31),利用Tmax为正数且Tmax+1为负数的性质,结果写完发现不能用>>,QAQ
  • 不过上面一种方法为我提供了思路,就是Tmax的补码表示是0111..11,Tmax+1是1000..00(废话
  • 一番推导可以得到只有Tmax具有(x | (x + 1)) == 111..111且为的性质
解法
int isTmax(int x) {
	return (!~((x | (x + 1)) & (x ^ (x + 1)))) ^ (!(x + 1));
}
allOddBits
题目描述

​ 判断一个数\(x\)所有二进制奇数位是否全为0,是则返回1,否则返回0

题目限制
  • 允许使用的操作符:! ~ & ^ | + << >>
  • 使用操作符的数量上限:12
思路
  • 先用掩码处理只保留\(x\)的奇数位
  • 由于要求最大可使用的常数为0xff,所以按字节判断奇数位是否为0,转换为每一字节\(x_i\)是否等于0xAA
  • 不能使用==,改用异或判断相等
解法
int allOddBits(int x) {
	return !((x & (x >> 8) & (x >> 16) & (x >> 24) & 0xAA) ^ 0xAA);
}
negate
题目描述

​ 计算\(-x\)

题目限制
  • 允许使用的操作符:! ~ & ^ | + << >>
  • 允许操作符的最大数量:5
思路

​ 这道题书上推导过,有-x = ~x+1

解法
int negate(int x) {
	return ~x + 1;
}
isAsciiDigit
题目描述

​ 判断一个数是不是ASCII的'0'-'9',即是否满足\(0x30 \le x\le 0x39\)

题目限制
  • 允许使用的操作符:! ~ & ^ | + << >>
  • 允许操作符的最大数量:15
思路
  • 十六进制下个位是个范围,考虑从十位入手
  • 通过加上不同的数时十位的值确定是否在范围内
解法
int isAsciiDigit(int x) {
	return !(((x + 6) & 0xF0) ^ 0x30) & !(((x + 16) & 0xF0) ^ 0x40);
}
conditional
题目描述

​ 实现x ? y : z

题目限制
  • 允许使用的操作符:! ~ & | ^ + << >>
  • 允许操作符的最大数量:16
思路
  • 由于x可能具有很多的值不便处理,先用x = !x讲x转换为0或1便于处理
  • 通过一定的变化,简化为一下实现k = k * x(x = 0或1)
  • -1的补码为11...11,所以将转化为k = k & (-x)
  • -x的操作前面的lab已实现,即-x = ~x+1
解法
int conditional(int x, int y, int z) {
	x = ~(!x) + 1;
	z = z & x;
	x = ~(x + 1) + 1;
	y = y & x;
	return y | z;
}
isLessOrEqual
题目描述

​ 判断是否满足\(x \le y\)

题目限制
  • 允许使用的操作符:! ~ & | ^ + << >>
  • 允许操作符的最大数量:24
思路
  • 将\(x \le y\)转化为\(y - x \ge 0\),但直接做减法可能会发生溢出
  • 分析知只有\(x,y\)异号时会产生溢出,所以分\(x,y\)异号和同号两种情况讨论即可
解法
int isLessOrEqual(int x, int y) {
	int k1 = ~(((x ^ y) >> 31) & (x >> 31)) + 1;//x < 0 && y >= 0
	int k2 = !((x ^ y) >> 31) & ~((~x + y + 1) >> 31);//xy > 0 && y - x >= 0
	return k1 | k2;
}
logicalNeg
题目描述

​ 不使用!下实现!

题目限制
  • 允许使用的操作符:~ | & ^ + << >>
  • 允许操作符的最大数量:12
思路
  • 除0以外的所有数\(x\),均满足\(x\)和\(-x\)中至少有一个为负(注意不是只有一个为负,\(Tmin\)和\(-Tmin\)均为负),但0满足0和-0均不为负,以此作为判断依据
解法
int logicalNeg(int x) {
	return ~((x | (~x + 1)) >> 31) & 1;
}
howManyBits
题目描述

​ 返回一个二进制数\(x\)的补码编码至少需要的二进制位数

题目限制
  • 允许使用的操作符:! ~ & | ^ + << >>
  • 允许操作符的最大数量:90
思路
  • 这道题卡了我一天多,差点真卡死了
  • 首先找一下性质,一个数用\(w\)位存储且最少需要\(k\)位时(\(w\ge k\)),那么这个数可以写作\(0..00(w-k+1个0)1...\)或\(1..11(w-k+1个1)0...\),所以有将其右移\(k-1\)位后可以得到\(0(00..00)\)或\(-1(11..11)\),问题转化为寻找最小的这个\(k\)
  • 一个一个的找90个操作符也不够用,所以想到把二分答案的思路,但它又不能写循环结构qwq
  • 后来想到了RMQ问题里的倍增,就用类似的做法写了出来
解法
int howManyBits(int x) {
	int ans = 0;
 	ans += (!!(x >> 15 ^ (x >> 15 >> 1))) << 4;
 	ans += (!!(x >> (7 + ans) ^ (x >> (7 + ans) >> 1))) << 3;
 	ans += (!!(x >> (3 + ans) ^ (x >> (3 + ans) >> 1))) << 2;
 	ans	+= (!!(x >> (1 + ans) ^ (x >> (1 + ans) >> 1))) << 1;
 	ans += (!!(x >> (ans) ^ (x >> (ans) >> 1)));
 	return ans + 1;
}

浮点数部分

要求

  • 浮点数部分的限制少很多,可以使用循环和控制结构、任意int或unsigned类型的常数,任意算术、逻辑、比较运算符

  • 不得定义或使用宏

  • 不得自行定义或调用函数

  • 不得进行任何形式的类型转换

  • 不得使用除intunsigned以外的类型(包括数组,struct,union)

  • 不得使用任何浮点类型的数据、操作以及常数

题目

floatScale2
题目描述

​ 输入一个浮点数\(uf\),返回\(uf*2\)的浮点表示

题目限制
  • 允许操作符的最大数量:30
思路
  • 没啥复杂的就是分情况讨论
  • 情况一:\(uf\)是无穷大或NaN,直接返回\(uf\)
  • 情况二:\(uf\)是非规格化数,\(uf*2\)也为非规格化数,即\(uf\)的\(f\)部分编码首位不为1,直接将\(f\)部分乘2即可
  • 情况三:\(uf\)是非规格化数,\(uf*2\)是规格化数,此时计算一下可知\(f\)部分变为\(2*f-0x800000\),\(e\)部分为\(1\)
  • 情况四:\(uf\)为规格化数,直接在\(e\)上加一即可
解法
unsigned floatScale2(unsigned uf) {
	int maske = 0x7f800000,maskf = 0x7fffff;
	if((maske & uf) == maske){//inf or NaN
		return uf;
	}
	if((maske & uf) == 0){
		int f = maskf & uf;
		if(f & 0x400000){
			f = f * 2 - 0x800000;
			uf |= 0x800000;
		}
		else f <<= 1;
		uf = (uf & 0xff800000) | f;
		return uf;
	}
	else{
		uf += 0x800000;
		return uf;
	}
}
floatFloat2Int
题目描述

​ 输入一个浮点数\(uf\)的位表示,返回(int)uf

题目限制
  • 允许操作符的最大数量:30
思路
  • 就还是分情况讨论(浮点数部分能用if是真**的爽)
  • 情况一:\(uf\)是无穷大或NaN,直接返回0x80000000u
  • 情况二:\(uf\)是非规格化数,直接返回0(因为最大非规格化数的绝对值小于0)
  • 情况三:\(uf\)是规格化数,按\(v=s*2^{e-bias}*(1+f*2^{-k})\)的公式计算即可,注意处理溢出和未定义的移位运算
解法
int floatFloat2Int(unsigned uf) {
	int maske = 0x7f800000,maskf = 0x7fffff,s = uf >> 31;
	if(( maske & uf ) == maske) return 0x80000000u;
	if(( maske & uf ) == 0) return 0;
	int f = ( uf & maskf ) + 0x800000;
	int bias = (1 << (8-1)) - 1;
	int e = ((maske & uf) >> 23) - bias;
	if(e > 31) return 0x80000000u;
	int v = f;
	if(e - 23 >= 0) v <<= e-23;
	else if(23-e < 32) v >>= 23-e;
	else v = 0;
	if(s) v = -v;
	return v;
}
floatPower2
题目描述

​ 输入整数\(x\),返回\(2.0^x\)的浮点表示

题目限制
  • 允许操作符的最大数量:30
思路
  • 先计算得知单精度浮点无法表示\(x < -149\)和\(x>128\)的值
  • 对于\(-149\le x < -126\)的情况,浮点表示为非规格化数,即(1<<(149-x))
  • 对于\(-126\le x \le 128\)的情况,浮点表示为规格化数,推导可知\(f\)部分为0
解法
unsigned floatPower2(int x) {
    if(x < -149) return 0;
	if(x > 128) return 0x7f800000;
	if(x < -126){
		int k = -126 - x;
		return 1 << (23 - k);
	}
	unsigned e = x + 127;
	return e << 23;
}
上一篇:循环组件中的重名对象


下一篇:NX二次开发-UFUN读取工作图层UF_LAYER_ask_work_layer