CSAPP实验之Data Lab _csapp

壮心未与年俱老，死去犹能作鬼雄。这篇文章主要讲述CSAPP实验之Data Lab相关的知识，希望能为你提供帮助。
0.上手指南一共 12 个需要补充的函数，所有的工作都只需修改 bits.c 文件，测试的话有三种方式：btest, dlc, 和 BDD checker。
一些小技巧：在函数开始时声明所有变量
}应该在第一列
注意运算符号的优先级，使用括号确保顺序的正确
关注 !, 0, TMin 等
任务指引还是比较清晰的，主要有以下一些说明：整型的范围是 0 到 255(0xFF)，不允许用更大
只能包含参数和局部变量
一元操作符 ! ~
二元操作符 & | + < < > >
不允许的操作有：使用任何条件控制语句
定义和使用宏
定义其他的函数
调用函数
使用其他的操作符
使用类型转换
使用除 int 之外的类型（针对整型）
使用除 int, unsigned 之外的类型（针对浮点数）
可以认为机器：使用 2’s complent，32位
执行算术右移
移动超过字长的位数会出问题
其他需要注意的事情有：使用 dlc(data lab checker) 来检测代码的合法性（有没有使用不给使用的符号语法等等）
每个函数都有操作数的上限值，注意 = 不算
使用 btest 来测试结果的正确与否
使用 BDD checker 来正规测试你的函数
显示32位int整型的show方法

void show(int x) { /* Show 32 Bits Integer By Binary */ for (int i = 0; i < 32; ++i) { if (i != 0 & & i % 4 == 0) cout < < " " ; cout < < ((x > > 31) & 1); x < < = 1; } cout < < endl; }

该方法用于检验函数是否写的正确以及调试的方便性
1.thirdBits题目要求：return word with every third bit (starting from the LSB) set to 1
允许操作：! ~ & ^ | + < < > >
操作数限制：8
分值：1

int thirdBits() { /* Desired output: 0100 1001 0010 0100 1001 0010 0100 1001 step 1:0000 0000 0000 0000 0000 0000 0100 10010x49 step 2:0000 0000 0000 0000 1001 0010 0100 1001 step 3:0000 0000 1001 0100 1001 0010 0100 1001 step 4:0100 1001 0010 0100 1001 0010 0100 1001 */ int a = 0x49; int b = (a < < 9); int c = a + b; return (c < < 18) + c; }

2.isTmin题目要求：returns 1 if x is the minimum, two’s complement number, and 0 otherwise
允许操作：! ~ & ^ | +
操作数限制：10
分值：1
该题用于检验INT_MIN 该题用到INT_MIN+INT_MIN溢出后为0的技巧但也要注意0+0也为0

int isTmin(int x) { /* Return 1 if x is the minimum, two’s complement number, and 0 otherwise. */ return !(x + x) & !!(x); }

3.isNotEqual题目要求：return 0 if x == y, and 1 otherwise
例如: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
允许操作：! ~ & ^ | + < < > >
操作数限制：6
分值：2
该题用异或即可，不同则不为0，相同则0，随后用到了!!将int值转化为bool值的技巧

int isNotEqual(int x, int y) { /* Return 0 if x == y, and 1 otherwise */ return !!(x^y); }

4.anyOddBit题目要求：return 1 if any odd-numbered bit in word set to 1
例如： anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
允许操作：! ~ & ^ | + < < > >
操作数限制：12
分值：2
该题的想法是想声明一个值为0xaa的变量随后将其扩展到32位，最后与x做与操作即可得到答案

int anyOddBit(int x) { /* Return 1 if any odd-numbered bit in word set to 1 1010 1010 */ int a = 0xAA; int b = (a < < 8) + a; int c = (b < < 8) + a; int d = (c < < 8) + a; return !!(x& d); }

5.negate题目要求：return -x
例如：negate(1) = -1.
允许操作：! ~ & ^ | + < < > >
操作数限制：5
分值：2
该题利用补码的取反后加一即可达到要求，但是最开始没有想到取反操作而是制造了0xffffffff这个数进行操作

int negate(int x) { /* Return negate eg: if x==1 return -1 Or return ~x+1 */ int mask = (1 ^ (1 < < 31)) > > 31; return (x^mask) + 1; }

6.conditional题目要求：same as x ? y : z
例如：conditional(2,4,5) = 4
允许操作：! ~ & ^ | + < < > >
操作数限制：16
分值：3
该题即三目操作符

int Conditional(int x, int y, int z) { /* x?y:z Better : int mask= ~!x+1; */ int mask = (!!x) < < 31; mask > > = 31; return (mask& y) | ((~mask)& z); }

7.subOK题目要求：Determine if can compute x-y without overflow
例如：
subOK(0x80000000,0x80000000) = 1
subOK(0x80000000,0x70000000) = 0
允许操作：! ~ & ^ | + < < > >
操作数限制：20
分值：3
该题判断减法是否溢出，减法是否溢出，第一个取决的便是两个数字的符号，我们可以发现
同号相减是不会溢出的，而异号相减溢出时结果的符号会与被减数的符号相反，所以有下面代码

int subOK(int x, int y) { /* Determine if can compute x-y without overflow */ int a = (x > > 31) & 1; int b = (y > > 31) & 1; int res = x + ~y + 1; int c = (res > > 31) & 1; return !(a^b) | !(a^c); }

