HIT CSAPP LAB2

DataLab 数据表示

仅供参考，因为我也是18级的~~~

目 录

第1章 实验基本信息 - 4 -
1.1 实验目的 - 4 -
1.2 实验环境与工具 - 4 -
1.2.1 硬件环境 - 4 -
1.2.2 软件环境 - 4 -
1.2.3 开发工具 - 4 -
1.3 实验预习 - 4 -
第2章 实验环境建立 - 5 -
2.1 UBUNTU下CODEBLOCKS安装 - 5 -
2.2 64位UBUNTU下32位运行环境建立 - 5 -
第3章 C语言的数据类型与存储 - 6 -
3.1 类型本质（1分） - 6 -
3.2 数据的位置-地址（2分） - 6 -
3.3 MAIN的参数分析（2分） - 6 -
3.4 指针与字符串的区别（2分） - 6 -
第4章 深入分析UTF-8编码 - 8 -
4.1 提交UTF8LEN.C子程序 - 8 -
4.2 C语言的STRCMP函数分析 - 8 -
4.3讨论：按照姓氏笔画排序的方法实现 - 8 -
第5章 数据变换与输入输出 - 9 -
5.1 提交CS_ATOI.C - 9 -
5.2 提交CS_ATOF.C - 9 -
5.3 提交CS_ITOA.C - 9 -
5.4 提交CS_FTOA.C - 9 -
5.5 讨论分析OS的函数对输入输出的数据有类型要求吗 - 9 -
第6章 整数表示与运算 - 10 -
6.1 提交FIB_DG.C - 10 -
6.2 提交FIB_LOOP.C - 10 -
6.3 FIB溢出验证 - 10 -
6.4 除以0验证： - 10 -
第7章 浮点数据的表示与运算 - 11 -
7.1 正数表示范围 - 11 -
7.2浮点数的编码计算 - 11 -
7.3特殊浮点数值的编码 - 11 -
7.4浮点数除0 - 11 -
7.5 FLOAT的微观与宏观世界 - 11 -
7.6 讨论：任意两个浮点数的大小比较 - 11 -
第8章 舍位平衡的讨论 - 12 -
8.1 描述可能出现的问题 - 12 -
8.2 给出完美的解决方案 - 12 -
第9章 总结 - 13 -
9.1 请总结本次实验的收获 - 13 -
9.2 请给出对本次实验内容的建议 - 13 -
参考文献 - 14 -

第1章 实验基本信息

1.1 实验目的

 熟练掌握计算机系统的数据表示与数据运算
 通过C程序深入理解计算机运算器的底层实现与优化
 掌握VS/CB/GCC等工具的使用技巧与注意事项

1.2 实验环境与工具

1.2.1 硬件环境

X64 CPU；2GHz；2G RAM；256GHD Disk 以上

1.2.2 软件环境

Windows7 64位以上；VirtualBox/Vmware 11以上；Ubuntu 16.04 LTS 64位/优麒麟 64位

1.2.3 开发工具

Visual Studio 2010 64位以上；CodeBlocks；vi/vim/gpedit+gcc

1.3 实验预习

 上实验课前，必须认真预习实验指导书（PPT或PDF）
 了解实验的目的、实验环境与软硬件工具、实验操作步骤，复习与实验有关的理论知识。
 采用sizeof在Windows的VS/CB以及Linux的CB/GCC下获得C语言每一类型在32/64位模式下的空间大小
Char /short int/int/long/float/double/long long/long double/指针
 编写C程序，计算斐波那契数列在int/long/unsigned int/unsigned long类型时，n为多少时会出错
(1).先用递归程序实现，会出现什么问题？
(2).再用循环方式实现。
 写出float/double类型最小的正数、最大的正数（非无穷）
 按步骤写出float数-1.1在内存从低到高地址的字节值-16进制
 按照阶码区域写出float的最大密度区域范围及其密度，最小密度区域及其密度（区域长度/表示的浮点个数）

第2章 实验环境建立

2.1 Ubuntu下CodeBlocks安装

CodeBlocks运行界面截图：编译、运行hellolinux.c

2.2 64位Ubuntu下32位运行环境建立

在终端下，用gcc的32位模式编译生成hellolinux.c。执行此文件。
Linux及终端的截图。

第3章 C语言的数据类型与存储

3.1 类型本质（1分）

C编译器对sizeof的实现方式：
sizeof不是函数，而是运算符，C语言中的关键字；
它由编译器来计算，编译阶段就计算出结果了，在运行时就只是一个常量。编译阶段可以确定数据类型，根据数据类型换算数据的长度。

