首页 > 其他分享 >csapp_实验_-__datalab

csapp_实验_-__datalab

时间：2024-05-12 19:53:05浏览次数：27  
标签：csapp return exp int 31 datalab _-__ bit uf

Datalab

前言

该实验是《深入理解计算机系统》（英文缩写CSAPP）课程附带实验——Lab1：Data Lab，对应书中第二章内容（信息的表示和处理），是所有实验中的第一个实验，

**实验目的 **

datalab实验提供了一个文件夹，我们的目的只是改写bits.c中的15个函数，使其完成相应的功能即可。至于其他文件是用来编译、测试，并且限制你使用一些禁止的运算符。

实验说明

Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.
学生实现简单的逻辑、二进制补码和浮点数，但使用c的一个高度受限的子集。例如，他们可能被要求仅使用位级操作和直线代码计算一个数字的绝对值。本实验帮助学生理解C数据类型的位级表示和数据操作的位级行为。

目标是修改bits.c的副本，使其通过btest中的所有测试，而不违反任何编码准则。

makefile -生成btest、fshow和show
readme -此文件
bits.c -你将修改并提交的文件
bits.h -头文件
btest.c -主要的btest程序
btest.h -用于构建btest
decl.c -用于构建btest
tests.c - 用于构建btest
test-header.c - 用于构建btest
dlc* -规则检查编译器二进制(数据实验室编译器)
driver .pl* -使用btest和dlc自动升级位的驱动程序
Driverhdrs.pm -可选的“击败教授”比赛的头文件
fshow.c -用于检查浮点表示的工具
ishow.c -用于检查整数表示的实用程序

一、不允许允许的操作

  1. 使用任何控制结构，如if, do, while, for, switch等。

  2. 定义或使用任何宏。

  3. 在此文件中定义任何其他函数。

  4. 调用任何库函数。

  5. 使用任何其他的操作，如&&, ||, -, or ? :

  6. 使用任何形式的casting

  7. 使用除int以外的任何数据类型。这意味着你不能使用数组、结构等。[1]

二、实验环境

将整个文件拖入Linux环境32位环境中，打开终端；
1.make clean 清除所有编译文件
2.make 编译所有文件 （如果bits.c有问题编译不成功）
3…/btest bits.c 测试bits.c
最终结果：（函数正确情况下）
​​
​​​​​​请添加图片描述

三、函数实现

需要注意的点:

  1. 按位右移>> ：
    对有符号数都是算数右移（最高位是0补0，最高位是1补1）
    对无符号数都是逻辑右移（最高位补0）
  2. 提取符号的方法：x&1 （格式化该数，得到其符号）

题目列表

请添加图片描述

1.bitXor(x,y)

只使用两种位运算实现异或操作。

请添加图片描述

  • 思路：

摩根定律

a^b=
1.(a|b)&(~a|~b)
2.~(~a&~b)&~(a&b)
3.(a&~b)|(~a&b)

请添加图片描述

  • 代码
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(~x&~y)&~(x&y);
}

2.tmin()

使用位运算获取对2补码的最小 int 值。这个题目也是比较简单。

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 0x1<<31;
}
  • 思路

C 语言中 int 类型是32位，即4字节数。补码最小值就是符号位为1，其余全为0。所以只需要得到这个值就行了，我采用的是对数值 0x1 进行移位运算，得到结果。

3.isTmax

判断x是不是补码表示的最大值

  • 思路

要我们判断输入的x是不是最大的补码整数。首先，最大补码整数为：符号位为0，其余位为1（其实就是最小补码取反）。所以我么可以先构造最大整数：max = ~(0x1<<31)。

假设x为TMax(01111111,8位)，则x+1得到TMin(10000000)，再加x，取反再取非，即可返回1，而其余值返回0
但因为当x=-1时，最后返回值也为1，所以要排除这种情况

int isTmax(int x) {
  return !(~(x+1)^x)&!!((x+1)^0x0);
}

4.allOddBits(x)

  • 思路

这个题目还是比较简单的，采用掩码方式解决。首先要构造掩码，使用移位运算符构造出奇数位全1的数 mask ，然后获取输入 x 值的奇数位，其他位清零（mask&x），然后与 mask 进行异或操作，若相同则最终结果为0，然后返回其值的逻辑非。

判断所有奇数位是否都为1，这里的奇数指的是位的阶级是2的几次幂。重在思考转换规律，如何转换为对应的布尔值。

所有奇数位为1则返回1。其中位的编号从0（最低有效位）到31（最高有效位）。

