CSAPP Data Lab

2024-09-01 17:04
文章标签 data lab csapp

本文主要是介绍CSAPP Data Lab,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

CSAPP 的第一个 Lab,对应知识点为书中的第 2 章(信息的表示与处理),要求使用受限制的运算符和表达式实现一些位操作。主要分为两个部分:整数部分和浮点数部分。其中整数部分限制较多,比较偏重技巧性,部分题个人认为很有难度。而浮点数部分则比较基础,主要考察对 IEEE 754 标准的熟悉程度,代码较长,但思路相对简单。

bitXor

思路

使用德-摩根定律进行推导,推导过程如下:

请添加图片描述

代码

int bitXor(int x, int y) {// 德-摩根定律return ~(~(x & ~y) & ~(~x & y));
}

tmin

思路

最小整数即最高位(负数权重)为 1,其余(正数权重)为 0。

代码

int tmin(void) {return 1 << 31;
}

isTmax

思路

由于不能使用左移运算符,因此没办法直接构造出 tmax,需要仔细考虑 tmax 的性质:tmax = 0x7fffffff ,而 tmax + 1 = 0x80000000 ,这两个数的二进制位完全互补,因此满足:tmax + tmax + 1 = 0xffffffff,结果全为 1,对该结果取反即可得到 0,取非得到 1。

但这里还要考虑一个特殊情况:当 x = 0xffffffff 时,x + 1 + x 也满足等于 0xffffffff,因此需要借助异或运算进行特判。

代码

int isTmax(int x) {int case1 = !((x + 1) ^ 0);  // case = x == 0xffffffff ? 1 : 0;return !(~(x + 1 + x)) & !case1;
}

allOddBits

思路

首先构造一个掩码 mask,奇数位全为 1,偶数位全为 0。将 mask 与 x 进行按位与,如果 x 的奇数位全为 1,那么按位与的结果仍然为 mask。然后便可以借助异或和非的组合,将结果转换为 0 或 1。

代码

int allOddBits(int x) {int mask = 0xaa;            // mask = 0x000000aamask = (mask << 8) | 0xaa;  // mask = 0x0000aaaamask = (mask << 8) | 0xaa;  // mask = 0x00aaaaaamask = (mask << 8) | 0xaa;  // mask = 0xaaaaaaaareturn !((x & mask) ^ mask);
}

negate

思路

补码表示法的重要特性,取反加一即可。

代码

int negate(int x) {return ~x + 1;
}

isAsciiDigit

思路

这里我用了比较笨的逐位判断的方法。首先判断第 4 到第 31 位是否为 0x3,然后只需要关注低 4 位的二进制表示了:若第 3 位为 0,则一定位于指定范围之内,再加上两个特例(1000 和 1001)即可。

最后将运算符的个数刚好卡在 15 个,勉强过关。

代码

int isAsciiDigit(int x) {// 0011 0000 <= x <= 0011 1001int high = !((x >> 4) ^ 0x3);         // 4 ~ 31 位是否为 0x3int case1 = ((x & 0xf) >> 3) ^ 0x1;   // bit3 = 0int case2 = !((x & 0xf) ^ 0x8);       // bit0~3 = 1000int case3 = !((x & 0xf) ^ 0x9);       // bit0~3 = 1001return high & (case1 | case2 | case3);
}

conditional

思路

很容易想到根据 x 的值是否非 0 构造出全 0 或者全 1 的数据 flag,然后将 flag 和 flag 取反后的值分别与 y 和 z 进行按位与,这样必然得到两个数:一个为 y 或 z 本身,另一个为 0,再将结果按位或即可。

构造的方法比较巧妙,需要注意到全 0 和全 1 分别代表整数 0 和 -1,它们分别是 0 和 1 的相反数,而 0 和 1 我们可以根据表达式是否非 0,使用非运算符构造出来,再将构造的结果取反加一即可。

代码

int conditional(int x, int y, int z) {int flag = ~(!x) + 1;     // flag = x ? 0 : -1;int yp = ~flag & y;       // flag = 0, yp = y; flag = -1, yp = 0;int zp = flag & z;        // flag = 0, zp = 0; flag = -1, zp = z;return yp | zp;
}

isLessOrEqual

思路

判断两个数的大小关系,很容易想到使用作差的方法,判断 x + ~y + 1 的结果是否小于等于 0,即全为 0 或者最高位为 1。