3.2 数据的位置-地址（2分）

打印x、y、z输出的值：截图1

截图1

反汇编查看x、y、z的地址，每字节的内容：截图2，标注说明


x的地址是0x0804a020
y的地址是0x08048528
z的地址是0x0804a024
反汇编查看x、y、z在代码段的表示形式。截图3，标注说明

x存在0x804a020,mov 0x8048528,%eax 将地址存入%eax语句
y存在0x8048528,这一地址经过flfl与fstpl操作将地址压入-0x10(%ebp)中
z存在0x804a024,这一地址push进栈以供puts使用

x与y在汇编阶段转换成补码与ieee754编码。
数值型常量与变量在存储空间上的区别是：
数值型常量一般存放在.rodata段、常量存储区，有的立即数直接编码在指令里，存放在代码段(.text)中；数值型变量若为未初始化的全局变量将存放在.bss段（在运行时将为.bss段分配空间），若为初始化的全局变量以及初始化的静态变量将存放在.data段，函数内的局部变量（用户临时创建的）、传递的函数参数一般存放在栈上，动态分配的变量在堆中。
字符串常量与变量在存储空间上的区别是：
指针方式创建的字符数组，是常量字符串；方括号（[]）方式创建的字符数组是字符串变量。
未初始化的全局字符串存放在bss段；全局的初始化的字符串常量内容存储在rodata段；全局初始化后的字符串变量存储在data段；函数内的局部变量（用户临时创建的）或常量中，字符串内容存放在rodata段，变量或常量指针放入栈中；静态字符串变量存放在data段。
常量表达式在计算机中处理方法是：
编译阶段尽量将左移右移代替乘除法，汇编阶段计算出常量表达式的值

3.3 main的参数分析（2分）

反汇编查看x、y、z的地址，argc的地址，argv的地址与内容，截图4

调试过程中
首先传递参数：


argv[0]内容为：/mnt/hgfs/hitics/xyzfuben/xyz
存放在：0xffffd181


argv[1]内容为：-学号
存放在：0xffffd19f

argv[2]内容为：身份证号
存放在：0xffffd1ab


argv[3]内容为：学号-姓名
存放在：0xffffd1c0

3.4 指针与字符串的区别（2分）

cstr的地址与内容截图，pstr的内容与截图，截图5

pstr修改内容会出现什么问题：用学号+姓名初始化后，若以 **pstr = “…”/…为身份证号/这一形式赋值，将会报错，因为原先pstr的值（学号+姓名）存储在常量区，这种赋值语句会意图修改常量区的值，不合法；若以pstr = “…”/…为身份证号/的形式赋值是合法的，但此时指针指向位置发生改变，即指针指向了常量区另一个地方，该地方存有后赋值的字符串常量。

第4章 深入分析UTF-8编码

4.1 提交utf8len.c子程序

#include <stdio.h>
int utf8len(char* cstr) {char *s = cstr;int length = 0;char num;while (*s != '\0') {length++;num = *s;if ((num & 0x80) == 0) {s++;}else {int result = 0;do{num = num << 1;result++;}while(num & 0x80);s += result;}}return length;
}
int main() {char cstr[100]="";scanf("%s", cstr);printf("%d\n", utf8len(cstr));return 0;
}

4.2 C语言的strcmp函数分析

分析论述：strcmp到底按照什么顺序对汉字排序

C语言中，（中文Windows系统）汉字使用的编码体系里面是两个字节的GB编码（Linux下一般为utf-8，Unicode编码汉字一般为三个字节）， strcmp是通过比较有符号数字大小来判断字符串的。编码大的，字符串就比较大。若前面字符串＞后面字符串，返回正数，=返回0，<返回负数

4.3讨论：按照姓氏笔画排序的方法实现

分析论述：应该怎么实现呢？
计算出每个字的笔画，通过笔画数来比较。需要构造一个字符串数组，索引为笔画数，具体的值为相同笔画数以横竖撇点折的顺序排列的。再实现一个比较器，使用循环去到笔画数组中查找进行比较。笔划数相同的可按拼音字母字典顺序排序。以GB编码为例，依据区位码的汉字顺序，依次将每个简体汉字的笔画数信息存入一笔画数组，根据所查汉字的区码和位码获得该汉字在笔画数组的位置和该字的笔画数。

第5章 数据变换与输入输出

5.1 提交cs_atoi.c

