实验需要的材料在这里：CSAPP Datalab
CSAPP原书在线阅读
将datalab-handout.tar下载复制到计划用来实验的目录下，解压：
1
| tar xvf datalab-handout.tar
|
解压之后，文件中bit.c是包含13个编程题中每个题的骨架。实验要求是使用没有任何循环或条件语句，以及有限的c算术和逻辑运算符来完成其中每个函数的内容，只能使用如下8个运算符：
在btest文件夹中，包含了一个测试程序，可以用来测试我们的实现是否正确。我们可以通过make命令编译btest，然后运行：
1
2
3
4
5
6
| # 编译并运行
make && ./btest
# 对某个函数进行单元测试
make && ./btest -f bitXnor
# 对某个函数进行单元测试，且指定测试用例，以 -1 指定第一个参数，依次类推
make && ./btest -f bitXnor -1 7 -2 0xf
|
dlc：用于检查我们的实现是否符合实验要求：
接下来，按照难度从易到难，我们依次完成实验
异或等价于不是同0且不是同1。
1
2
3
4
5
6
7
8
9
10
11
| //1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
return ~(~x&~y)&~(x&y);
}
|
获得对2补码的最小int值。在C中，int是32位的，所以补码的最小值就是符号位为1，其余位为0的值，对0x1左移31位即可。
1
2
3
4
5
6
7
8
9
| /*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1 << 31;
}
|
判断$x$是否是int的最大整数。最大整数tmax应该为0x7fffffff。
题目提示不允许使用移位操作。
注意到：
$$
Tmax=0x7fffffff,Tmin=0x80000000\\
so,that:Tmax=\sim Tmin,Tmax+1 = Tmin\\
-Tmin = \sim Tmin + 1 = Tmax + 1 = Tmin\\
so,that:\\
-(\sim Tmax) = Tmax + 1 = \sim Tmax\\
$$
也就是说，假如~x的相反数与~x相等，则满足x=Tmax。
注意除了Tmax拥有这个性质，当x=-1时：
$$
x=0xffffffff\\
\sim x=0x00000000\\
-(\sim x)=\sim (\sim x)+1 = x+1 = 0x00000000
$$
也满足这个上述特点，需要排除。
1
2
3
4
5
6
7
8
9
10
| /*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
return !!(~x)&!((~x)^(x+1));
}
|
提示
注意返回值是int型的，所以需要使用!!将结果转换为0或1。
当$x$中所有奇数位都为$1$时返回true。
奇数位都为$1$的数形如：
$$
x=0b1x_{30}1x_{28}1…1x_{2}1x_{0}
$$
思路是构造偶数位都为$1$的掩码0x55555555，再与$x$按位取或，若能构造出0xffffffff则复合要求。
由于实验要求不允许使用长度超过8位的常量，所以通过移位操作来构造掩码。
1
2
3
4
5
6
7
8
9
10
11
12
13
| /*
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = 0x55 + (0x55 << 8);
mask = mask + (mask << 16);
return !(~(mask | x));
}
|
返回$x$的相反数。
这个操作在第三个实验里其实已经使用过了。
$$
-x=\sim x + 1
$$
1
2
3
4
5
6
7
8
9
10
| /*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
|
判断$x$是否是ASCII码0~9中的某一个，即判断$0x30\leq x\leq 0x39$。
注意到$0x30\sim 0x39$的低4位从$0000\sim 1001$，低5~8位为$0011$，可以分别判断。
在满足低5~8位为$0011$的前提下，若倒数第4位为0则符合要求，若倒数第4位为1则需判断是否为$1000$或$1001$，即中间2位是否是0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| /*
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int f3 = !((x >> 4) ^ 3);
int f0t9 =!! (!(x & 8) + !(x & 6));
return f3 & f0t9;
}
|
实现出w =( x ? y : z)的条件判断。
感觉在上个题就实现了，上题相当于对一个二进制数$x=x_4 x_3 x_2 x_1$，是否满足$(x_4 == 1)?(x & 6 == 0):1$。
判断$x$通过!!x获得0/1，再通过按位取反+1分别获得0x00000000和0xffffffff，再与$y$和$z$按位或并相加，获得结果。
1
2
3
4
5
6
7
8
9
10
11
12
| /*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
int f = !!x;
int mask = ~f + 1;
return (y & mask) + (z & ~mask);
}
|
判断是否符合$x\leq y$的关系。
首先比较符号位，若符号位相同，则判断$x-y\leq 0$是否成立。减号可以由按位取反+1获得相反数，再相加实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| /*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int fx = x >> 31;
int fy = y >> 31;
int f = fx ^ fy;
int z = x + ~y + 1;
return !!((f & fx) | ((!f) & ((!z) | z >> 31)));
}
|
实现逻辑取反，$x$非0返回0，$x$为0返回1。
通过取反+1获得相反数，如果x是0，其相反数与x拥有相同的符号位0，否则在x和其相反数两个数之间一定会有至少一个符号位为1。
在Tmin = 0x80000000中也一致，-Tmin = ~Tmin + 1 = 0x7fffffff + 1 = 0x80000000。
1
2
3
4
5
6
7
8
9
10
11
| /*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) {
return (((~x + 1) | x) >> 31) + 1;
}
|
计算出表示$x$需要的最少补码位数。
$$
0=0b0,1bit\\
1=0b01,2bits\\
-1=0b1,1bit\\
2=0b010,3bits\\
-2=0b10,2bits\\
3=0b011,3bits\\
-3=0b101,3bits
$$
如果是正数的话x补码形如：0x00001...，所需补码位数是从左向右第一个1的位置在+1（符号位），负数的话x补码形如：0x11110...，取反之后是0x00001...，所需位数是从左向右第一个1的位置+1。
不能通过循环来从左向右找，尝试二分找第一个1的位置。
int型有32位，逐渐二分为16、8、4、2、1位。
$$
\begin{aligned}
&x = 0b0001,1…,….,….,….,….,….,….\\
loop1:& !!(x»16)=1,b16=16\\
&\text{高16位存在1，则可以舍去低16位，将x右移16位}\\
&x = x»16=0b0001,1…,…,…\\
loop2:&…
\end{aligned}
$$
最后统计完毕之后要+1符号位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
int f = !!(x >> 31);
f = ~f + 1;
x = (x & ~f) + (~x & f);
int b16 = (!!(x >> 16)) << 4;
x = x >> b16;
int b8 = (!!(x >> 8)) << 3;
x = x >> b8;
int b4 = (!!(x >> 4)) << 2;
x = x >> b4;
int b2 = (!!(x >> 2)) << 1;
x = x >> b2;
int b1 = !!(x >> 1);
x = x >> b1;
return b16 + b8 + b4 + b2 + b1 + x + 1;
}
|
求一个float浮点数乘2之后的值。
float的各位：
| 符号 | 指数(exp) | 尾数 |
|---|
| 1 | 8 | 23 |
0/1 | 0x01111111+e | 小数部分 |
通过定义先按指数是否为0x00000000或0x11111111、≠0 & ≠255分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /*
* floatScale2 - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representation of
* single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatScale2(unsigned uf) {
unsigned s = uf & 0x80000000;
unsigned exp = uf & 0x7f800000;
unsigned f = uf & 0x007fffff;
if(!exp){
return s | (uf << 1);
}
if(!(exp ^ 0x7f800000)){
return uf;
}
exp = exp + 0x00800000;
if(exp == 0x7f800000){
return 0x7f800000 | s;
}
return s | (exp & 0x7f800000) | f;
}
|
将float浮点数转化为int类型。
算出真实的Exp：Exp + 0b0111111 = e，
再给尾数最左侧补一位1，整体右移|Exp-23|位（舍位），再通过正负性取补码。
注意，若溢出或是NaN返回0x80000000u
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /*
* floatFloat2Int - 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.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
int floatFloat2Int(unsigned uf) {
unsigned s = uf & 0x80000000,
e = uf & 0x7f800000,
f = uf & 0x007fffff;
int exp = (e >> 23) - 0x7f;
unsigned res = f | 0x00800000;
if(exp < 0) return 0;
if(exp >= 31) return 0x80000000;
if(exp < 23)exp = 23 - exp;
else exp = exp - 23;
res = res >> exp;
if(s)return -res;
else return res;
}
|
求浮点表示下的$2.0$的$x$次。
emmm其实就是exp + x，那就处理好$0b000000$和$0b11111111$的情况就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /*
* floatPower2 - Return bit-level equivalent of the expression 2.0^x
* (2.0 raised to the power x) for any 32-bit integer x.
*
* The unsigned value that is returned should have the identical bit
* representation as the single-precision floating-point number 2.0^x.
* If the result is too small to be represented as a denorm, return
* 0. If too large, return +INF.
*
* Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatPower2(int x) {
int exp = 0x7f + x;
if(exp < 0x00)return 0;
if(exp >= 0xff)return 0x7f800000;
if(exp == 0x00)return 1;
return exp << 23;
}
|
写完哩~最后一个样例似乎跑了好久（。
做完实验第一次感觉到!f和~f的区别（迫真。
下个实验再见(∪.∪ )…zzz