深入理解计数机系统Datelab实验报告（超详细）

前言

面对有着计算机神书之称的《深入理解计算机系统》的第一个开篇实验Datelib，身为小白的我肯定是即惶恐又期待的，其实第一次了解这本书是在大一下临近期末的时候在知乎博主的推荐下去网路上找了这本书的电子版看的，但由于基础知识的缺乏抱着这本书啃的过程其实是举步维艰的甚至于跟着听CMU的课程也只是一知半解，后来就放弃挣扎了🤣

然后，现在过去一学期补充了相关的前置背景知识（计算机组成原理、linux系统入门），然后借着镜像计划这个契机正好算是挽回一下先前的遗憾吧~

实验准备

下载必要文件并解压

测试编译文件时发生了这样的错误提示：

1
2
3

/usr/include/gnu/stubs.h:7:27: 致命错误：gnu/stubs-32.h：没有那个文件或目录
 # include <gnu/stubs-32.h>
                           ^

搜索后发现是由于64位机上未安装32位的glibc库文件，于是安装了相应的库文件

1	sudo yum install glibc-devel.i686

由于编译的过程会经常用到make和make clean指令，所以方便起见就直接编写脚本run.sh用于测试数据通过量（注意修改权限为可执行）
1
2
3
4
#/bin/bash
make clean
make btest
./btest
运行脚本测试，发现总通过量为 Total points: 0/37确定脚本无误

正式实验

实现1 bitXor( int x, int y)

解题思路：

通过样例我猜想：结果应该是以 ~x&y 的形式存在的，然而一跑起来就一发入魂（bushi 😂）然后看了错误样例大概是x = 1000B, y = 0111B的时候跑错了
然后经过简单分析后得到了这样的式子 (~x&y)+(x&~y)，测试了一下发现跑过了（显然老爷子的测试工具没有对每一个实现去限制操作符，然后被我偷桃成功了，ps：后面发现dlc这个工具，好吧老爷子yyds 😂）
然后考虑到这里的+运算符是起到了|的作用的，于是转为去使用&和~去实现|运算的功能，简单罗列真值表后发现~((~x) & (~y))的作用等价于x|y于是进一步改进得到最终答案~(~(~x&y)&~(x&~y))
跑测试后得到Total points: 1/37，最终用到了8个操作符解决问题😁

实现2 tmin(void)

解题思路：

由补码的权值分配我们可以发现32位整型变量的第32位代表着最小的权重即 $-2^{31}$ 于是我们就可以得到最小补码为1<<31
测试通过Total points: 2/37，用到1个操作符解决问题

实现3 isTmax(int x)

解题思路：

由补码的权值分配我们知道了32位整型变量只有第32位权值为负也就是最大的补码就是最小补码取法~(1<<31)
判断一个数是否与最大补码相同这里想到了之前实现的异或操作，只要把x与最大补码异或一下就可以判断该数是否与补码相同了x^~(1<<31)
然而我们可以发现虽然得到了判断是否相同的方法，但是如果按照前述的计算方案往年可以发现如果x就是最大补码那么返回值就是0而其他情况则会返回非零值，这就与题目要求的需要返回1和0相违背了😬
正当我在思考这么吧0映射到1，把非0映射到0的时候发现题干给出了!运算符，这就正好符合我们的要求，于是得到了结果为!(x^~(1<<31))😆
然而，我万万没想到用dlc跑过之后发现老爷子居然禁掉了移位操作 😅
于是想到了最大补码加一会转换为最小补码的情况，这样就可以做到自产自销了于是进一步改进代码为!(x^~(x+1))
但是这样就会引进特殊情况也就是当x = -1时，这也正好能通过故加上限制条件!((x^~(x+1))|!(x+1))
受此启发还得到了另一种变形的答案!(~(x+x+1)|!(x+1))这个实际上得出x = -1才是正常的结论（~(x+x+1)的用意是得到x+x+1 = -1化简得到了x = -1）但是由于补码的特殊性才会让最大补码也能混入然后排除了x = -1就得到了想要的结果
测试通过Total points: 4/37，用到7个操作符解决问题

实现4 allOddBits(int x)

解题思路：