#include <stdio.h>
#include <string.h>
int main() {char str[100];int len = 0;scanf("%s", str);len = strlen(str);int j = 1;if (str[0] == '-'){len--;}while (--len) {j *= 10;}int result = 0;int i = 0;if (str[0] == '-') {i++;}while (j) {int m = 0 - '0' + str[i++];result = m * j + result;j /= 10;}if (str[0] == '-') {result = -result;}printf("%d\n", result);return 0;
}

5.2 提交cs_atof.c

#include <stdio.h>
#include <string.h>
int main() {char str[100];scanf("%s", str);int flag = 0;if (str[0] == '-') {flag = 1;strcpy(str, str + 1);}char *p = str;int len = 0;int j = 1;float x = 0;int leng = strlen(str);while (*p != '\0' && *p != '.') {len++;j *= 10;p++;}int i = 0;while (len--) {int m = 0 - '0' + str[i++];j /= 10;x += m * j;}float y = 1.0;i++;if (*p == '.') {p++;while (leng - i) {y /= 10;int m = 0 - '0' + str[i++];x += y * m;}}if (flag) {x = -x;}printf("%f\n", x);return 0;
}

5.3 提交cs_itoa.c

#include <stdio.h>
#include <string.h>
int main() {int x;scanf("%d", &x);int flag = 0;int i = 0;char str[100];if (x < 0) {flag = 1;x = -x;str[i++] = '-';}else if (x == 0) {str[i++] = '0';}int j = 1;while (x / j) {j *= 10;}j /= 10;while (x) {int m = x / j;x -= j * m;j /= 10;str[i++] = m + '0' - 0;}str[i] = '\0';printf("%s\n", str);return 0;
}

5.4 提交cs_ftoa.c

#include <stdio.h>
#include <string.h>
int main() {double x;scanf("%lf", &x);int flag = 0;int i = 0;char str[100];if (x < 0) {flag = 1;x = -x;str[i++] = '-';}if (x >= 0 && x < 1) {str[i++] = '0';}int xx = x;int j = 1;while (xx / j) {j *= 10;}j /= 10;x -= xx;while (xx) {int m = xx / j;xx -= j * m;j /= 10;str[i++] = m + '0' - 0;}if (x != 0) {str[i++] = '.';int length = 0;while (x && length <= 5) {x *= 10;length++;int m = x;str[i++] = m + '0' - 0;x -= m;}while (length <= 5) {str[i++] = '0';}str[i] = '\0';if (x != 0){x *= 10;int m = x;x -= m;i--;if (m >= 5){while (i >= 0){if (str[i] == '.'){i--;continue;}if (str[i] == '9') {str[i] = '0';i--;continue;}str[i]++;break;}}}}else{str[i++] = '.';str[i++] = '0';str[i++] = '0';str[i++] = '0';str[i++] = '0';str[i++] = '0';str[i++] = '0';str[i] = '\0';}printf("%s\n", str);return 0;
}

5.5 讨论分析OS的函数对输入输出的数据有类型要求吗

论述如下：
OS的函数将输入输出的数据都看成字符串来处理。通过输入输出流来实现，例如在Linux下stdin 为标准输入流，标准的输入设备默认键盘；stdout 为标准输出流，标准的输出设备默认屏幕；stderr 为标准错误流，只有程序出错时才会执行的流程。OS先接收输入的字符串，再进行进一步处理；对于输出，也就将要输出的数据转换成字符串输出的。
如：

1. sprintf函数
   int sprintf(char *str, const char *format, …)输出int类型，输入要求为字符串地址，以及用字符串如%s等作为format
2. atoi函数 atof函数
   int atoi(const char *nptr); double atof(const char *nptr)
   输出int类型，输入字符串首地址 输出double类型，输入字符串首地址
3. itoa函数
   char *itoa (int value, char *str, int base );
   返回转换后字符串首地址，输入待转换int数以及转换进制
4. ftoa函数
   char *ftoa(float f, int *status) 返回转换后字符串首地址，输入float和基数

第6章 整数表示与运算

6.1 提交fib_dg.c 、

#include <stdio.h>
int fib_dg(int x){if(x <= 0){return 0;}if(x == 1){return 1;}return fib_dg(x - 1) + fib_dg(x - 2);
}
int main(){for(int i = 0; i <= 100; ++i){printf("fib_dg(%d) = %d\n", i, fib_dg(i));}return 0;
}

6.2 提交fib_loop.c

