实验及其环境
Data Lab
[Updated 12/16/19]
环境: Ubantu
gcc版本: 4.8.5
常用命令
make：编译所有文件
./dlc bits.c: 测试使用的操作符是否合法
./btest -h //测试命令的功能列表，按照说明使用即可
如./btest -f bitXor，测试bitXor是否能通过所有的测试用例
在data-handout的readme文件中对上述命令有具体说明，在此不多赘述
题解
第一关
1.bitXor
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
大意：使用~和&来完成^运算符。
大致思路是先完成
( ~x & y) | ( x & ~y)
运算，最后利用摩根定律，使用~和&运算符来替代
|
操作符。
int bitXor(int x, int y) {
return ~(~(~x & y) & ~( x & ~y));
}
2.tmin
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
大意：求Tmin
送分题，直接移位
int tmin(void) {
return 1 << 31;
}
3.isTmax
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
大意：判断给出的x是否是Tmax。
如果x == Tmax，则有
!~((x + 1) ^ x ) = 1
，当然 x == -1时，该等式也成立。因此特判一下 x != -1，此时
!!(x + 1)
应该为0x1，等式成立只有这两种情况了。
int isTmax(int x) {
return !~((x + 1) ^ x ) &!!(x + 1);
}
第二关
1.allOddBits
/*
* 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
*/
大意：如果x中所有的奇数位都为1则返回1，反之返回0.(x位数范围为0-31)，偶数位可以不用管。
取其中的一个字节10101010，十进制为170,将其生成为一个所有奇数位都为1的数字mask(10101010 10101010 10101010 10101010)，拿这个数字和x来比较，如果x == mask,则必有
(x&mask) ^ mask == 0
(a^a == 0, x&mask是为了去掉偶数位)
int allOddBits(int x) {
int mask = 170 + (170 << 8) + (170 << 16) + (170 << 24);
return !((x & mask) ^ mask);
}
2.negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
大意：求相反数
书本中给有这个公式
int negate(int x) {
return ~x + 1;
}
第三关
1.isAsciiDigit
/*
* 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
*/
大意：判断给定的x是否是ascii码，即
0x30 <= x <= 0x39
返回1，反之则返回0
先算出0x30等于十进制的48，而0x39位十进制的57，所以转化一下，即求
x-48>=0 && x-58<0
（-运算符使用第二关第三题可以计算），再通过取反并移31位。如果x是在此区间范围，
!((x + ~48 + 1) >> 31) = 0x1
,
((x + ~58 + 1) >> 31 = 0x1
，通过&连接即可
int isAsciiDigit(int x) {
return (!((x + ~48 + 1) >> 31)) & ((x + ~58 + 1) >> 31);
}
2.conditional
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
大意：实现三目运算符 x ? y : z
这题可以这样想，既然x!=0返回y，则有一部分应该是0xffffffff & y，此时应该无视z,那么另外一个部分就可以是0x0 & z，然后通过|操作符连接。即返回
(0xffffffff & y) | (0x0&z)
那么问题来了，x!=0时，则需将x转化为0xfffffff，反之则转化为0x0;我是用移位操作来完成的，类似二分的递增。
int conditional(int x, int y, int z) {
int bits = !!x;
bits += bits << 1;
bits += bits << 2;
bits += bits << 4;
bits += bits << 8;
bits += bits << 16;
return (bits & y) | (~bits & z);
}
看到网上有将x转化为0xfffffff更神仙的方法:
int conditional(int x, int y, int z) {
return ((!x+~1+1)&y)|((~!x+1)&z);
}
3.isLessOrEqual
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
大意: x<= y时返回1，反正返回0
先得到x, y和 y – x 的符号位，再分三种情况讨论即可
①x < 0, y < 0, y – x >= 0
②x > 0, y > 0, y – x >= 0
③y >=0, x < 0
int isLessOrEqual(int x, int y) {
int negX = x >> 31;
int negY = y >> 31;
int gte = !((y + ~x + 1) >> 31);
return (negX & negY & gte) | (!negX & !negY & gte) | (negX & !negY);
}
第四关
1.logicalNeg
/*
* 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
*/
大意：实现!的逻辑
这题大概是第四关里面最简单了的
注意一个特点, 只有+0 == -0,其他的数都不等，那么可以利用这个特点，来对x进行一个比较和判断，当 x == 0时，(~-0) & (~+0) 的符号位一定为1, 若是其他的数，符号位则不为1. 最后右移31位，&1去除其他的位可以得到结果
int logicalNeg(int x) {
return (((~(~x + 1)) & (~x)) >> 31) & 1;
}
2.howManyBits
/* 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
*/
大意：返回最少用来表示x的位数.
可以说是最难的一题了
比如说howManyBits(12) 返回 5，12的需要最少的二进制是 01100，高位的0可以去掉，此时需要的位数是5位。但是如果用1100就不行，因为这时表示的是-4。表示-5的需要最少的二进制为 1001，返回4
可以先做一个预处理，把负的都取反，比如上面的-5,取反后为(1…1)0110，这时就可以把-5当成正数来处理了。
接下来这一部分比较头疼，我也是想了很久才想明白，主要是使用了一个二分的思想
核心思想是，查看x的后16bit是否都是1，如果是这样的话，那么x至少要16位才能表示；如果后16位都是1，那么将x右移16位，反之则右移0位，使用
(!!(x >> 16)) << 4
可以使得s16变为0或16；接下来，再依次对x的后8位，4位，2位，1位进行处理。
最后特殊情况需要注意，比如当x输入是0时，这是s1 – s16都是0，此时s16 + s8 + s4 + s2 + s1 = 0, 但实际上都需要返回1，尝试在之前的结果加上x+1，此时返回的刚好等于1；再看另一种情况， x是0x01需要返回2，此时s1 – s16均为0， 最后的x = 1，x+1 =2，也成立。所以最后应该返回
s16 + s8 + s4 + s2 + s1 + x + 1
而不是
s16 + s8 + s4 + s2 + s1
int howManyBits(int x) {
int s16, s8, s4, s2, s1;
int sign = (x >> 31) & 1;
int mask = ~sign + 1;
x = (mask & ~x) | (~mask & x);
s16 = (!!(x >> 16)) << 4;
x >>= s16;
s8 = (!!(x >> 8)) << 3;
x >>= s8;
s4 = (!!(x >> 4)) << 2;
x >>= s4;
s2 = (!!(x >> 2)) << 1;
x >>= s2;
s1 = (!!(x >> 1)) << 0;
x >>= s1;
return s16 + s8 + s4 + s2 + s1 + x + 1;
}
3.floatScale2
/*
* 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
*/
大意：给定一个位表示的浮点数f，返回2*f的位表示
这里面牵扯到的是浮点数的知识了，翻书可以知道float是32位表示，其中符号位sign占1位，阶码位exp占8位，尾数frac占23位。所以可使用掩码操作，先分别得到sign，exp，frac的位表示。
接下来就很明朗了，直接将这个数分为规格化数(normalize)和非规格化数(denormolize)讨论即可，对sign，exp，frac进行计算，最后返回
sign | exp | frac
。
①exp = 0的时候，十进制的值表示为2
E
∗
M
{^E*M}
E
∗
M
，这时候uf*2，也就是2
E
∗
2
M
{^E*2M}
E
∗
2
M
，直接frac左移一位就可以了(非规格化的值时，M=f)。
②exp !=0 且 uf不为无穷时，十进制2
E
{^E}
E
∗
M
{*M}
∗
M
乘2就变成了2
E
+
1
{^{E+1}}
E
+
1
∗
M
{*M}
∗
M
，又
E
=
e
x
p
−
b
i
a
s
{E = exp – bias}
E
=
e
x
p
−
b
i
a
s
,所以只需要将exp加1就可以完成计算了，此外，还要注意一下溢出的情况特判。
unsigned floatScale2(unsigned uf) {
unsigned sign = uf & 0x80000000;
unsigned exp = uf & 0x7f800000;
unsigned frac = uf & 0x007fffff;
if( exp == 0x0){
frac <<= 1;
}else if(exp!= 0x0 && exp != 0x7f800000){
exp += 0x00800000;
// return ∞
if(exp == 0x7f800000) return sign | exp;
}
return sign | exp | frac;
}
4.floatFloat2Int
/*
* 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
*/
大意：将float转化为int，其中float给出的是位表示。
还是先分别取其中的sign,exp和frac三个位。先计算出
a
b
s
=
2
E
∗
M
abs = 2{^E}*M
a
b
s
=
2
E
∗
M
，然后返回
sign == 0 ? abs : -abs
;
可以先在草稿纸上算一算，uf<1时肯定要返回0，所以计算uf==1时的临界值，即
2
E
∗
M
=
=
1
{2^E*M == 1}
2
E
∗
M
=
=
1
，此时E是0，根据
E
=
e
x
p
−
127
{E = exp – 127}
E
=
e
x
p
−
1
2
7
可得exp为127，所以分下面几种情况讨论
①当exp<127时，向下取整进而返回0；
②这时再来考虑一下溢出的情况，int最大值为
2
31
−
1
2^{31}-1
2
3
1
−
1
所以这个时候
e
x
p
−
127
=
=
31
{exp – 127} == 31
e
x
p
−
1
2
7
=
=
3
1
刚好溢出，所以当exp > 157的时候返回一个0x80000000u
③最后来考虑可以正常计算的情况，先求得abs的值，然后再来考虑frac位的情况。由于
a
b
s
=
2
E
∗
(
1
+
f
)
{abs = 2^E*(1+f)}
a
b
s
=
2
E
∗
(
1
+
f
)
，所以只需要在原来的基础上加上
f
∗
2
E
{f*2^E}
f
∗
2
E
，这就很好办了，使用一个循环，依次计算frac的每一位即可。
int floatFloat2Int(unsigned uf) {
int sign = uf >> 31;
int exp = (uf >> 23) & 0xff;
int frac = uf & 0x007fffff;
int E;
int cnt;
int abs;
if (exp < 127) {
return 0;
}
else if (exp > 157) {
return 0x80000000u;
}
E = exp - 127;
//2^E * M
cnt = -23;
abs = 1 << E;
while (frac > 0) {
abs += (cnt + E >= 0) ? (1 << (cnt + E)) : 0;
cnt++;
frac >>= 1;
}
return !sign ? abs : ~abs + 1;
}
5.floatPower2
/*
* 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
*/
大意：返回2^x的位级表示
也是一系列的特判，计算float可以表示的范围。
①最小的边界值为
2
E
=
2
−
23
−
126
=
2
−
149
2^E=2^{-23-126}=2^{-149}
2
E
=
2
−
2
3
−
1
2
6
=
2
−
1
4
9
，所以x<-149时直接返回0
②最大的值为
2
254
−
127
=
2
E
−
127
2^{254-127}=2^{E-127}
2
2
5
4
−
1
2
7
=
2
E
−
1
2
7
，所以x>127时返回一个正无穷就行
③这时再来计算最小的规格化值，也就是exp等于1，frac=0时x的边界值。这时十进制是
2
1
−
127
=
2
−
126
2^{1-127}=2^{-126}
2
1
−
1
2
7
=
2
−
1
2
6
,所以当x<-126时，exp=0，frac=-x
④最后的情况就是exp!=0了，这时位数frac=0，由于
2
x
=
2
e
x
p
−
127
{2^x = 2^{exp-127}}
2
x
=
2
e
x
p
−
1
2
7
,所以exp = x+127，通过掩码操作和移位，得到exp部分的位表示。
unsigned floatPower2(int x) {
unsigned sign = 0x0;
unsigned exp;
unsigned frac;
if(x < -149) return 0;
else if(x > 127) return 0x7f800000u;
else if( x < -126 ){
exp = 0x0;
frac = ~x + 1;
}else{
frac = 0x0;
exp = ((x + 127) & 0xff) << 23;
}
return sign | exp | frac;
}
运行结果
舒服了
小结
这个实验写了两天，文章写了一天(猝。有部分题还是有难度的。推荐vscode上的一个插件Romote-SSH，通过这个插件连接远程服务器，直接在vscode上写的。
剩下的部分和书接下来再看，有一说一csapp这本书真有意思，接下来再继续完成bomb实验。