8.isGreater题目要求：if x > y then return 1, else return 0
例如：isGreater(4,5) = 0, isGreater(5,4) = 1
允许操作：! ~ & ^ | + < < > >
操作数限制：24
分值：3
该题比较两个数字的大小，首先我们明确正数是比负数大的，而负数比正数小
利用该性质我们可以先由该性质判断，随后利用两数相减为正数时返回1性质写出表达式
我们需要注意的是，该地方是不需要考虑溢出的，因为溢出是异号相减的行为

int isGreater(int x, int y) { /* if x > y then return 1, else return 0 */ int a = (x> > 31) & 1, b = (y> > 31) & 1; int res = x + ~y + 1; int c = (res> > 31) & 1; return ((!a& b) | !c)& (!a | b); }

9.bitParity题目要求：returns 1 if x contains an odd number of 0’s
例如：bitParity(5) = 0, bitParity(7) = 1
允许操作：! ~ & ^ | + < < > >
操作数限制：20
分值：4
该题要我们数出一个int整形的二进制表达中是否有奇数个0，我们可以利用异或不改变奇偶性来写

int bitParity(int x) { /* returns 1 if x contains an odd number of 0’s bitParity(5) = 0, bitParity(7) = 1 */ x = (x > > 16) ^ x; x = (x > > 8) ^ x; x = (x > > 4) ^ x; x = (x > > 2) ^ x; x = (x > > 1) ^ x; return (x & 1); }

10.howManyBits题目要求：return the minimum number of bits required to represent x in two’s complement
例如：
howManyBits(12) = 5
howManyBits(298) = 10
howManyBits(-5) = 4
howManyBits(0) = 1
howManyBits(-1) = 1
howManyBits(0x80000000) = 32
允许操作：! ~ & ^ | + < < > >
操作数限制：90
分值：4
该题要求我们返回该数字用补码表示时最少能用几位来表示我们可以用二分法来判断有多少位
然后我们还要对特殊情况0和-1进行区分对待
值得一提的是，我们对负数要取反，但不必加一，因为补码表示中负数范围是比正数大的
而最小的负数取反后刚刚好是最大的正数

int howManyBits(int x) { /* return the minimum number of bits required to represent x in two’s complement */ int a = ((!x) < < 31) > > 31; //当x为0时，a全为1，否则全为0 int b = ((!~x) < < 31) > > 31; //当x为-1时，b全为1，否则全为0 int bit_16, bit_8, bit_4, bit_2, bit_1; int sum; int op = x ^ (x > > 31); bit_16 = (!!(op > > 16)) < < 4; op = op > > bit_16; bit_8 = (!!(op > > 8)) < < 3; op = op > > bit_8; bit_4 = (!!(op > > 4)) < < 2; op = op > > bit_4; bit_2 = (!!(op > > 2)) < < 1; op = op > > bit_2; bit_1 = (!!(op > > 1)); op = op > > bit_1; sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1; return (a & 1) | (b & 1) | (~a & ~b& sum); }

11.float_i2f题目要求：Return bit-level equivalent of expression (float) x. Result is returned as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point values.
允许操作：Any integer/unsigned operations incl. ||, & & . also if, while
操作数限制：30
分值：4
该题只要懂得浮点数的表示即可写出

unsigned float_i2f(int x) { int sign = (x > > 31) & 1; int exponent, fraction, fraction_mask = 0x7fffff; if (x == 0) return 0; else if (x == 0x8000000) exponent = 158; else { if (sign == 1) x = ~x + 1; int bit_16, bit_8, bit_4, bit_2, bit_1; int sum; int op = x ^ (x > > 31); bit_16 = (!!(op > > 16)) < < 4; op = op > > bit_16; bit_8 = (!!(op > > 8)) < < 3; op = op > > bit_8; bit_4 = (!!(op > > 4)) < < 2; op = op > > bit_4; bit_2 = (!!(op > > 2)) < < 1; op = op > > bit_2; bit_1 = (!!(op > > 1)); op = op > > bit_1; sum = 1 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1; if (sum > 24) fraction = x > > (sum - 24); else if (sum < 24) fraction = x < < (24 - sum); fraction & = fraction_mask; exponent = 127 + sum - 1; } show(fraction); unsigned ux = (sign < < 31) + (exponent < < 23) + fraction; return ux; }

12.float_f2i题目要求：Return bit-level equivalent of expression (int) f for floating point argument f. Argument is passed as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point value. Anything out of range (including NaN and infinity) should return 0x80000000u.
允许操作：Any integer/unsigned operations incl. ||, & & . also if, while
操作数限制：30
分值：4
该题是11题的逆过程，值得注意的是，我们要对小数部分进行切除

int float_f2i(float f) { int*pf = (int*)& f; int x = *pf; show(x); int sign = x > > 31; int x_abs = x & 0x7fffffff; int exponent = x_abs > > 23; if (exponent < 127) return 0; show(exponent); int fraction_mask = 0x7fffff; int fraction = x& fraction_mask; show(fraction); int i = 0; while (fraction) { if (fraction & 1) break; fraction > > = 1; ++i; } cout < < i < < endl; show(fraction); fraction |= (1 < < (23 - i)); show(fraction); int len = exponent - 127 - (23 - i); cout < < len < < endl; int res; if (len > 0) res = fraction < < len; else res = fraction > > -len; cout < < exponent < < endl; cout < < res < < endl; if (sign == -1) res = ~res + 1; return res; }

结语【CSAPP实验之Data Lab】第一个数据实验算是结束了，通过该实验，我又加深了对数据的理解，尤其是各种掩码的设计，有了更深的理解