CSAPP - Data Lab
前言
看到网上对这个实验讲解的不是很详细,个人将其中的一些部分进行了细化方便大家理解与学习,如有不对处还请多多指正。
第一题
用&
和~
在 14 个字符以内实现异或
1 |
|
求解方式有如下 3 种方式:
1 |
|
可以用这三种方式表示异或操作,具体的推导可以自行Google。答案如下:
1 |
|
第二题
题目要求返回最小二进制补码整数,
1 |
|
我们已知最小的二进制补码数是-2147483648
其对应的二进制位是1000000...
,所以我们直接将 1 进行左移即可得到。答案如下:
1 |
|
第三题
题目要求如果是补码的最大数返回 1 ,否则返回 0
1 |
|
我们知道011111.....
表示的是补码的最大二进制位,如果我们对其加 1 可以得到10000000....
再取一次反便可以得到原来的最大补码。同时由于一个数异或本身为 0 ,我们便可以利用个性质来代替等号的判断,于是我们有对应的如下思路:
1 |
|
题目中并没有允许?:
的使用,于是我们可以换一种方式来实现这个过程:
1 |
|
上述的结果并不完全正确,如果我们输入的数字是1111111...
那么再经过上述操作过后,会再次变回该数字,因此我们要判断这个特例
1111… + 1 = 0000…
~ 0000… = 1111…
我们这里引入一个概念规格化数据:!! x
1 |
|
同时我们利用&
运算符的特性,一个数与 0 进行与运算的结果都是 0 ,来判断特殊数据1111...
,我们构造如下式子来进行判断特殊数据:
1 |
|
如果输入值是1111...
那么其值是 0 ,其他情况下返回值为 1
于是我们可以写出对应解:
1 |
|
第四题
题目要求判断所有二进制偶数位是否都为 1 ,如果是返回 1 否则返回 0
1 |
|
我们从题目中了解到最大长度的二进制位长 32 ,我们注意到:一个特殊的数据101010....
与一个数进行&
运算得到的结果如果与101010....
本身异或等于 0 时则证明了该数的二进制偶数位上全是 1 。
对此我们需要101010....
来帮助我们进行判断,但是题目中不允许我们直接定义,于是我们将A ( 1010 )
进行变换得到0xAAAAAAAA
1 |
|
通过上述方式我们构造出来了0xAAAAAAAA
,于是我们可以进行相应的运算了,答案如下:
1 |
|
第五题
题目要求返回输入数据的负数
1 |
|
一个数x
,-x
为其补码,所以我们对x
取反码后加一,得到的便是其所对应的负数
A + ~A = -1
和A + neg A =0
利用这两个式子我们可以得到neg A = ~A + 1
所以答案为:
1 |
|
第六题
题目要求如果输入的ASCII
在字符0 - 9
之间就返回 1 否则返回 0
1 |
|
我们先把0x30
和0x39
转为二进制可以得到:110000
和111001
我们试想一下如果我们输入的二进制位数是大于 6 位时那必定在右移六位后是不为 0 的,如果是小于或者等于 6 位时,那么得到的结果便是 0 ,我们引出第一个判断条件,来进行判断其二进制位数:
1 |
|
接下来我们观察在这个 6 位的二进制位中两个数的开头均为0x11XXXX
,于是我们再将输入的数据进行右移 4 位来与000011 ( 0x3 )
进行异或来判断是否相等,得到第二个判断条件:
1 |
|
接下来我们需要判断的便是后 4 位的二进制位,我们如何得到后 4位的二进制数呢?我们利用&
同为 1 下结果才为 1 的性质与0xf ( 1111 )
来进行运算,得到的便是后 4 位二进制位。得到后 4 位的二进制位后我们需要的便是比较大小范围了,0x30
与0x39
取完后 4 位二进制位后分别为 0000
和1001
,题目中可使用符号并没有给出减号,需要我们自己构造一下。
1 |
|
我们试想一下我们的二进制最大为1001 ( 9 )
如果我们减去一个1010 ( 10 )
是小于 0 的那么是不是我们所需要的数据范围?那么我们便可以写出最后一个判断表达式:
1 |
|
如果减出来的值是一个负数那么得到的便是1111...
,我们需要再次处理,将其右移 31 位( 因为输入最大二进制位为 32 )
得到其符号位 1 ,如果减出来的数大于等于 0 其符号位为 0 ,因此我们利用符号位来判断计算结果。
1 |
|
于是我们将上面 3 个条件组合进行判断便可以得到对应的答案了:
1 |
|
第七题
题目要求我们实现一个三目运算符? :
1 |
|
三目运算?:
中我们需要判断的便是x
的值是否为 0 ,为 0 时取z
的值,反之取y
的值。那么有没有一种方式让我们取值时根据x
的值进行返回1111...
或0
,让我们直接利用&
运算直接取到z
或y
?
事实上是有的,之前我们介绍过了!!
规格化一个数,如果这个数是一个 0 返回的便是 0 ,在其他情况下返回值是 1 。由于在程序中singed ( 有符号数 )
执行的是算术右移 ( 填补符号位 ),而输入的最大的二进制位长 32 ,我们可以利用上述性质来进行转换出一个根据x
变化而变化的数据而分别取到y
或z
的值。
1 |
|
第八题
题目要求我们返回x
和y
的大小关系,如果x<=y
返回 1 否则返回 0
1 |
|
这个题目中如果我们直接采用x-y
的方式来编写的话,可能会造成溢出现象,我们需要考虑的是x
和y
两者的符号,分多种情况进行讨论。
我们先看x==y
的情况,在这个情况下我们返回的是 1 ,我们可以用异或实现这个判断,如果是 0 则两数相等:
1 |
|
第二个情况我们考虑x
为+
,y
为-
,此时我们的返回值一定是不成立的,那么要怎么判断呢?我们利用x
和y
的符号位来进行判断数据:
1 |
|
同理当x
为-
,y
为+
时:
1 |
|
第三个情况是两个同号时:
1 |
|
我们把上面的情况合并在一起可以得到答案:
1 |
|
第九题
题目要求我们实现!
运算
1 |
|
对于这个题目我们需要想到的是 0 的符号位在取反前后都是 0 ,而对于一个其他不为 0 的数,在取反前后的符号位是不一样的,我们便利用这个特性来实现!
:
1 |
|
第十题
题目要我们求一个数的补码最小需要的位数
1 |
|
根据题目要求我们先来判断以下这些数的值:
1 |
|
可以看到表示一个负数时我们需要去除前面的多个 1 ,来确定表示这个数所需要的对应位数多少。同时如果输入的数据是 0 时,我们需要一个判断,来检测输入的数据是否为 0 ,如果是 0 那就可以直接返回 0 .
我们先对 0 的判断进行实现:
1 |
|
而对于负数的符号位的个数进行判断我们需要去取其符号位,输入的二进制位最大为 32 位,所以我们将输入的数字进行左移 31 位,得到的便是其符号位。
1 |
|
此时我们已经拥有了输入数据的符号位,我们还需要拿到输入 x 的高位,在一般其情况下我们输入的是一个正数时只需要去取出其最高位后加上一个符号位 0 ,而对于一个负数,我们需要去除前面的一连串 1 ,得到一个值的最高位为 0 ( 即其除去多余 1 后的数据 ),再加上一个符号位便是表示所需要的位数。有如下实现:
111110111 对于这个负数我们去除多余的 1 直到遇到 0 时,在加上 1 ( 代表其符号位 )
0111 ——> 4 + 1 = 5
1 |
|
我们假设一下,上面输入的一个数x
是一个正数,那么有flag = 0
,对于上式我们可以发现得到的新x
是原来的x
值即没有改变x
,我们如果输入的是一个负数,那么有flag = 1
而x
在取反后前面多余的 1 恰好变成了 0 ,而 0 变成了 1,方便我们判断对应第一个 0 的位置。
我们已经得到了这个数的最高位,接下来需要的便是计算对应表示其二进制位个数的多少。
我们输入的数据最大的二进制位长度为 32 ,我们将其不断二分来进行判断是否需要对应长度的二进制数。
1 |
|
此时我们已经拥有了输入值为 0 时的需要的二进制位和非 0 时的二进制位的个数,那么我们怎么把他们合并呢?
我们此时还是根据输入的符号位来进行处理,我们试想输入一个 0 ,那么其符号位恒为 0 ,不论在左移还是右移过程中都是不变的,而当输入一个非 0 数时,在右移过程中会有算术右移的出现,我们通过移动符号位来得到一个全为 1 ( 长 32 位 )的二级制数。那么我们在返回值时可以采用生成的全为 1 的这个数来保留我们的isZero
,同时确保我们的result
不会覆盖掉得到的答案,我们有如下定义:
1 |
|
把上述综合一下便是所需答案:
1 |
|
第十一题
题目要求返回表达式 2*f
的位级等效值
1 |
|
开始前先插入一些关于浮点数的概念:
浮点数的相关二进制位的权重如图:
但是这个方式无法表示较大的数据,在
IEEE
中我们引入一个新的方式来进行表示:
s
:符号位 |exp
: 阶码 |frac
:小数字段其中数值大致可以分为三类:
规格化的值
当阶码的二进制位不全为 0 ,且不全为 1 时,此时表示的是规格化的值。
对于图中
E
的值并不是解码所对应的值,而是需要其减去一个偏置,对于float
和double
的偏置是不相同的,则以float
为例,其最小最大 E 值如下:$E_{min}=-126\ \ \ \ | \ \ \ \ E_{max}=127$在小数字段上,尾数 M 被定义为
1+f
,尾数的二进制表示如图:因为我们可以调整 E 的取指,使得尾数 M 的取值范围大于等于 1 ,小于 2 ,既然第一位总是一,那么就没有必要显示的表示出来,这也就是为什么尾数 M 的值需要加一。
非规格化的值
当阶码的二进制位全为 0 时,此时表示的是非规格化的值。其大概有两个用途,其一是表示 0 ,其二是表示非常接近 0 的数。
若表示非常接近 0 的数,则阶码字段全为 0 ,阶码 E 的值等于
E = 1 - bias
, 尾数 M 的值是 f( M = f )
。+0.0 和 -0.0 在某些方面认为时不同的,而在其他方面是相同的。
特殊值
当阶码的二进制位全为 1 时,表示的数值是特殊值。特殊值分为两类,一类表示无穷大或者无穷小,另外一类表示不是一个数。
如我们输出下列数据,得到的返回值便是
NaN (不是一个数)
,如:$\sqrt{-1}\ \ \ \ | \ \ \ \ \infty-\infty$
了解完后题目中所给出的数据是float
类型,那么我们分别去取出其s
、exp
、frac
,便有如下计算过程:
1 |
|
第十二题
题目要求将浮点数转换为整数
1 |
|
与上面一个题相似,我们分别去取出其s
、exp
、frac
,便有如下计算过程:
1 |
|
第十三题
题目要求返回对应数等于 2 的x
次阶乘
1 |
|
对于这个题目我们需要先找到对应的范围来进行判断
对于非规格化的数:
1 |
|
对于规格化的数:
1 |
|
对此我们可以写出如下操作:
1 |
|