想要判断一个位是否为1很简单：设计一种掩码，需要检测的位设置为1，其余位设置为0，然后和要检测的数按位与，最后判断结果和掩码是否相等即可。

本题的难点是怎么构造这样一个补码。因为常数被限制在0~255，即我们只能设置最低的8位。先看8位，奇数位为1偶数位为0即0xAA（10101010），采用位移的方式使32位中每个8位都符合这个标准。结果如下：

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */

int allOddBits(int x) {
    int A = 0xA;
    int AA= A|(A<<4);
    int AAA=AA|(AA<<8);
    int mask=AAA|(AAA<<16);
  return !((x&mask)^mask);
}

5.negate

返回-x

思路：
一个数的相反数为其二进制位表示的按位取反，再+1，即-x=(~x)+1

/* negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return (~x)+1;
}

6.isAsciiDigit(x)

计算输入值是否是数字 30-39 的 ASCII 值。这个题让我认识到了位级操作的强大。

思路：
要使0x30 <= x <= 0x39，则x-0x30>=0 且 0x39-x>=0
即运算结果的符号位为0，可以用移位操作（有符号数右移为算术右移）
另，减法运算可以看作x+(-x), -x=~x+1

/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
    //0x30 -> 110000
    //0x39 -> 111001
    //leading zero ->26
    int a = x>>6;
    int cond1 = !a;

    //11xxxx
    int b = x>>4;
    int cond2 = !(b^0b11);

    //111001 1001 -> 9
    int c = x&(0xf);
    int res = c-(0xA);
    int cond3 =!!(res>>31);
  return

7.conditional(x, y, z)

使用位级运算实现C语言中的 x?y:z三目运算符。又是位级运算的一个使用技巧。

  • 思路：
    用倒推的思路，返回值二选一，return结果一定是用 | 连接
    而一个返回y，一个返回z，返回原值可以用补码全1（即-1）和&来实现，返回0可用0和&来实现
    定义中间量condition=-1或0，condition需要与x相关联，则可以用!!x和取相反数的操作来实现
    当 x!=0时，!!x=1, condition=~(!!x)+1=-1
    当 x= 0时，!!x=0, condition=~(!!x)+1= 0
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
	int mask = ((!!x)<<31)>>31;
  	return (mask&y)|((~mask)&z) ;
}

8.isLessOrEqual

如果x<=y，则返回1，否则返回0

当相同符号时，直接相减判断是否为负数即可。
当前者为正，后者为负时，直接返回0，前者为负后者为正时返回1。

  • 思路

​ 通过位运算实现比较两个数的大小，无非两种情况：一是符号不同正数为大，二是符号相同看差值符号。

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 *   1.x=y
 *   !(x^y)
 *
 *   2.x+ y-
 *   signX = x>>31&0x1;
 *   signY = y>>31&0x1;
 *   !signX&&!signY
 *
 *   3.x- y+
 *   signX&&!signY;
 *
 *   4.x+ y+   x- y-
 *   x+(~y)+1 //x-y
 *   ((x+(~y)-1)>>31)&0x1
 */
int isLessOrEqual(int x, int y) {
    int cond1 = !(x^y);
    int signX = (x>>31)&1;
    int signY = (y>>31)&1;
    int cond2 = !((!signX)&(signY));
    int cond3 = signX&(!signY);
    int cond4 = ((x+(~y)+1)>>31)&0b1;

  return cond1 |( cond2 & (cond3 | cond4)) ;
}

9.logicalNeg

实现“！”运算符

使用位级运算求逻辑非 !

  • 思路

​ 逻辑非就是非0为1，非非0为0。利用其补码（取反加一）的性质，除了0和最小数（符号位为1，其余为0）， 外其他数都是互为相反数关系（符号位取位或为1）。0和最小数的补码是本身，不过0的符号位与其补码符号位位或为0，最小数的为1。利用这一点得到解决方法。

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
    int negx = (~x)+1;
    int sign = (negx|x)>>31;
  return sign+1 ;
}

10. howManyBits

求值：“一个数用补码表示最少需要几位？”

例子：

howManyBits(12) = 5

howManyBits(298) = 10

howManyBits(-5) = 4

howManyBits(0) = 1

howManyBits(-1) = 1

howManyBits(0x80000000) = 32

这里我们以12为例

0000 0000 0000 0000 0000 0000 0000 1100

实际上要得到12只需要4+1（符号位）=5位即可

这里我们可以看出，计算一个数最小需要多少比特位的问题转化成了从最高位到最低位寻找第一个数据为1的问题

这里我们使用类似于二分的思想

先看高低16位（判断是否存在数据为1的比特位），在看8位，4，2，1......

