【从零开始的新手之旅】：2023西工大计算机系统基础实验之Lab1
温馨提示*擅长运用人工智能技术，遇到不解之处可随时向AI寻求解答。*尽管我的代码能获取步数得分和答案得分，但在解题步骤的精简度上明显逊色于教师示范，因此，我建议大家不宜完全参照我的解答步骤，其他博主的答案更具有参考价值。*由于未充分考虑评价标准、虚拟机系统等各种潜在影响因素，答案可能存在局限性，并不能确保在所有情况下都适用。
实验要求
实验所用
*ChatGPT(24小时贴心解惑专家、自学好帮手，不好意思问助教和老师的问题可以问它，想问的问题也可以先问它。如果没有魔法，可以用国内著名的大语言模型代替)
*DeepL翻译（bits.c文件开头有一大段英文注释，还有每个函数的实现要求也是英文，如果跟本人一样英语水平一般，可以用这个翻译为中文，结果还蛮准确的）
*在Linux终端里输入“make btest./btest”（当认为一个函数没问题却一直报错时可以用这个方法找到出错的测试用例。说实话，这比NOJ良心多了，要是不知道这个我也做不出来）
可以得到类似于这样的报错信息：
*姜学锋、刘君瑞编著的《C程序设计》（我主要是用它来查看与、或、异或以及位移等运算符的规则，比如1 | 0=1，以及借鉴教材里给出的这些运算符的常见用法）
*不断试错与纠正的耐心（？？）
实验思考与结果
2015 CMU 15-213 CSAPP 深入理解计算机系统 课程视频中在讲解二进制补码时提到了一个令我印象深刻的理解方式：“我们可以通过2的幂之和来计算原码对应的十进制数。而对于补码，只需将最高位的二进制数视为负数，其他位仍视为正数再相加即可”,例如 二进制补码“11111”转化为十进制数可以这样做：“-16+8+4+2+1=-1”。
/*
* tmin - 返回最小的二进制整数
* 合法运算符: ! ~ & ^ | + << >>
* 运算符数量最大值: 4
* 分值: 1
*/
int tmin(void) {
int a=1;
return a<<31;
}
我这题我是先要求AI给我适当的提示，然后我再根据提示思考得到的。虽然这多少有些画蛇添足，但正是这题给了我一个启发：“如果这道题可以使用选择结构，它就会变得非常简单，因为我们可以根据输入数据的不同特征进行不同的操作。但是因为只能使用顺序结构，所有我们必须使用相同的操作来达到不同的效果。也就是说我们输入数据时，必须把数据的特征也一并量化作为参数，然后再通过对数据和参数进行各种操作来达到目的。这也许可以迁移到其他题目上。”
例如“ x1=x>>31;”如果x为非负数，x1=0；反之x1=-1。之后x与x1之间一系列的运算就是通过x1的不同才能根据x正负性得到不同的结果。
/*
* absVal - x的绝对值
* 样例: absVal(-1) = 1.
* 你可以假设 -TMax <= x <= TMax
* 合法运算符: ! ~ & ^ | + << >>
* 运算符数量最大值: 10
* 分值: 4
*/
int absVal(int x) {
int x1=0,x2=0;
x1=x>>31;
x2=x1^x;
x1=~x1+1;
return x2+x1;
}
一开始我对与、或、异或以及位移等运算符都非常陌生，常常需要翻书查看规则来进行思考，但到最后这些运算符的运算规则全都忘不掉了，还学会用了使用这些运算符来实现常见的加减乘除运算。
/*
* bitAnd - 只使用 ~ 和 | 实现 x&y 的效果
* 样例: bitAnd(6, 5) = 4
* 合法运算符: ~ |
* 运算符数量最大值: 8
* 分值: 1
*/
int bitAnd(int x, int y) {
int a=0;
a=~x|~y;
return ~a;
}
我总是习惯于使用常见的十进制来思考问题，但是做这个实验往往需要用二进制来进行思考，因此有时可能就反应不过来，不能根据二进制数本身的特征来进行操作以达到目的。
/*
* replaceByte(x,n,c) - 用 c 替换 x 中的第 n 字节
* 字节编号是从 0（LSB）到 3（MSB）的
* 样例: replaceByte(0x12345678,1,0xab) = 0x1234ab78
* 你可以假设 0 <= n <= 3 and 0 <= c <= 255
* 合法运算符: ! ~ & ^ | + << >>
* 运算符数量最大值: 10
* 分值: 3
*/
int replaceByte(int x, int n, int c) {
int i=0,j=255,k=0;
i=n<<3;
j=j<<i;
j=~j;
j=x&j;
k=c<<i;
return k+j;
}
下面这三道题我并不清楚具体的原理，我只知道计算机乘除的实现与位移运算关系密切，因此我就先用合法运算符基本复现出乘除的功能，确保大多数样例能通过检测。然后我再使用“make btest./btest”查看是哪个特例出错，接着根据错误的结果来 “拆分或合并实现乘法或实现除法的代码”，或者 “调整乘除的顺序 ”，抑或 “添加一些额外步骤把特例的特征量化并进行各种操作 ”来达到“订正特例的结果但其余样例结果不变” 的目的。不得不承认，这需要多次反复地进行实验。
/*
* mult3div2 - 给出x乘以3/2后的结果，结果向0舍入
* 应完全复现 C 表达式 (x*3/2) 的效果，
* 也包括溢出行为。
* 样例:mult3div2(11) = 16
* mult3div2(-9) = -13
* mult3div2(1073741824) = -536870912(overflow)
* 合法运算符: ! ~ & ^ | + << >>
* 运算符数量最大值: 12
* 分值: 2
*/
int mult3div2(int x) {
int a=0,b=0;
a=x<<1;
a=a+x;
b=a>>31;
b=~b+1;
a=a+b;
return a>>1;
}
/*
* multFiveEighths - 给出x乘以5/8后的结果，结果向0舍入。
* 应完全复制 C 表达式 (x*5/8) 的效果，
* 包括溢出行为。
* 样例：multFiveEighths(77) = 48
* multFiveEighths(-22) = -13
* multFiveEighths(1073741824) = 13421728（溢出）
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 12
* 分值： 3
*/
int multFiveEighths(int x) {
int a=0,b=0;
a=x<<2;
a=a+x;
b=a>>31;
b=~b+1;
a=a+b;
a=a>>1;
a=a+b;
a=a>>1;
a=a+b;
return a>>1;
}
/*
* trueFiveEighths - 给出x乘以5/8后的结果，结果向0舍入，避免因溢出而出错。
* 样例：trueFiveEighths(11) = 6
* trueFiveEighths(-9) = -5
* trueFiveEighths(0x30000000) = 0x1E000000（无溢出）
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 25
* 分值： 4
*/
int trueFiveEighths(int x)
{
int a=x>>1,b=x>>31,c=x>>3,d=x&1,e=x&7,f=!e;
d=d<<2;
e=e+d;
e=~e+8>>31;
f=f|!b;
return a+c+!!e+!f;
}
这道题需要分为 正+正、负+负，负+正 三类情况，根据从“absVal - x的绝对值”得到的启示，我们需要先量化不同情况下溢出与未溢出的特征并将之储存在参数中，例如正+正未溢出得正，溢出得负；负+负未溢出得负，溢出得正。但真正的难点在于找到符合要求的对数据和参数进行的一系列操作。单一的& 、^ 、|都无法满足要求，我的做法是尝试各种运算符的各种组合，尤其要注意& 、^ 、|之间的组合运算。
为了理清思路我会列出一个表格，它包含不同情况下各个参数的值，值得一提的是，我的参数最终往往都会变为0，1或-1这样简单的数。然后我再将这些数之间& 、^ 、|的单独及组合运算的结果写在旁边，来对照着思考并反复尝试。虽然这一过程听起来颇为艰辛，然而作为从零开始的新手，我也很无奈。
/*
* addOK - 确定能否在不溢出的情况下计算 x+y
* 样例：addOK(0x80000000,0x80000000) = 0、
* addOK(0x80000000,0x70000000) = 1、
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 20
* 分值： 3
*/
int addOK(int x, int y) {
int d=0,e=0,f=0,g=0,h=0;
d=x+y;
d=d>>31;
e=x>>31;
f=y>>31;
g=e|f;
h=e^f;
g=d+g+h+1;
return !!g;
}
这两题是相互联系的。它们跟上一题有相似之处，也是需要分类讨论，量化特征以及尝试组合运算，最好也要列表格或画出流程图。但多了用~ 、！等运算符调整参数、中间量或结果的值这一步，比如按位取反再+1可以取到相反数；！可以把非零数变为0，而0变为1；！！可以把非零数变为1，而0仍为0。这是为了便于找到能得到正确结果的操作。
/*
* isLess - 如果 x < y 则返回 1，否则返回 0
* 样例：isLess(4,5) = 1。
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 24
* 分值：3
*/
int isLess(int x, int y){
int a=0,b=0,c=0,d=0,e=0;
a=~x;
b=a>>31;
c=y>>31;
a=a+y;
a=a>>31;
d=b|c;
e=b^c;
e=a+d+e+1;
a=a+!e;
return !a;
}
/*
* isLessOrEqual - 如果 x <= y 则返回 1，否则返回 0
* 样例：isLessOrEqual(4,5) = 1。
* 合法运算符：! ~ & ^ | + << >>
* 最大操作数 24
* 分值： 3
*/
int isLessOrEqual(int x, int y) {
int a=0,b=0,c=0,d=0,e=0;
a=~y;
b=a>>31;
c=x>>31;
a=a+x;
a=a>>31;
d=b|c;
e=b^c;
e=a+d+e+1;
a=a+!e;
return !!a;
}
计算机取余运算的实现也与位移运算关系密切，另外这道题应该要用到之前提过的所有方法。不过我记得我刚做完时运算符的数量超标了，我之后是通过纯粹的运算层面的分析 整合与省略不必要的步骤，才最终使运算符数量小于最大值。不过问题就是几乎不存在可读性了。
/*
* rempwr2 - 计算 x%(2^n)，0 <= n <= 30，且负参数应产生负余数
* 示例：rempwr2(15,2) = 3, rempwr2(-35,3) = -3
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 20
* 分值： 3
*/
int rempwr2(int x, int n) {
int a=x>>31,b=a^x,c=~a+1+b,d=c>>31,e=~0>>n<<n;
e=~e&c^d^a;
return e+d+!!a;
}
接下来的四道题其实用非常暴力的手段就可以得到正确的答案，但是每道题目的运算符数量都被我硬生生地弄成了上百个.......因此我不得不借助外力。其中这篇文章我个人认为讲得不错，值得借鉴。
面试经典问题——统计 32 位有符号整型二进制表示中 1 的数目
这道题我是借鉴了分治法的思想优化之后得到的结果。原本我是把x统一转为正数，再通过位移查看每一位上是不是1，然后把结果累加起来，最后根据总和与符号位的值来返回结果。
“a=a^(a>>1);”这类步骤是为了得到x的前2位、前4位、前8位、前16位以及最终的32位的1的个数和的奇偶，因为1^1=0、0^0=0、1^0=1且奇+奇=偶、偶+偶=偶、奇+偶=奇，比如假设x的前两位都是1，那么即使不统计这两个1，结果的奇偶性仍然不变。可以用一个样例代入代码进行运算来理解原理。
/*
* 奇偶校验 - 如果 x 包含奇数个 1，则返回 1
* 样例：parityCheck(5) = 0, parityCheck(7) = 1
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 20
* 分值： 4
*/
int parityCheck(int x) {
int a=1<<31,b=x&a;
a=~a&x;
a=a^(a>>1);
a=a^(a>>2);
a=a^(a>>4);
a=a^(a>>8);
a=a^(a>>16);
return (a+!!b)&1;
}
下面这三道题我思考后发现它们之间存在联系，只要能得到二进制补码中 1 的个数，就能通过模仿与迁移写出其余两道题目的代码，但我发誓就算我想破脑袋我也绝对想不出来。我最终是通过阅读上面提到的文章并多次咨询AI才勉强理解并实现的（其实就是抄得不甘心[doge]）。不得不说，这种根据计算机系统与二进制的特征精心设计的并行操作与分而治之的做法对于我这种从零开始的新手未免太过超前.......
/*
* bitCount - 返回二进制补码中 1 的个数
* 样例：bitCount(5) = 2, bitCount(7) = 3
* 合法运算符： ! ~ & ^ | + << >>
* 运算符数量最大值： 40
* 分值： 4
*/
int bitCount(int x) {
int a=1<<31,b=x&a,c=85+(85<<8),d=c+(c<<16);
a=~a&x;
a=a+~((a>>1)&d)+1;
c=51+(51<<8);d=c+(c<<16);
a=(a&d)+((a>>2)&d);
c=15+(15<<8);d=c+(c<<16);
a=(a+(a>>4))&d;
a=a+(a>>8);
a=a+(a>>16);
return (a&63)+!!b;
}
/*howManyBits - 返回用二进制补码表示 x 所需的最小位数
* 示例：howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* 合法运算符： ! ~ & ^ | + << >>
* 最大操作数运算符数量最大值： 90
* 分值：4
*/
int howManyBits(int x) {
int b16,b8,b4,b2,b1,b0;
int sign=x>>31;
x = (sign&~x)|(~sign&x);
b16 = !!(x>>16)<<4;
x = x>>b16;
b8 = !!(x>>8)<<3;
x = x>>b8;
b4 = !!(x>>4)<<2;
x = x>>b4;
b2 = !!(x>>2)<<1;
x = x>>b2;
b1 = !!(x>>1);
x = x>>b1;
b0 = x;
return b16+b8+b4+b2+b1+b0+1;
}
/*
* ilog2 - 返回 floor（底数为2的x的对数），其中 x > 0
* 样例: ilog2(16) = 4
* 合法运算符: ! ~ & ^ | + << >>
* 运算符数量最大值: 90
* 分值: 4
*/
int ilog2(int x) {
int b16,b8,b4,b2,b1;
b16 = !!(x>>16)<<4;
x = x>>b16;
b8 = !!(x>>8)<<3;
x = x>>b8;
b4 = !!(x>>4)<<2;
x = x>>b4;
b2 = !!(x>>2)<<1;
x = x>>b2;
b1 = !!(x>>1);
x = x>>b1;
return b16+b8+b4+b2+b1+x+~0;
}温馨提示
*善于运用人工智能技术，遇到不解之处可随时向AI寻求解答。
*尽管我的代码能获取步数得分和答案得分，但在解题步骤的精简度上明显逊色于教师示范，因此，我建议大家不宜完全参照我的解答步骤，其他博主的文章在这方面会更具参考价值。
*由于未充分考虑评价标准、虚拟机系统等各种潜在影响因素，答案可能存在局限性，并不能确保在所有情况下都适用。
*完全依赖个人的独立摸索并非总是最优策略，如果你能得到来自同学伙伴或学长学姐的指导与帮助，那么恭喜你。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
24
0- 0
已为社区贡献2条内容
所有评论(0)