该实验的目的是《深入理解计算机系统》课程配套的lab实验,用于提升对计算机基础信息的理解和操作,例如位,整数,浮动,补码等等。
lab的具体内容可以在官网中下载,所有的lab代码在GitHub上。
基本要求和操作
我们需要了解的文件有:
bits.c
:我们只需在此文件中进行操作,里面有大量的注释,注释就是出题者的要求,包括你需要修改这个函数以便完成的目标、你在这个函数中所能使用的操作符种类、能使用的操作符的数目等;btest.c
:运行make后会生成可执行文件,用于测试编写的函数释放正确;dlc
:用于检测代码风格;driver.pl
:最后用于打分;fshow.c
和ishow.c
:make后可以得到两个可执行文件,分别可以输出你输入的float数和integer数的内存表示形式,比如标志位是什么,阶码是多少等。
基本的步骤就是:
- 修改bits.c函数注释与代码;
- 运行
./dlc -e bits.c
查看自己用了多少操作符,以及是否有代码风格问题; - 编译工程,并运行
./btest
检查是否做对了; - 所有的做完了,最后再运行
./driver.pl
获得打分。
题目列表如下:
名称 | 描述 | 难度 | 指令数目 |
---|---|---|---|
bitXor(x,y) | 只使用~ 和& 实现 |
1 | 14 |
tmin() | 返回最小补码 | 1 | 4 |
isTMax(x) | 判断是否是补码最大值 | 1 | 10 |
allOddBits(x) | 判断补码所有奇数位是否都是1 | 2 | 12 |
negate(x) | 不使用- 实现-x |
2 | 5 |
isAsciiDigit(x) | 判断x 是否是ASCII码 |
3 | 15 |
conditional(x,y,z) | 类似C语言x?y:z |
3 | 16 |
isLessOrEqual(x,y) | 实现x<=y |
3 | 24 |
logicalNeg(x) | 不使用! 实现!x |
4 | 12 |
howManyBits(x) | 计算补码表达x 所需的最少位数 |
4 | 90 |
floatScale2(uf) | 计算2.0*uf |
4 | 30 |
floatFloat2Int(uf) | 计算int(uf) |
4 | 30 |
floatPower2(x) | 计算2.0 x |
4 | 30 |
bitXor
根据布尔代数,异或就是当参与运算的两个二进制数结果不同时才为1,相同时为0。可以认为,异或是同时为0或同时为1的反,即x^y = ~((x&y)|(~(x|y)))
。题设只允许用~
和&
实现,而x|y = ~(~x&~y)
,所以得出x^y = ~(x&y)&~(~x&~y)
(注意C语言运算符优先级),如下:
1 | /* |
tmin
这题就比较简单了,最小的补码一定是符号位为1,其他位为0的数,所以对int(32位数)类型而言,其最小补码数就是1<<31
。
1 | /* |
isTmax
很明显对于补码来说,最大值就是符号位为0,其它位均为1的数。题设要求最大补码数时返回1,其它数返回0,且限定操作符。这时候需要联想到的就是,!0 = 1
,但是其它数取反均为0,那就是说,如果我们能将最大补码数转换为0就好了。
步骤:
- 我们假设
x
为Tmax
,即0111 ... 1111
,那么将x + 1
即得到1000 ... 0000
(注意此处不能取反得到1000 ... 0000
),即Tmin
; - 我们将
Tmin
左移1位即得到全0,但是题设不允许使用<<
,那么我们将Tmax + Tmin
再取反即得到0; - 验证其它数是否也会产生这个结果,发现如果
x = 1111 ... 1111
时,经过以上操作也会得到0,那我们需要排除这种情况,而此时x
是个特殊的数,!(~x) = 1
,其它任何数做这个操作都是0。
我们的代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14/*
* 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) {
int y = x + 1; // if x == 0x7fffffff, y = 0x80000000
x = ~(x + y); // x = 0
y = !y; // exclude if x == 0xffffffff
x = x + y; // exclude if x == 0xffffffff
return !x;
}
allOddBits
当整数的奇数位都为1时,返回1,否则返回0。这题其实很简单,直接用掩码就好了,当奇数位全为1时,如果把偶数位也全部填上1(与0x55555555
的掩码取或),那么就是0xffffffff
,这是再取反取非,即为1;如果奇数位不全为1,以上假设就不成立。代码如下:
1 | /* |
negate
取负值,这个简单,就是取反加一。
代码如下:
1 | /* |
isAsciiDigit
这题求解整数是否在Ascii码数字09(即0x300x39)。此题还是比较有难度的,我们可以使用两个数,一个数加上比0x39大的数后符号从正变负,另一个数是加上比0x30小的数时是符号,然后再判断符号位,只要有一个符号位为1,则不在此范围内。代码如下:
1 | /* |
conditional
利用限定的符号实现符号x ? y : z
的功能。逻辑如下:
- 如果
x != 0
,那么输出y,如果x == 0
,则输出z; - 如果我们能通过x的值不同转换为全0或者全1的掩码,那输出就很容易的;
代码如下:1
2
3
4
5
6
7
8
9
10
11/*
* 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) {
x = ~!x + 1; // if x == 0, ~!x + 1 = -1(0xffffffff); if x != 0, ~!x + 1 = 0
return (~x & y) | (x & z);
}
isLessOrEqual
本题是利用限定的运算符实现≤
,其实对比两个数的大小,无非就是符号相同看差值符号,符号不同正数为大。
代码如下:
1 | /* |
logicalNeg
本题是取非操作,我们知道,0的非是1,其它数的非是0。那么就是要找出0和其它数的不同,而0最大的不同就是-0 = 0
(但是有另一个例外就是-Tmin = Tmin
),且0的符号位和-0的符号位是相同的,均为0,而其它数的符号位和负值符号位不同(除了Tmin,Tmin的符号位和-Tmin的符号位都是1),利用这个特性,可以将0和其它数区别开来;而针对补码的右移是算数右移,即当符号位是0时,右移31位将得到0,当符号位是1时,右移31位将得到-1(全1),此时再+1,即得到0和1两个值。代码如下:
1 | /* |
howManyBits
如果是一个正数,则需要找到它最高的一位(假设是n)是1的,再加上符号位,结果为n+1;如果是一个负数,则需要知道其最高的一位是0的(例如4位的1101和三位的101补码表示的是一个值:-3,最少需要3位来表示)。代码如下:
1 | /* howManyBits - return the minimum number of bits required to represent x in |
floatScale2
接下来三题都是考察对浮点数的掌握程度。
本题的意思是用int类型表征出浮点数2*f
的形式,且输入输出都要用无符号整数表时。其实最重要的就是要掌握浮点数的表达形式:(-1)s*M*2E。
- 当阶码域全0的时候(即非规格化的值),此时M = f,我们左移f,即可得到2*uf值;
- 当阶码域不全为0,且非全1的时候(即规格化的值),我们将阶码值加1即可得到(-1)s*M*2E+1 = 2((-1)s*M*2E);
- 当阶码域全1时,值为无穷大或者NaN,此时直接返回uf即可,因为操作无意义。
1 | /* |
floatFloat2Int
本题考查int(uf)
,其实重点还是对浮点编码(-1)s*M*2E理解,具体解析的步骤在注释中。
1 | /* |
floatPower2
这题求解的是2.0x。分析如下:
- 首先我们要知道float类型的精度是多少,也就是最小的非规格化值是V=2-n-2k-1+2=2-149。
- 当x<-149时,2.0x超出了浮点数的表达精度,这时返回0;
- 当-149≤x≤-127时,这时2.0x只有小数部分(即非规格化的值),那我们只需要将1左移149+x位即可;
- 当-127<\x<128时(即规格化的值),即将阶码编码值(x+127)左移23位即可;
代码如下:
1 | /* |
结果
运行结果如下:
1 | $ ./btest |
小结
总体来说,data-lab不算特别的困难,只是有些地方想不到就会很难,但是一般通了以后就是一通百通了,看起来有些奇淫巧计,其实对于补码和浮点数的认知还是有很大的帮助的。