这里用 flag = !!(x>>16);

如果flag结果为1，表示高16位中存在一位或者多位数据为1的比特位

为0表示高16位中不存在数据为1的比特位

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            hiowManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
	int isZero = !x;
	int flag = x>>31;
	int mask = ((!!x)<<31)>>31;
	x = (flag & (~x)) | ((~flag) & x );
	int bit_16,bit_8,bit_4,bit_2,bit_1,bit_0;

	bit_16 =(!((!!(x>>16))^(0x1)))<<4;
	x>>=bit_16;
	bit_8 =(!((!!(x>>8))^(0x1)))<<3;
	x>>=bit_8;
	bit_4 =(!((!!(x>>4))^(0x1)))<<2;
	x>>=bit_4;
	bit_2 =(!((!!(x>>2))^(0x1)))<<1;
	x>>=bit_2;
	bit_1 =(!((!!(x>>1))^(0x1)));
	x>>=bit_1;
	bit_0 =x;

	int ret = bit_16 + bit_8 + bit_4 + bit_2 + bit_1 + bit_0 + 1;

	return isZero | (mask & ret) ;
}

11.unsigned floatScale2(unsigned uf)

求浮点数乘以2的结果

根据IEEE浮点规则我们知道

$$V = (（-1）^ s ) * M * ( 2 ^ E )$$

⚠️这里需要注意的是函数传入的参数以及返回值都是无符号整型数

也就是说变量uf虽然是一个无符号整型数，但在题目中我们需要把它的二进制表示解析成一个单精度浮点数

思路1

请添加图片描述

看了图,思考一下如何将一个无符号整型数解析成单精度浮点数呢？

A：根据单精度浮点数的定义来划分变量uf的32个bit位

其中uf二进制表示的最高位（31位）表示的是符号位s

第23～30位表示阶码字段（exp）

第0～22位表示小数字段（frac）

我们需要从uf中提取符号字段、阶码字段和小数字段

那么获取阶码字段exp将uf与0x7F800000（如下）按位“与运算”，再将结果右移23位即可

0     1111 1111（exp）   0000.....0000

即 exp = （0x7F800000 & uf ) >>23

这样就解析出阶码字段exp，获取其他字段的方式同理

由此，我们将无符号整型数解析成单精度浮点数

根据IEEE浮点规则我们知道

$$V = (（-1）^ s ) * M * ( 2 ^ E )$$

根据阶码exp的值分类讨论

1.当exp = 0xFF时，表示特殊值，当为特殊值时我们知道有两种情况。一种（当frac不等于0）表示不是一个数（NaN），另一种（frac等于0）表示无穷（根据符号位表示正无穷还是负无穷）。

    当为NaN时根据题目要求，直接返回uf即可

    当为无穷时，无穷 * 2 结果还是无穷，返回uf

2.当exp = 0时，表示非规格化的数，由于非规格化的数表示数值0或者非常接近0的数

    当frac = 0 时，此时表示0 ，0乘以任何数都为0，所以直接返回uf（注意当符号位不同时，正零与负零是有区别的，但由于0怎么乘都为0，所以这里我们不做讨论，直接返回uf，不能返回零）

    当frac != 0 时，此时表示非常接近0的数，针对这情况只需将小数字段乘以2即可（左移一位）

3.当exp 既不等于0，也不等于0xFF时，此时表示规格化的数

    对于这种情况乘以2只需要对 exp + 1 即可

    （具体原因可以看上面的IEEE浮点表示规则）

    不过这里还有一种特殊情况要出处理，当exp = 254，此时虽然是一个规格化的数，但阶码字段加1之后会超出规格化所能表示的范围，针对这种情况，我们需要返回无穷（无穷分为正无穷和负无穷，这里根据符号位判断即可）

思路2

1.首先考虑第一种情况

When argument is NaN, return argument

需要先求出exp

int exp = (uf&0x7f800000)>>23; //23-30 这8位
int sign=uf>>31&0x1; //符号位
int frac=uf&0x7FFFFF;

如果exp=255 并且尾数非0 就是NaN 直接return 就好 其次如果frac 全为0 那么则表示无穷大 这两种情况都可以直接return

  1. 如果exp=0 则表示非规格化数

请添加图片描述

那么我们直接返回uf*2 就可就是把frac>>1

2.如果exp!=0 && ！=255 那么表示规格化数

请添加图片描述

那么我们的修改就先把exp+1

最终用或操作和移位操作将这三个字段拼成一个32bit的数返回即可

代码