一开始实验的时候理解错了，原来老爷子的数永远是从0开始的🤣
更正后想到对于一个奇数位完全为1的数如果补齐他所有的偶数位就会得到一个很规范的数0xffffffff就可以用于判断操作了，这时通过初步判断得到了这样的式子 !(~(x|0x55555555))，跑测试后是可以通过的

但是我隐约记得前面有限制不能定义超过一个字节的常量，翻到前面确认确实如此，只能另寻他法了😥

1 2	Each "Expr" is an expression using ONLY the following: 1. Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff.

然后想到通过一个字节的这个常数逐步构建出来我们需要的0x55555555，于是便得到了

int allOddBits(int x) {
    int t = 0x55;
    t = (t<<8)+t;
    t = (t<<16)+t;
    return !(~(x|t));
}

貌似这次不能一行搞定了🤣

测试通过Total points: 6/37，用到7个操作符解决问题

实现5 negate(int x)

解题思路：

根据补码的权值分配情况还是很容易想到这个的（bushi），印象中老爷子在讲整数补码的时候有提到过，然后学校上课的时候也提到了两种整型补码求负的方法：一种时取反加一(~x)+1；另一种时保持第一个出现的一及以前的数不变后面的数取反（一般用于人工计算），然后就得到最后的结果了(~x)+1
测试通过Total points: 8/37，用到2个操作符解决问题

实现6 isAsciiDigit(int x)

解题思路：

这个题类比到了符号位的溢出判断当这个数是在0x30 ~ 0x39之间时，如果加上一个0x06的话还会保持在0x36 ~ 0x3f之间，但是如果是在0x3A ~ 0x3f之间的数就会发生溢出为0x40 ~ 0x46之间的数，这样就可以将一个在0x30 ~ 0x3f之间的数给转换为可以判断其是否在0x30 ~ 0x39之间啦，式子为((x+0x6)>>4^3) 😉
然后需要判断这个数是否在0x30 ~ 0x3f之间我们同样要用到只需要一开始就用到异或运算就可以了(x>>4^3)，最终得到结果为!((x>>4^3)|((x+0x6)>>4^3))
测试通过Total points: 11/37，用到7个操作符解决问题

实现7 conditional(int x, int y, int z)

解题思路：

一般先去想如何把x化为规整的数可以显然地得到!!x可以将所有的非零映射为1 将零映射为0这样就将判断的数字缩小到两个了
现在我们想到要将一个数的影响降到最小我们可以让这个数与上0就可以同样的要将这个数的影响完全保留就与上全1即-1，通过这里我们可以发现如果我们对刚才得到的!!x取反就正好能得到这样规整的全0和全1，于是有了这样的式子x = ~(!!x)+1就可以将x完全规整化了 😉
然后简单思考一下就可以得到这样的式子(x&y)|(~x&z)这也就是答案啦 😁
测试通过Total points: 14/37，用到8个操作符解决问题

实现8 isLessOrEqual(int x, int y)

解题思路：