#include <stdio.h>
int main(){int a = 0, b = 1;printf("fib_loop(0) = %d\n", a);printf("fib_loop(1) = %d\n", b);for(int i = 2;i <= 100;i++){int t = b;b = a + b;a = t;printf("fib_loop(%d) = %d\n", i, b);}return 0;
}

6.3 fib溢出验证

int 时从n=47时溢出，long时n=93时溢出。
unsigned int 时从n=48时溢出，unsigned long时n=94时溢出。

6.4 除以0验证：

除以0：截图1

除以极小浮点数，截图：

第7章 浮点数据的表示与运算

7.1 正数表示范围

写出float/double类型最小的正数、最大的正数（非无穷）
float: 最小正数（十进制）：1.401298 * 10^-45 最大正数（十进制）：3.402823466 * 10³⁸
double：最小正数（十进制）：4.94065645841246544 * 10^-324 最大正数（十进制）：1.7976931348623158 * 10³⁰⁸

7.2浮点数的编码计算

（1）按步骤写出float数-1.1的浮点编码计算过程，写出该编码在内存中从低地址字节到高地址字节的16进制数值
-1.1符号位即最高位为1，由于1.1>1，故bias = 27 – 1= 127，而1.1<2，故exp（10）=127，exp（2）=01111111，故f（10）≈0.1，将0.1不断乘以2，可以得到000[1100…(1100循环)]，当位数达到23位后为[1100…]＞2-24（即理论上24位以后为1…1…）,向上舍入，尾数部分最后[1100]变为[1101]，因此-1.1编码为0xbf8ccccd，从内存中低地址到高地址：cd cc 8c bf
（2）验证：编写程序，输出值为-1.1的浮点变量其各内存单元的数值，截图。

#include <stdio.h>
int main(){float x = -1.1;char *p = &x;for(int i = 1; i <= sizeof(float); ++i){printf("%hhx\t", *p);p++;}printf("\n");return 0;
}

7.3特殊浮点数值的编码

（1）构造多float变量，分别存储+0-0，最小浮点正数，最大浮点正数、最小正的规格化浮点数、正无穷大、Nan,并打印最可能的精确结果输出（十进制/16进制）。截图。

（2）提交子程序floatx.c

#include <stdio.h>
int main(){union{int x;float y;}temp[7];temp[0].x = 0;//+0temp[1].x = (-1) << 31;//-0temp[2].x = 1;//最小浮点正数temp[3].x = 0x7f7fffff;//最大浮点正数temp[4].x = 0x00800000;//最小正规格化数temp[5].x = 0x7f800000;//正无穷temp[6].x = 0x7f900000;//NaNprintf("%f\t\t\t\t\t\t%x\n", temp[0].y, temp[0].x);printf("%f\t\t\t\t\t\t%x\n", temp[1].y, temp[1].x);printf("%f\t\t\t\t\t\t%x\n", temp[2].y, temp[2].x);printf("%f\t\t%x\n", temp[3].y, temp[3].x);printf("%f\t\t\t\t\t\t%x\n", temp[4].y, temp[4].x);printf("%f\t\t\t\t\t\t\t%x\n", temp[5].y, temp[5].x);printf("%f\t\t\t\t\t\t\t%x\n", temp[6].y, temp[6].x);return 0;
}

7.4浮点数除0
（1）编写C程序，验证C语言中float除以0/极小浮点数后果，截图

（2）提交子程序float0.c

#include <stdio.h>
int main() {printf("%f\n", 1.0 / 0);printf("%f\n", 1.0 / 1e-340);return 0;
}

7.5 Float的微观与宏观世界

按照阶码区域写出float的最大密度区域范围及其密度，最小密度区域及其密度（表示的浮点个数/区域长度）：
-（1-2^-23） * 2^-126~（1-2^-23） * 2^-126、22²³/2 * （1-2^-23） * 2^-126、
-（2-2^-23） * 2¹²⁷~（2-2^-23） * 2¹²⁷、2（2⁸-1） * 2²³/2 * （2-2^-23） * 2¹²⁷
最小正数变成十进制科学记数法，最可能能精确到多少：1.40129810^-45
最大正数变成十进制科学记数法，最可能能精确到多少：4.94065645841246510^-324

7.6 讨论：任意两个浮点数的大小比较

论述比较方法以及原因。
IEEE规则中，先比较符号位正数＞负数，再比较阶码位，最后比较尾数。
编程中浮点数从MSB到LSB表示，若相差较大可直接比较大小，当两个数比较接近时，我们常常采用二分法的思想，定义精度如1e-7等，当二者之差小于这个很小的数时，就认为二者是相等的了。为了方便起见，我们对浮点数进行比较时，一般均采用上述方法，而不直接用== 或！=比较，因为有些数可能无法用浮点数精确表示，表示时发生舍入而影响比较结果。