不过这里还需要考虑溢出:由于同号相减必定不会导致溢出,因此我们只需要考虑异号的情况。而如果两个数异号,那它们之间的大小关系就显而易见了。

代码

int isLessOrEqual(int x, int y) {int sign1 = ((x >> 31) & 1) & ((y >> 31) ^ 1);  // sign1 = (x < 0 && y > 0) ? 1 : 0;int sign2 = ((x >> 31) ^ 1) & ((y >> 31) & 1);  // sign2 = (x > 0 && y < 0) ? 1 : 0;int z = x + ~y + 1;                             // z = x - yint sub = !(x ^ y) | ((z >> 31) & 1);           // z <= 0    return (sub | sign1) & !sign2;
}

logicalNeg

思路

这题从二进制位的角度不好思考,不妨从其表示的十进制数的角度出发:

当 x = 0 时,-x = x ,即 x 和 -x 的最高位相同,都为 0;当 x != 0 时,x 和 -x 的最高位必定有一个为 1。

可以利用这一特性将 x | nx 右移 31 位,由于整数进行的是符号右移,因此当最高位为 0 时,右移的结果全为 0,当最高位为 1 时,右移的结果全为 1。再将右移结果加 1,即可构造出 1 或者 0,且刚好与零和非零对应。

代码

int logicalNeg(int x) {int nx = ~x + 1;return ((x | nx) >> 31) + 1;
}

howManyBits

思路

这题看到限制 90 个运算符就给吓着了,实际上也确实很困难,自己想了半天也没有思路,于是在网上参考了别人的解法,感觉相当精妙,在这里介绍一番:

对于正整数 x 而言,可以使用二分搜索的方式来确定所需的位数。首先判断 x 是否需要 16 位来表示,即 x 右移 16 位是否为 0,如果是,则右移 16 位,否则不做处理,然后再判断是否需要 8 位来处理,以此类推。最后将上述过程中的右移次数累加起来再加一(正整数首位需要为 0),即为总共需要的位数。

对于负整数 x 而言,它所需的位数与 x 取反得到的整数所需位数相同,证明没整明白。。。

代码

