CSAPP Data Lab

Data Lab的内容是仅采用有限制的位运算符实现一些函数。

bitXor

实现按位异或。

\(x\oplus y = (x\wedge \neg y)\vee(\neg x\wedge y)=\neg(\neg(x\wedge \neg y)\wedge\neg(\neg x\wedge y))\)

1
2
3
4
int bitXor(int x, int y)
{
return ~(~(~x & y) & ~(x & ~y));
}

tmin

计算\(T_{min}\)

其位级表示为0x80000000,即1 << 31

1
2
3
4
int tmin(void)
{
return 1 << 31;
}

isTmax

判断\(x\)是否是\(T_{max}\)

\(T_{max}\)和-1均满足\(\neg x = x + 1\),判断\(x\)\(y\)相等可以用!(x ^ y),判断不为-1可以按位取反之后取两次非(不取两次非的话可能会取到\(>1\)的值)。

1
2
3
4
int isTmax(int x)
{
return !(~x ^ (x + 1)) & !!~x;
}

allOddBits

判断\(x\)的奇数位上是否都为1。

\(x\)的每个字节都或0x55,如果奇数位上都为1的话会得到0xFFFFFFFF也就是-1,之后判断是否为-1。

1
2
3
4
5
6
int allOddBits(int x)
{
int y = 0x55;
int z = (y << 24) | (y << 16) | (y << 8) | y | x;
return !~z;
}

negate

计算\(x\)的相反数。

取反+1,书上有写。

1
2
3
4
int negate(int x)
{
return ~x + 1;
}

isAsciiDigit

判断\(x\)是否在0x300x39之间。

\(x\)右移四位,必须和3相等,之后\(x\)的(低位起)第4位为0,或者第4位为1并且第2、3位为0。

1
2
3
4
5
6
int isAsciiDigit(int x)
{
int y = x & 0xF;
int z = x >> 4;
return !(z ^ 3) & (~(y >> 3) | !((y >> 1) & 3));
}

conditional

实现x ? y : z

首先通过\(x\)计算\(a\),如果\(x\)不为0则\(a\)0xFFFFFFFF,否则\(a\)为0。观察得到a = !x - 1。之后利用0xFFFFFFFF & x == x0 & x == 0即可。

1
2
3
4
5
int conditional(int x, int y, int z)
{
int a = !x + ~1 + 1;
return (~a & z) + (a & y);
}

isLessOrEqual

判断x <= y

一般来说计算y - x,判断符号位为0即可,对于溢出的情况,比较\(x\)\(y\)的符号位,如果\(x\)为负并且\(y\)非负,则答案必为1,如果\(x\)非负并且\(y\)为负,则答案必为0。

1
2
3
4
5
6
7
int isLessOrEqual(int x, int y)
{
int a = (x >> 31) & !(y >> 31);
int b = !(x >> 31) & (y >> 31);
int z = y + ~x + 1;
return a | ~b & !(z >> 31);
}

logicalNeg

实现!x

~0 == -1,即检查~x的每一位是否都为1。

1
2
3
4
5
6
7
8
9
int logicalNeg(int x)
{
int a = ~x;
int b = (a >> 16) & a;
int c = (b >> 8) & b;
int d = (c >> 4) & c;
int e = (d >> 2) & d;
return (e >> 1) & e & 1;
}

howManyBits

以补码方式表示\(x\)的最小位数。

注意非负数需要以符号位0开头,负数的位数是取反后的位数加上一个符号位。

首先根据利用之前的条件判断计算\(y\),如果\(x\)是非负数,y = x,否则y = ~x

答案初始为1(符号位),之后不考虑符号位看表示\(y\)需要多少位即可。

对于答案的每一位,看它是1还是0,比如如果答案的第5位为1,则\(y\)的长度大于16,即y >> 16不为0,下一步迭代\(y\)的高16位,反之迭代\(y\)的低16位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int howManyBits(int x)
{
int a = 1;
int k = ~1 + 1;
int t = !((x >> 31) & 1) + k;
int y = (t & ~x) + (~t & x);
t = !(y >> 16) + k;
a += t & 16;
y = (t & (y >> 16)) + (~t & y & ((0xFF << 8) | 0xFF));
t = !(y >> 8) + k;
a += t & 8;
y = (t & (y >> 8)) + (~t & y & 0xFF);
t = !(y >> 4) + k;
a += t & 4;
y = (t & (y >> 4)) + (~t & y & 0xF);
t = !(y >> 2) + k;
a += t & 2;
y = (t & (y >> 2)) + (~t & y & 3);
t = !(y >> 1) + k;
a += t & 1;
y = (t & (y >> 1)) + (~t & y & 1);
a += y;
return a;
}

floatScale2

计算2 * f

根据规格化、非规格化、特殊情况三种来判断,注意非规格化转化到规格化和规格化溢出的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned floatScale2(unsigned uf)
{
int s = uf & 0x80000000;
int exp = (uf >> 23) & 0xFF;
int frac = uf & 0x7FFFFF;
if (exp == 0xFF)
return uf;
if (!exp)
{
if (frac >> 22)
return s | (1 << 23) | ((frac << 1) & 0x7FFFFF);
return s | ((frac << 1) & 0x7FFFFF);
}
if (exp == 0xFF - 1)
return s | (0xFF << 23);
return s | ((exp + 1) << 23) | frac;
}

floatFloat2Int

浮点数转整数。

非规格化的数返回0,特殊情况返回\(T_{min}\);规格化的指数\(E<0\)的情况返回0,\(E>31\)的情况返回\(T_{min}\),其余的情况正常计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int floatFloat2Int(unsigned uf)
{
int s = uf >> 31;
int exp = (uf >> 23) & 0xFF;
int frac = uf & 0x7FFFFF;
if (exp == 0xFF)
return 0x80000000u;
s = s ? -1 : 1;
if (!exp)
return 0;
if (exp >= 127)
{
if (exp <= 157)
return s * (1 << (exp - 127)) * ((frac >> 23) + 1);
return 0x80000000u;
}
else
return 0;
}

floatPower2

计算\(2.0^x\)

最小非规格化数为\(2^{-23}\times2^{-126}\),最小规格化数为\(1\times2^{-126}\),最大规格化数为\((2-\varepsilon)\times2^{127}\)

1
2
3
4
5
6
7
8
9
10
11
unsigned floatPower2(int x)
{
if (x < -149)
return 0;
else if (x < -126)
return 1 << (x + 149);
else if (x < 128)
return (x + 127) << 23;
else
return 0x7f800000;
}

总结

难度比预想大一些,尤其是整数部分的最后几道题,有很多小trick,但是感觉收获不大,可能用处比较局限。

作者

xqmmcqs

发布于

2022-01-18

更新于

2022-01-18

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×