第8章 舍位平衡的讨论

8.1 描述可能出现的问题

在数据统计中，常常会根据精度呈现或者单位换算等要求，需要对数据执行四舍五入的操作，这种操作称为舍位处理。简单直接的舍位处理有可能会带来隐患，原本平衡的数据关系可能会被打破。
例如，保留一位小数的原始的数据是4.5+4.5=9.0，而四舍五入只保留整数部分后，平衡关系就变为5+5=9了，看上去明显是荒谬的。
例如，13,451.00元 + 45,150.00元 + 2,250.00 元 - 5,649.00 元 = 55,202.00元
现在单位变成单位万元，仍然保留两位小数，根据4舍5入的原则:1.35万元 + 4.52万元 + 0.23万元 - 0.56万元 = 5.54万元 ,出现0.02万的误差，平衡被打破。

8.2 给出完美的解决方案

舍位后总计产生的误差，称为“平衡差”（真实数值-平衡后理论数值），舍位平衡其实就是消除平衡差的过程。
（1）单向舍位平衡，即如果在数据统计时，每个数据只用于一次合计，那么在处理舍位平衡时，只需要根据合计值的误差，调整使用的各项数据就可以了，这属于比较简单的情况。
考虑方法1：我们将平衡差直接加到第一个数据，可以解决舍位平衡。但这种方法很可能会使改动后的该数据变动较大，从而影响后续操作，故该方法pass。
考虑方法2：我们将正精度单位（例如保留到0.1/1，正精度单位即为0.1/1）（如果平衡差>0）或负精度单位（例如保留到-0.1/-1，正精度单位即为-0.1/-1）（如果平衡差<0）加到绝对值最大的数据中，这样使得每个数据没有更改或偏差不是很大，但是寻找绝对值最大的多个数据需要进行排序算法，对于大量数据不是很适用，所以该方法pass
考虑方法3：我们将所有的非零数按顺序加上正或负精度单位。考虑到在四舍五入时，0并不会产生误差，而且如果修改数据中的0，这样的变动会比较明显，因此在调整时将保留原始数据中的0不变。这样调整平衡的结果比较合理。同时这种方案避免了排序操作，效率较高，因此这种舍位平衡的规则最为常用。
（2）双向舍位平衡，即如果数据在行向和列向两个方向同时需要计算合计值，同时还需要计算所有数据的总计值。
有一些平衡差只与合计值相关，这样的平衡差称为合计平衡差。在双向舍位平衡表中，只存在一横一纵两个合计平衡差。其它的平衡差都会和具体数据相关，如Feb这个月最下方的平衡差，这种平衡差称为非合计平衡差。
考虑情况1：横向与纵向的非合计平衡差符号相同。只需要调整交叉点处的数据，根据平衡差符号加减最小调整值。
考虑情况2：同向的2个非合计平衡差符号相反。任选另一方向平衡差为0的数据，将这两个方向的数分别根据按平衡差的符号加减最小调整值。
考虑情况3：某个合计平衡差与另一方向的非合计平衡差符号相反。调整交叉点处的合计数据，根据合计平衡差的符号加减最小调整值。
考虑情况4：某个合计平衡差与同方向的非合计平衡差符号相同。任选一另一方向平衡差为0的数据，同时调整这2个方向的数据
考虑情况5：两个方向合计平衡差的符号相同。此时，只有合计数据影响了结果的平衡。任选一个非合计值，根据合计平衡差的符号加减最小调整值，同样调整这个数据的横向和纵向合计值。
综上：
1.对于其它的情况，说明计算有误，是无法通过1次调整达成舍位平衡的。
2.上面的情况往往是混合出现的。
3.可以先处理第(1)种情况，即所有非合计行列平衡差符号相同的情况，再处理第(2)种情况，将非合计行/列中不同符号的平衡差消除。全部调整理完毕后，非合计行与非合计列的平衡差只能各为一种符号。此时再处理第(3)种和第(4)种情况，将非合计行/列的平衡差与合计行/列的平衡差配合消除。最后，如果两个方向行/列的平衡差仍未消除，再按照第(5)中情况处理。这样，就可以对一般性的数据组合完成双向舍位平衡处理了。

参考：

https://blog.csdn.net/raqsoft/article/details/83503757