实验一 数据表示与运算实验
以下为《实验一 数据表示与运算实验》的无排版文字预览，完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。
实验一 数据表示与运算实验
一、实验目的
1．更好地熟悉和掌握计算机中整数和浮点数的二进制编码表示。
2. 加深对数据二进制编码表示的了解。
3. 使用有限类型和数量的运算操作实现一组给定功能的函数。
二、实验仪器设备/实验环境
1．Linux操作系统 —— 64位 Ubuntu 18.04
2. C编译环境(gcc)、make自动化编译工具
3. 虚拟机
三、实验内容
本实验每位学生拿到一个datalab-handout.tar文件。学生可以通过U盘、网盘、虚拟机共享文件等方式将其导入到Ubuntu实验环境中，选择合适位置存放。然后在Ubuntu环境下解压(tar -xvf …)。解压后，根据文件中的叙述和要求更改bits.c文件，其他文件不要动。本次实验的主要操作方式为：使用C语言的位操作符实现题目要求。
完成实验后提交给老师时，将自己编写的bits.c改名为“bits_学号”的形式交给学委统一收集。文件名例：bits_***.c。如果文件名出现错误，则自动评分程序不会给出分数，请务必注意！！！！
需要完成bits.c中下列函数功能，具体分为三大类：位操作、补码运算和浮点数操作。
1．位操作
表1列出了bits.c中一组操作和测试位组的函数。其中，“级别”栏指出各函数的难度等级（对应于该函数的实验分值），“功能”栏给出函数应实现的输出（即功能），“约束条件”栏指出你的函数实现必须满足的编码规则（具体请查看bits.c中相应函数注释），“最多操作符某某量”指出你的函数实现中允许使用的操作符的最大数量。
也可参考tests.c中对应的测试函数来了解所需实现的功能，但是注意这些测试函数并不满足目标函数必须遵循的编码约束条件，只能用做关于目标函数正确行为的参考。
表1 位操作题目列表
本题分数
函数名
功能
约束条件
最多操作符某某
1
isZero
判断变量x是否为0。如果为0，则返回1；否则，返回0。
仅可以使用以下操作符： ! ~ & ^ | + >
2
1
specialBits
构建0xffca3fff，并返回。
仅可以使用以下操作符： ! ~ & ^ | + >
3
1
upperBits
根据输入的变量n，构建一个高n位某某1其他位某某0的数，并返回该值。
注：0
12
4
bitParity
如果x中包含奇数个0，则返回1；否则返回0。
仅可以使用以下操作符： ! ~ & ^ | + >
20
2
byteSwap
将x的第n字节和第m字节交换，
0
20
3
subtractionOK
如果x-y没有溢出，则返回1；否则返回0。
仅可以使用以下操作符： ! ~ & ^ | + >
20
3．浮点数操作
表3列出了bits.c中一组浮点数二进制表示的操作函数。可参考bits.c中注释说明和tests.c中对应的测试函数了解其更多具体信息。注意输入参数和返回结果均为unsigned int类型，但应作为单精度浮点数解释其32 bit二进制表示对应的值。
表3 浮点数操作题目列表
本题分数
函数名
功能
约束条件
最多操作符某某
2
floatAbsVal
通过bit级操作返回一个float型浮点数的绝对值。如果输入参数为NaN，则直接返回输入参数的原值。
可以使用任何的操作符，包括||和&&。也可以使用if，while。
10
2
floatIsEqual
判断两个浮点数是否相等，如果相等则返回1，否则返回0。
如果输入参数中含有NaN，则返回0。
注：+0和-0被当作相等的情况对待。
可以使用任何的操作符，包括||和&&。也可以使用if，while。
25
四、实验步骤
1. 使用dlc检查函数实现代码是否符合实验要求的编码规则。
首先./dlc bits.c直接检测是否有错误。如图1.1所示：
/
图1.1
由图知，如果没有任何错误输出，则表示bits.c文件的编写无误，基本符合要求。
然后用-e选项调用dlc，观察操作符某某。如图1.2所示：
通过此选项可以查看每一道具体题目是否符合要求。如果没有任何问题，输出结果如下图1.2所示。如果局部出现问题，则输出会类似于图1.3所示，在具体位置表示出相应题目的具体问题。对于本例，小题1：语法错误，小题3：超过了最多操作符某某量要求，原题要求不超过3个，结果使用了5个。
/
图1.2 无问题情况
/
图1.3有问题的情况
2、使用 btest 检查函数实现代码的功能正确性。
首先使用make编译生成btest可执行程序，如图1.4所示。部分warning不需要特殊处理，但如果出现的warning过多则需要适当注意是否程序中有错误。
/
图1.4
然后调用 btest 命令检查 bits.c中所有函数的功能正确性。如图1.5所示，得分会以数字形式显示在左侧，错误显示则显示error。
/
图1.5
如果有报错，如图1.6。没有报XX就更好，去做实验吧。
/
图1.6
这说明你的编译环境不完善。因为makefile中的编译法则中有输出32位输出格式文件，你没有装相关工具就会出现这个错误。
解决也很简单， 完善编译环境即可。
sudo apt-get install gcc-multilib
出了问题，百度下更全面，希望你们养成这个习惯
五、实验注意事项
1.注意给出的可以使用的运算符及最大个数。
2.除了float类型的两个操作函数可以使用if-else条件语句外，其它函数只能用顺序结构进行代码设计和实现。
3.本实验使用btest程序进行评分时记分为50分制，但最后教师端进行实际成绩核算时会使用100分制（乘以2）。
六、做题过程
1、isZero(int x)：
要求：isZero(5) = 0, isZero(0) = 1
最大操作数：2
return !x;
做完之后可以，编译(make)一下看结果是否通过
/
2、negate(int x)
要求：negate(1) = -1
Legal ops: ! ~ & ^ | + >
最大操作数：5
即有符号数x，求补码 -x，而 补码 = 反码 + 1。
反码即 ~x。按位取反
按照我们生活中的思维，原来的(x)+ 相反数 (-x) = 0000 0000 ，假设w = 8.
原码 + 相反数 = 0000 0000
相反数 = 0000 0000 - 原码 ，即 -x = 0000 0000 - x
在8位二进制中，把我们得出来的结论 0000 0000与 1 0000 0000相等的结论用上，变成如下式子：
相反数 = 1 0000 0000 - 原码
相反数 = （1111 1111 + 0000 0001 ）- 原码
相反数 = 1111 1111 - 原码 + 0000 0001
相反数 = （1111 1111 - 原码 ）+ 0000 0001
看到这里我相信大家应该会感觉有点那味了，1111 1111 - 原码 是什么呢？这个不就是每一位都与原码相反的二进制数吗，我们的学者把它称为反码，反码反码，不就是每一位都与原码相反的二进制数吗。（比如原码为0101 0101 的二进制数，带入1111 1111 - 原码 这个式子中得 1111 1111 - 0101 0101 = 1010 1010 ，0101 0101 的反码是 1010 1010）
把刚刚得到的结论带入上式，
相反数 = 反码 + 0000 0001 ，即 -x = ~x + 1
所以 return ~x+1;
3、specialBits(void)
eg ： return bit pattern 0xffca3fff
Legal ops: ! ~ & ^ | + >
Max ops: 3
分析： 0xffca3fff
1111 1111 1100 1010 0011 1111 1111 1111
f f C A 3 F F F
int specialBits(void) {
return 0xffca3fff; // 投机，违反了什么？
}
/
考虑到 0xff3cafff 为 1111 1111 1100 1010 0011 1111 1111 1111
取反 0000 0000 0011 0101 1100 0000 0000 0000
11 0101 1100 0000 0000 0000
11 0101 11 31; // 补码的符号位
return (is_neg | is_pos) + 1;
如果是非零的数， (is_neg | is_pos) 结果是全1的，即-1。再加1结果是0
如果是零，(is_neg | is_pos) 结果是0，再加1，结果是1
9、bitParity(int x) 如果x中包含奇数个0，则返回1；否则返回0。
Examples: bitParity(5) = 0, bitParity(7) = 1
Legal ops: ! ~ & ^ | + >
Max ops: 20
最容易想到的就是线性的方法了，检查每一个位，为1则累加1。最后检查累加值最低位（奇数的判断）是1，则输出1，否则返回0。但可以看到这样的话需要检查的32步，再加上累加操作的32步，总共64步。大于20步。
经过上述思考，可以发现用线性的方法极有可能是要超出20步的。那么最容易降低复杂度的就是O(logN)的算法。鉴于此，我想到可以用二分的方法试一下。那么，怎么用二分呢？再仔细一看，由于检查的是含有1是否为奇数，并没有要求计算总的数量，所以是否可以用一个操作符来判断奇偶。
怎样的操作数可以判断奇偶，于是想到xor。由于xor在两数都不相同时为1，所以多个位作xor操作，得出为1则说明有奇数个1。并且利用二分的思想分解成两个16位->两个8位……->两个1位，如此不断xor。就得出了最后答案。
这里 假设 x = 0x00 00 00 07 ，异或过程中如果位值相同，会一起抵消掉，相当于偶数
int w16 = (x >> 16)^x; // w16 = 0x***^0x***=0x***
int w8 = (w16 >> 8)^w16; // w8 = 0x***^0x***=0x***
int w4 = (w8 >> 4)^w8; // w4 = 0x***^0x***=0x***
int w2 = (w4 >> 2)^w4; // w2 = 0x***^0x***=0x***
int w1 = (w2 >> 1)^w2; // w1 = 0x***^0x***=0x***
return w1 & 1; // answer = 0x000000 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 subtractionOK(0x***,0x***) = 0, // 溢出
Legal ops: ! ~ & ^ | + >
Max ops: 20
只要x与y,x-y的符号位不同时就会溢出。(-++负减正得正，+--),即
subtractionOK(-1,-1) = 1,因为 -1 –(-1) = 0，变化符号了
根据上题思路
该题判断减法是否溢出，减法是否溢出，第一个取决的便是两个数字的符号，我们可以发现
同号相减是不会溢出的，此时输出1，而异号相减溢出时结果的符号可能会与被减数的符号相反，造成溢出，输出0.你可以举例子，好好捋捋。
x – y = x + (~y + 1)
int x_neg = (x >> 31) & 1;
int y_neg = (y >> 31) & 1;
int sum = x + (~y + 1); // x - y
int sum_neg = (sum >> 31) & 1;
return !(x_neg^y_neg) | !(x_neg^sum_neg);
[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《实验一 数据表示与运算实验》的无排版文字预览，完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。
图片预览
