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类型的常数，任意算术、逻辑、比较运算符
-
不得定义或使用宏
-
不得自行定义或调用函数
-
不得进行任何形式的类型转换
-
不得使用除
int和unsigned以外的类型（包括数组，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;
}