要判断x与y的大小关系我们首先想到的就是作减法啦😜
然后可以看到题目是要求小于或等于时返回1，为了方便我们来判断大于
当x > y时，y-x就一定是负数即符号位为1（虽然补码没有专门代表的符号的位但我们可以姑且将唯一代表着负数权值的最高位成为符号位），当x==y或者x < y时其值符号位一定是0，然后只要得到符号位并且将其取非就可以得到结果了，因此我们就可以得到这样的式子!((y+(~x)+1)>>31)
但是这里就出现了溢出的问题，所以加上限制条件当两个数的符号不相同的时候可以直接判断!sign_x^sign_y)&(!((y+(~x)+1)>>31)其中sign_x和sign_y分别表示x和y的符号
当这x和y的符号不一致时简单罗列真值表就可以看出sign_x&(!sign_y)，然后和前面有限制式子与一下就可以得到答案了(sign_x&(!sign_y))|((!sign_x^sign_y)&(!((y+(~x)+1)>>31)))
测试通过Total points: 17/37，用到13个操作符解决问题

实现9 int logicalNeg(int x)

解题思路：

首先我们着眼容易下手的0，我们可以发现想到对0取反后就可以达到全1,所以我们就对全1进行每次对半进行与如果最终得到了1就说明这个数的每一位都是1即为取反前的0，所有得到代码
1
2
3
4
5
6
7
8
9
int logicalNeg(int x) {
x = ~x;
x = (x>>16) & x;
x = (x>>8) & x;
x = (x>>4) & x;
x = (x>>2) & x;
x = (x>>1) & x;
return x;
}
但是我大意了，右移操作居然是算术右移所以这显然得不到正确答案 😖
所以我恬不知耻地去找了一下其他前辈的做法然后得到了最终的做法😀：针对0取反得到的任为0，而其他数都会得到其对应的相反数然后将这个数与其相反数取或就一定得到的是一个负数（尽管最小补码取负后任为其本身但取或后的结果也是负的故不影响判断）然后只要移位判断其最高位即可，于是得到结果为~(x|((~x)+1))>>31&1

然后我灵光一现就想到了，其实最早的想法离成功只差一步就是将x&1即可将算数移位的影响给抵消掉了，于是有了这个差一点就超过操作符限制的答案🤣：

// int logicalNeg(int x) {
//     return ~(x|((~x)+1))>>31&1;
// }

int logicalNeg(int x) {
    x =  ~x; 
    x = (x>>16) & x;
    x = (x>>8) & x;
    x = (x>>4) & x;
    x = (x>>2) & x;
    x = (x>>1) & x;
    return x&1;
}

测试通过Total points: 21/37，用到12个操作符解决问题

实现10 howManyBits(int x)

解题思路：

看这个允许的操作符数就明白这个题属实复杂，一开始只是想着去用移位加一但是后面发现这明显会超过指令条数限制

于是想到了二分的方案：对于一个数如果是整数，那么这个数最后一个1代表着最少需要的位数，然后二分地计算如果其高16位有数字的话那么就意味着答案至少16~32之间，然后答案加16继续将前一半与后一半合并如果后一半有数字就将前一半的影响降为0如果后一半全为0那么就意味着后一半本身贡献的影响就为0就不用关注，于是可以得到这样的代码：

int x_32 = x;
int t = (~(!!(x_32>>16))+1);
ans += t&16;
int x_16 = (x_32&(~t))|(x_32>>16);

同样的操作进行多次就可以了得到这样的结果了：

int howManyBits(int x) {
    int ans = 0;
    
    int x_32 = x;
    int t = (~(!!(x_32>>16))+1);
    ans += t&16;
    
    int x_16 = (x_32&(~t))|(x_32>>16);
    t = (~(!!(x_16>>8))+1);
    ans += t&8;
    
    int x_8 = (x_16&(~t))|(x_16>>8);
    t = (~(!!(x_8>>4))+1);
    ans += t&4;
    
    int x_4 = (x_8&(~t))|(x_8>>4);
    t = (~(!!(x_4>>2))+1);
    ans += t&2;
    
    int x_2 = (x_4&(~t))|(x_4>>2);
    t = x_2&3;
    ans += t + (~(t>>1&t)+1);

    return ans+1;
}

(最后的答案+1是因为要算上符号位)

但是这样的解答还需要考虑到负数的情况，考虑负数是要找到最后一个0的情况正好与整数时候相反我们就对当x为负数时将x取反就可以得到结果啦，这时候我们可以重点考虑符号位移位的方式就可以得到这样的符号位sign = x>>31，然后很庆幸这里是算术移位如果不是的话 x 为负数我们会得到sign = 1还需要对其进行去负数，然而由于是算术移位就x为负就会得到sign = -1，x为正就会得到sign = 0这样规整的数；我们根据前面的经验就很容易得到将负数的x取反而正数的x不变的式子x_32 = (x&~sign)|(~x&sign)

int howManyBits(int x) {
    int ans = 0;
    int sign = x>>31;
    int x_32 = (x&~sign)|(~x&sign);
    int t = (~(!!(x_32>>16))+1);
    ans += t&16;
    
    int x_16 = (x_32&(~t))|(x_32>>16);
    t = (~(!!(x_16>>8))+1);
    ans += t&8;
    
    int x_8 = (x_16&(~t))|(x_16>>8);
    t = (~(!!(x_8>>4))+1);
    ans += t&4;
    
    int x_4 = (x_8&(~t))|(x_8>>4);
    t = (~(!!(x_4>>2))+1);
    ans += t&2;
    
    int x_2 = (x_4&(~t))|(x_4>>2);
    t = x_2&3;
    ans += t + (~(t>>1&t)+1);
    
    return ans+1;
}

其实这里最后的临界条件x_2转换改了很多次版，最后确定的思路就是罗列出四种情况

x_2	->	ans
0	->	0
1	->	1
2	->	2
3	->	2

我们可以发现只有当x_2 = 3的时候才会异常所以考虑这种状态的时候减去1即可，而有发现只有数字3的二进制第一位和第零位全为1，所以根据这个性质得到ans += t + (~(t>>1&t)+1)

最终这个有（亿）点复杂的问题就通过二分的方法解决了Total points: 25/37，共用到了42个操作符😂

副栏：值得注意的是在使用dlc工具时发生了这样的报错

./bits.c:266: syntax error
./bits.c:267: undeclared variable `x_16'
./bits.c:270: syntax error
./bits.c:271: undeclared variable `x_8'
./bits.c:274: syntax error
./bits.c:275: undeclared variable `x_4'
./bits.c:278: syntax error
./bits.c:279: undeclared variable `x_2'

原因是早期的c程序是要求所有的变量在最开头就声明好的，不允许在程序运行的中间去声明变量的所以会发生这样的错误（如果我没有记错的话这点应该是大一入学时教c语言的老师顺嘴提到的 🤣）将所有的变量声明提到开头就可以了

int howManyBits(int x) {
    int ans = 0;
    int sign = x>>31;
    
    int x_32 = (x&~sign)|(~x&sign);
    int x_16, x_8, x_4, x_2;

    int t = (~(!!(x_32>>16))+1);

    ans += t&16;
    
    x_16 = (x_32&(~t))|(x_32>>16);
    t = (~(!!(x_16>>8))+1);
    ans += t&8;
    
    x_8 = (x_16&(~t))|(x_16>>8);
    t = (~(!!(x_8>>4))+1);
    ans += t&4;
    
    x_4 = (x_8&(~t))|(x_8>>4);
    t = (~(!!(x_4>>2))+1);
    ans += t&2;
    
    x_2 = (x_4&(~t))|(x_4>>2);
    t = x_2&3;
    ans += t + (~(t>>1&t)+1);

    return ans+1;
}

最终是用到了58个操作符解决问题

实现11 float_twice(unsigned uf)

解题思路：

由于博猪对浮点数的理解有限以下的解法多少都参考了其他前辈的解法，然后加上了自己了理解写成的（别骂了别骂了🥺）
首先要对IEEE754规范下的单精度浮点数的划分有理解：

符号位阶码尾码

1位 8位 23位
然后要考虑的是一些特殊情况当阶码为0xff的时候就表示无穷大或NAN情况乘2仍然为无穷大或NAN就直接返回原数据即可，当阶码位0时就表示无穷小或0，这时就直接将尾码左移就和然后需要注意的是保留符号位即可于是写出式子(uf<<1)|(uf&(1<<31))

符号位	阶码	尾码
1位	8位	23位

排除了这些特殊情况之后就直接将阶码加一就可以得到结果啦，但是要注意的是加完之后需要判断此时的值是否为无穷大，如果为无穷大的话那么就要将尾码置零才能表示无穷大😀

unsigned float_twice(unsigned uf) {
    int exp = uf>>23&0xff;
    if(exp == 0xff) return uf; 
    if(exp == 0) return (uf<<1)|(uf&(1<<31));
    uf = uf + (1<<23);
    if(((uf>>23)&0xff) == 0xff) return uf&((0xff<<23)|(1<<31));
    return uf; 
}

测试通过Total points: 29/37，用到17个操作符解决问题

实现12 float_i2f(int x)

解题思路：

首先我们朴素的想法就是要找到这个最后一个1这样就可以确定移位的多少也就是其阶码的值，可以通过移位又可以得到尾码，而符号位只需要根据原int值的符号即可确定
这里要找到最后一个1也就需要保证这个int值是正数，然而我们由前面的经验可以知道最小补码是不能表示其相应的相反数的（取负后任然为其本身）所以我们特殊处理直接特判返回（这里有个小技巧：可以根据老爷子的判题工具直接得到正确返回，你错过一次后判题工具会给出其正确返回值😉）还有当x = 0时无法找到其最后一个1也作特判返回即可
1
2
3
4
int sign = x&(1<<31);

if(x == 0) return 0;
else if(x == sign) return 0xcf000000;
sign这个变量本来应该是用来保存x的符号的，但是可以发现的是最小补码正好满足x == sign就偷懒用上前面得到的sign啦😁
然后先根据符号值去取反确保其为正数，再根据移位去得到其最后一个1的位置就能得到阶码部分的值了，需要注意的是阶码部分的表示法是使用了移码，而样将8位补码转化为8位移码就需要加上127，（这种理解方式更原始，手算的时候其实只要将8位的补码的符号位取反即可）
1
2
3
i = 30;
while(!(x>>i)) i--;
exp = i+127;
然后将这个x对齐让最后一个1标齐到最左边，这样就可以把整个x化为整个的尾码，然后向右移8位与取后23位得到的数就是真正的尾码了（这里需要注意的是右移8位是因为最高位的1是要被舍去的这个的规范决定的，能够扩大尾码的表示范围）
1
2
x <<= 31-i;
fra = (x>>8)&0x7fffff;
最后需要注意的就是尾码舍去问题，注意这里的舍去是根据银行家舍入法进行舍入的即大于0.5就进位等于0.5要看整数部分奇偶性，奇数则进位；于是就得到了fra += (x>128 || ((x==128) && (fra&1)))，然后还要判断这个尾码加完之后是否会溢出要进位于是整体就得到了：
1
2
3
4
5
6
7
8
x = x&0xff;
del = (x>128 || ((x==128) && (fra&1)));
fra += del;

if(fra >> 23){
fra &= 0x7fffff;
exp+=1;
}

最后按顺序组合符号位+阶码+尾码返回即可，最终的结果为：

unsigned float_i2f(int x) {
    int sign = x&(1<<31);
    int exp, fra, del, i;

    if(x == 0) return 0;
    else if(x == sign) return 0xcf000000;
    
    if(sign) x = -x; 

    i = 30; 
    while(!(x>>i)) i--;
    exp = i+127;
    
    x <<= 31-i;
    fra = (x>>8)&0x7fffff;

    x = x&0xff;
    del = (x>128 || ((x==128) && (fra&1)));
    fra += del;

    if(fra >> 23){
        fra &= 0x7fffff;
        exp+=1;
    }   

    return (sign | (exp<<23) | fra);
}

测试通过Total points: 33/37，用到26个操作符解决问题

实现13 float_f2i(unsigned uf)

解题思路：

这个相对于前一个将整数转换为浮点的确实要轻松很多，毕竟整数转浮点需要考虑到更多的特殊情况 😉
首先提取出浮点数的每一个部分，有了上一题的铺垫其实这个还是很好处理的
1
2
3
int sign = uf & (1<<31);
int exp = ((uf>>23)&0xff)-127;
int fra = uf & 0x7fffff;
这里的阶码为了运算方便就减去的127使其移码的表示形式变成补码的表示形式方便计算。
然后就需要排除掉一些不能表示的部分了，根据规范浮点数的尾码用二进制表示一定是这种形式1.xxx，当其阶码大于32时就表示这个尾码经过移位一定是会超过int的表示范围的，根据要求我们返回0x80000000u即可（这里也一并考虑到了无穷大和NAN的情况），而同样的如果阶码小于0就表示为0.xxx的形式了我们直接返回0即可（这里也一并算是考虑到了浮点0的情况）于是我们有了
1
2
if(exp > 32) return 0x80000000u;
if(exp < 0) return 0;
然后补齐尾码默认的1，注意我们可以注意到现在得到的尾码其实是相当于对实际的尾码进行左移23位得到的整数形式，于是我们注意移位方向就好啦😜
1
2
3
4
fra |= 1<<23;

if(exp > 23) fra <<= exp-23;
else fra >>= 23-exp;

最后的返回值根据符号位来就好啦

int float_f2i(unsigned uf) {
    int sign = uf & (1<<31);
    int exp = ((uf>>23)&0xff)-127;
    int fra = uf & 0x7fffff;
    
    if(exp > 32) return 0x80000000u;
    if(exp < 0) return 0;

    fra |= 1<<23;

    if(exp > 23) fra <<= exp-23;
    else fra >>= 23-exp;

    if(sign) return -fra;
    return fra;
}