int howManyBits(int x) {int absx = (x >> 31) ^ x;int b16, b8, b4, b2, b1, b0;// 二分搜索b16 = (!!(absx >> 16)) << 4;absx = absx >> b16;b8 = (!!(absx >> 8)) << 3;absx = absx >> b8;b4 = (!!(absx >> 4)) << 2;absx = absx >> b4;b2 = (!!(absx >> 2)) << 1;absx = absx >> b2;b1 = (!!(absx >> 1));absx = absx >> b1;b0 = absx;return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

floatScale2

思路

这题主要是要对规格化数和非规格化数进行分类讨论:

当 uf 为规格化数,即阶码不为 0 时,乘二相当于将阶码位加 1。

当 uf 为非规格化数,即阶码为 0 时,此时 uf 的值完全由尾数来表示,且不含隐含 0,因此乘二相当于将尾数乘二,即左移 1 位。

需要注意的是,当 uf 为非规格化数且尾数最高位为 1 时,尾数左移会导致最高位的 1 移动到阶码的最低位。但经过验证,此时的结果仍然符合预期,即非规格化数无缝衔接到了规格化数,不禁感叹 IEEE 754 标准浮点数的设计之精妙。

代码

unsigned floatScale2(unsigned uf) {unsigned t = (uf >> 23) & 0xff;  // 阶码unsigned m = uf & 0x7fffff;      // 尾数if (t == 0xff) return uf;        // 无穷大或者 NaN// 非规格化数if (t == 0x00) {m <<= 1;uf &= 0xff800000;uf |= m;}// 规格化数else {t += 1;uf &= 0x807fffff;uf |= (t << 23);}return uf;
}

floatFloat2Int

思路

首先确定整数所能表示的上下界的值:当阶码小于 127,即指数位小于 0 时,此时浮点数 uf 小于 1,对应的整数为 0;当阶码大于 150,即指数位大于 23 时,此时单精度浮点数的精度(尾数长度)不足以正确表示对应的整数,返回 0x80000000。

对于在合理范围内的 uf,将其转换为对应的整数,首先需要尾数最高位的高一位加上规格化数隐含的 1,再根据阶码的大小将尾数进行右移,阶码越大,右移位数越少。最后根据符号位的值选择是否将结果取反加一。

代码

int floatFloat2Int(unsigned uf) {unsigned s = (uf >> 31) & 0x1;   // 符号unsigned t = (uf >> 23) & 0xff;  // 阶码unsigned m = uf & 0x7fffff;      // 尾数int val;// 小于 1if (t < 127) {val = 0;}// 大于 1 且不溢出else if (t <= 150) {val = m | 0x800000;val >>= (23 - (t - 127));if (s == 1) {val = ~val + 1;}}// 溢出else {val = 0x80000000;}return val;
}

floatPower2

思路

同样是对规格化数和非规格化数的分类讨论:

x >= -150 && x < -127 时,结果为非规格化数,此时浮点数表示只有一个位为 1,其余全为 0。直接根据指数 x 的值确定该位的位置即可。

x >= -127 && x < 128 时,结果为规格化数,此时浮点数表示的尾数全为 0,只有阶码用来表示指数的值。根据指数 x 的值确定阶码的值,然后构造出浮点数即可。

代码

unsigned floatPower2(int x) {unsigned val;// 太小if (x < -150) {val = 0;}// 非规格化数else if (x < -127) {val = 1 << (150 + x);}// 规格化数else if (x < 128) {unsigned t = x + 127;val |= (t << 23);}// 太大else {val = 0x7f800000;}return val;
}

这篇关于CSAPP Data Lab的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127537

相关文章

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

CentOS下mysql数据库data目录迁移

https://my.oschina.net/u/873762/blog/180388        公司新上线一个资讯网站,独立主机,raid5,lamp架构。由于资讯网是面向小行业,初步估计一两年内访问量压力不大,故,在做服务器系统搭建的时候,只是简单分出一个独立的data区作为数据库和网站程序的专区,其他按照linux的默认分区。apache,mysql,php均使用yum安装(也尝试

使用Spring Boot集成Spring Data JPA和单例模式构建库存管理系统

引言 在企业级应用开发中,数据库操作是非常重要的一环。Spring Data JPA提供了一种简化的方式来进行数据库交互,它使得开发者无需编写复杂的JPA代码就可以完成常见的CRUD操作。此外,设计模式如单例模式可以帮助我们更好地管理和控制对象的创建过程,从而提高系统的性能和可维护性。本文将展示如何结合Spring Boot、Spring Data JPA以及单例模式来构建一个基本的库存管理系统

15 组件的切换和对组件的data的使用

划重点 a 标签的使用事件修饰符组件的定义组件的切换:登录 / 注册 泡椒鱼头 :微辣 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta http-equiv="X-UA-

12C 新特性,MOVE DATAFILE 在线移动 包括system, 附带改名 NID ,cdb_data_files视图坏了

ALTER DATABASE MOVE DATAFILE  可以改名 可以move file,全部一个命令。 resue 可以重用,keep好像不生效!!! system照移动不误-------- SQL> select file_name, status, online_status from dba_data_files where tablespace_name='SYSTEM'

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构:字节 ➡️领域: Information systems → Data management systemsStorage management 📚摘要:介绍了字节新提出的ByteGraph 3.0(BG3)模型,用来处理大规模图结构数据 背景

java.sql.SQLException: No data found

Java代码如下: package com.accord.utils;import java.sql.Connection;import java.sql.DriverManager;import java.sql.PreparedStatement;import java.sql.ResultSet;import java.sql.ResultSetMetaData;import

FORM的ENCTYPE=multipart/form-data 时request.getParameter()值为null问题的解决

此情况发生于前台表单传送至后台java servlet处理: 问题:当Form需要FileUpload上传文件同时上传表单其他控件数据时,由于设置了ENCTYPE=”multipart/form-data” 属性,后台request.getParameter()获取的值为null 上传文件的参考代码:http://www.runoob.com/jsp/jsp-file-uploading.ht

Oracle Data Guard:Oracle数据库的高可用性和灾难恢复解决方案

在企业级数据库管理中,确保数据的高可用性和在灾难情况下的快速恢复是至关重要的。Oracle Data Guard是Oracle公司提供的一种强大的数据库高可用性解决方案,它通过在主数据库和至少一个备用数据库之间提供实时或近实时的数据保护来实现这一目标。本文将详细介绍如何在Oracle数据库中部署和使用Oracle Data Guard,包括其基本概念、配置步骤、管理技巧和实际应用示例。 1. O

Creating OpenAI Gym Environment from Map Data

题意:从地图数据创建 OpenAI Gym 环境 问题背景: I am just starting out with reinforcement learning and trying to create a custom environment with OpenAI gym. However, I am stumped with trying to create an enviro