//float
/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
	//s,expr,frac
	unsigned s = (uf >> 31) & (0x1);
	unsigned expr = (uf>>23) & (0xff);
	unsigned frac = (uf & 0x7fffff);

	//0
	if(expr == 0 && frac == 0)
		return uf;
	//inifity or nor na number
	if(expr == 0xff)
		return uf;
	//denormalize
	if(expr == 0)
	{
		//E = expr - basic
		//    expr - 127 = -127
		// frac
		frac <<= 1;
		return (s << 31 ) | frac;
	 }
	//normalize
	expr++; //即乘以二
	//E = expr - 127
	return (s << 31) | (expr << 23) | (frac);
}

12.int floatFloat2Int(unsigned uf)

把单精度浮点数强制转化成整型数

  • 思路

​ 6位IEEE浮点数格式如下

请添加图片描述

根据上图我们可以分为三种情况

先计算出E=exp-bias

  1. 如果是小数 E< 0的情况我们直接返回0

  2. 如果是exp=255 的情况直接返回0x80000000u 这里注意如果超范围了也会直接返回0x80000000u
    因此可以直接用E>=31 来判断

  3. 如果是规格化数则我们进行正常处理 $$

    标签：csapp,return,exp,int,31,datalab,_-__,bit,uf
    From： https://www.cnblogs.com/cfpls/p/18188097

相关文章

  • 蓝桥杯-错误票据(两种写法stringstream和扣字符)
    某涉密单位下发了某种票据，并要在年终全部收回。每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。你的任务是通过编程，找出断号的ID和重号的ID。假设断号不可能......
  • 多模态大模型 LLaVA 微调教程-大语言模型8
    写完之后发现他好像不是很需要这个东西，所以就先发在自己的博客好了。不投稿首页或者候选区应该本来也就不会有多少流量，所以应该不会干嘛的，大不了后面被说不让放网上以后就删掉这篇，嘻嘻。LLaVA是最早出现的VisionLanguageModel。本教程将教你微调llava-v1.5-13b。与本博客......
  • Datalab
    Datalab前言该实验是《深入理解计算机系统》（英文缩写CSAPP）课程附带实验——Lab1：DataLab，对应书中第二章内容（信息的表示和处理），是所有实验中的第一个实验，**实验目的**datalab实验提供了一个文件夹，我们的目的只是改写bits.c中的15个函数，使其完成相应的功能即可。至于其他文件......
  • c++踩方格-动态规划基础题
    有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b、走过的格子立即塌陷无法再走第二次；c、只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同......
  • python教程13-异常处理
    异常处理流程：流程示例： 抛出异常自定义异常 ......
  • 数据结构学习笔记-先序遍历森林
    先序遍历森林问题描述：设计算法输出先序遍历的森林节点及其所在的层次【算法设计思想】1.数据结构定义首先，定义二叉树节点的数据结构。每个节点包含存储数据的data字段，以及指向左右子节点的指针（lChild和rChild）。这种数据结构是二叉树和森林表示的基础。2.先序遍历单棵树设......
  • python教程12-面向对象进阶
    1、classmethod类方法类方法只能访问类变量，不能访问实例变量2、staticmethod静态方法不能访问类变量，也不能访问实例变量。除非在实例调用时给方法传实例。3、反射1-判断对象是否有属性的情况用法： 实例： __name__，模块被其他模块导入的时候调用，是你叫的名字。模块自己主......
  • 梦熊四月 csp-s 模拟赛2 T2 排序
    小B想要对一个长为\(n\)的序列\(A\)排序。已知\(A\)中只包含\(0,1,\cdots,n-1\)且对任意\(i\nej\)有\(A_i\neA_j\)且\(n\)为\(2\)的次幂。为了排序，小B只想用以下两种操作：交换相邻的两个位置，也就是说选择\(1\lei\len-1\)并且交换\(A_i,A_{i+1}\)。......
  • [笔记]（更新中）树形dp-中（树上背包）
    树上背包是树形dp的常见模型，通常是分组背包的变形。引入：二叉苹果树P2015二叉苹果树题意简述：在一个二叉树中，每个边有一个权值。我们要保留\(Q\)条边组成的连通分量（必须包含根节点），求边权和最大值。我们思考，从节点\(1\)（根节点）开始保留\(Q\)条边，最大答案是什么？我们分出\(3\)种......
  • numba-cfunc
    参考文档:https://numba.pydata.org/numba-doc/latest/user/cfunc.htmlcfunc创建C/C++回调函数与jit相似，有一个不同点是，cfunc强制传递一个签名，用来确定C回调的可见签名。cfunc对象暴漏出编译后的C回调地址，以便可以传递给任何的外部C/C++库。他还暴漏了一个ctypes......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99