SnowMoon-Haoyu's Blog

09-排序2 Insert or Merge (25 分) According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repe ...

CSAPP6——程序机器级表示2

发表于 2021-08-15 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP

汇编入门（二） x86-64 架构中的整型寄存器如下图所示（暂时不考虑浮点数的部分）仔细看看寄存器的分布，我们可以发现有不同的颜色以及不同的寄存器名称，黄色部分是 16 位寄存器，也就是 16 位处理器 8086 的设计，然后绿色部分是 32 位寄存器（这里我是按照比例画的），给 32 位处理器使用，而蓝色部分是为 64 位处理器设计的。这样的设计保证了令人震惊的向下兼容性，几十年前的 x86 代码现在仍然可以运行！前六个寄存器(%rax, %rbx, %rcx, %rdx, %rsi, %rdi)称为通用寄存器，有其『特定』的用途： %rax(%eax) 用于做累加 %rcx(%ecx) 用于计数 %rdx(%edx) 用于保存数据 %rbx(%ebx) 用于做内存查找的基础地址 %rsi(%esi) 用于保存源索引值 %rdi(%edi) 用于保存目标索引值而 %rsp(%esp) 和 %rbp(%ebp) 则是作为栈指针和基指针来使用的。下面我们通过 movq 这个指令来了解操作数的三种基本类型：立即数(Imm)、寄存器值(Reg)和内存值(Mem)。对于 mo ...

CSAPP5——程序机器级表示

发表于 2021-08-14 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP

从C到机器代码机器代码就是处理器能够直接执行的字节层面上的程序，但是对于人类来说基本上是不可读的，所以把字节按照具体含义进行『翻译』，就成了人类可读的汇编代码。注意这里的用词是『翻译』而不是『编译』，可以认为汇编代码就是机器代码的可读形式。 C->可执行程序： C 语言代码(a.c)经过编译器的处理(gcc -0g -S)成为汇编代码(a.s) 汇编代码(a.s)经过汇编器的处理(gcc 或 as)成为对象程序(a.o) 对象程序(a.o)以及所需静态库(lib.a)经过链接器的处理(gcc 或 ld)最终成为计算机可执行的程序先来看一段C代码及其经过汇编产生的代码 12345678// C 代码*dest = t;// 对应的汇编代码movq %rax, (%rbx)// 对应的对象代码0x40059e: 46 89 03 C 代码的意思很简单，就是把值 t 存储到指针 dest 指向的内存中。对应到汇编代码，就是把 8字节（也就是四个字, Quad words）移动到内存中（这也就是为什叫做 movq）。t 的值保存在寄存器 %rax 中，dest 指向的 ...

数据结构与算法刷题笔记10——排序算法(快排)

发表于 2021-08-13 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 快速排序

快速排序算法思想每次排序先选出一个主元，然后将比主元小的数放到左边，比主元大的放右边然后再分别进入左边右边快排。需要注意的是主元的选取方法，一般是选择头中尾三个数中的中位数，而非固定的某个位置的数字当数据规模剩下的比较小的时候采用其它的排序来完成剩下的排序，防止数据规模不大时候仍然各种递归导致处理得很慢遇到相等的元素也要进行交换，防止得到的两个子集大小相差较大算法实现 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<stdlib.h>#include<stdio.h>void Quick_sort(int *Data,int N);void swap(int *A,int *B);void Qsort(int *Data, int Left, int Right);vo ...

每日一文之影评随笔

发表于 2021-08-12 | 更新于 2023-12-01 | SnowMoonの生活随笔 | 随笔 • 影评

今天不写技术，天天写也累了，今天换换口味，记录一下最近看的电影教父系列首先谈谈这几天看的《教父》系列电影，目前只看了前两部，不过给我的触动也还是挺深的，两代教父有着完全不同的境遇，所谓打江山难，守江山更难呐！一代教父白手起家，从西西里镇被追杀来到当时充满希望和梦想的美国，一步步开始为美国的意大利人提供保护，重感情的品质加上雷厉风行的行事风格，总体感觉一代的维多克里昂是个很可靠的教父，最终的结局也还算可以，在与孙子的玩耍中逝去。二代目虽然继承了一代目的处事能力与判断力，但是对于亲情和家庭的重视不太够，在第二部里众叛亲离，最后柯里昂家族基本只剩下他一个人结局算是比较悲惨的。不过这个人物的形象在这部剧里还是很饱满的金句摘录俗话说教父是男人处世的圣经，个人感觉里面的很多句子确实是非常的有意味，因此将一些金句摘录进来首先就是这句很能体现一代目教父大人的性格的话不抽空陪家人的男人，不是真正的男人。这句话看似是对之前被教训"You can act like a man!"的Johnny说的，实际上是对他的大儿子说的，这也体现了一代目教父维多·柯里昂对于家 ...

数据结构与算法刷题笔记9——排序算法（堆、归并）

发表于 2021-08-11 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 归并排序 • 堆排序

09-排序1 排序 (堆、归并) 题目全文见此文数据结构与算法刷题笔记8——排序（冒泡、插入、希尔）堆排序中心思想选择排序的优化版，选择排序是顺序扫描整个数组，找到最大值然后放到末尾，堆排序是使用了一个最大堆来存储最大值，然后每次找最大值就使用删除首节点的方法，最终继续使用选择排序完成剩下的排序过程。实现代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<stdlib.h>#include<stdio.h>void Heap_sort(int Data[],int N);void PercDown(int *Data,int M,int N);void swap(int *A,int *B);int main(){ int i,N,*Data; scanf("%d\n",&N); Data = (int*)malloc(N*siz ...

CSAPPLAB1——Datalab(下)

发表于 2021-08-10 | 更新于 2023-12-01 | SnowMoonの项目记录 | CSAPP • Datalab

前言：本文为CSAPP3.0配套Lab的刷题笔记，这是第一个lab——Datalab的笔记每个实验题目将采用以下格式来记录题目描述题解和思路解题代码 isLessOrEqual 题目描述如果x<=y，返回1，否则返回题解与思路本来刚开始一看：诶，这简单嘛，让y-x>=0就行了嘛，就想着写个y+x的相反数然后判断它的符号位，然后没想到又是该死的TMin，这该死的按位取反加一仍然为它本身的数字！还有一个原因是如果相减的结果大于Tmax会溢出为负数，也会有错误，所以修改了实现的逻辑分成两种情况：x和y符号相同和不同时：y为正为真 x和y符号相同时：y-x>0为真由于溢出只有在x和y异号的时候才会出现，所以这种方法巧妙的规避了溢出的情况代码 1234567891011121314/* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + ...

CSAPPLAB1——Datalab(上)

发表于 2021-08-09 | 更新于 2023-12-01 | SnowMoonの项目记录 | CSAPP • Datalab

前言：本文为CSAPP3.0配套Lab的刷题笔记，这是第一个lab——Datalab的笔记每个实验题目将采用以下格式来记录题目描述题解和思路解题代码 bitXor 题目描述只使用按位与非逻辑实现按位异或逻辑题解与思路排除掉两个不能通过的逻辑，写成的代码就能通过。即：把x与y相同的答案都否定掉代码 1234567891011//1/* * 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);} tmin 题目描述返回补码表示数字的最小值。题解与思路补码的最小值是符号位为1，其余均为0，所以返回这个数字就行了。我的思路也很简单粗暴，直接通过移位得到代码 1234567891011/* * tmin - ...

CSAPP阅读笔记4——数据编码4

发表于 2021-08-08 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP • 浮点数

浮点数2 舍入对于浮点数的加法和乘法来说，我们可以先计算出准确值，然后转换到合适的精度。在这个过程中，既可能会溢出，也可能需要舍入来满足 frac 的精度。在二进制中，我们舍入到最近的偶数，即如果出现在中间的情况，舍入之后最右边的值要是偶数，对于十进制数，例子如下： 12345 原数值舍入结果原因2.8949999 2.89 #不到一半，正常四舍五入2.8950001 2.90 #超过一般，正常四舍五入2.8950000 2.90 #刚好在一半时，保证最后一位是偶数，所以向上舍入2.8850000 2.88 #刚好在一半时，保证最后一位是偶数，所以向下舍入对于二进制数也是类似的 12345 十进制二进制舍入结果十进制原因2 又 3/32 10.00011 10.00 2 \\不到一半，正常四舍五入2 又 3/16 10.00110 10.01 2 又 1/4 \\超过一般，正常四舍五入2 又 7/8 10.11100 11 ...

CSAPP阅读笔记3——数据编码3

发表于 2021-08-07 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP • 浮点数

浮点数浮点数的定义： d=∑i=−nm2i×did=\sum_{i=-n}^m2^i \times d_i d=i=−n∑m2i×di 这个定义导致我们只有在表示x2k\frac{x}{2^k}2kx时候是精确的，其它数字的小数部分都会变成循环小数。而由于这些数字的编码长度都是有限的，通过这种表达方式表示的浮点数都是有限的。 IEEE 浮点数标准以下内容引用自文章【读薄 CSAPP】壹数据表示 IEEE 的浮点数标准更多是从数值角度来建立的，对于舍入，上溢出和下溢出都有比较统一的处理方法。但与此同时也给硬件优化带来了比较大的困难。因为和平时使用的数制也有一定差异，从理解的角度来看不够直观，但是好在主流的 CPU 都支持浮点数，所以我们不必过多涉及这方面的细节。在 IEEE 标准中，我们用下面的公式来表达浮点数： (−1)sM2E(−1)^sM2^E (−1)sM2E 其中 s 是符号位，决定正负；M 通常是一个值在 [1.0, 2.0) 的小数；E 是次方数。具体编码时结构如下，这里用单精度、双精度和扩展精度为例：其中 s 是符号位，决定正负；M 通常是一个值在 [ ...

CSAPP阅读笔记2——数据编码2

发表于 2021-08-06 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP • 原码 • 补码

整形变量Integer 类型拓展与截取无符号数的零拓展：无符号数转换为更大的数据类型，只需要在开头添加0即可，这种运算也被称为零拓展。 **补码数的符号拓展：**补码数转换为更大的数据类型需要在开头添加最高有效位的值，即：如果为负数，需要在拓展出来的开头位置添加数个1，正数需要添加数个0。截断数字当我们将一个位数为 w 的数字截断为 k 位的数字时，我们会丢弃最高的w-k位。 **截断无符号数：**相当于做mod运算，x′=x mod 2kx'=x\ mod\ 2^kx′=x mod 2k **截断补码数值：**和无符号值相似，不过需要将最高位转换为符号位运算与溢出无符号数字加法：溢出时会丢弃最高位，实际上相当于做了个mod操作 x+wuy={x+y,x+y<2wx+y−2w,2w≤x+y<2w+1x+^u_wy= \left\{ \begin{array}{l} x+y,\quad x+y<2^w\\ x+y-2^w, \quad 2^w\leq x+y<2^{w+1}\\ \end{array} \right. x+wuy ...

CSAPP阅读笔记1——数据编码

发表于 2021-08-05 | 更新于 2024-01-18 | SnowMoonの项目记录 | CSAPP • 原码 • 补码

数据编码假设字长(word size)为 www,也即数据的位数，则二进制向十进制的转换分别是：无符号数： B2U(X)=∑i=0w−1xi⋅2iB2U(X)=\sum_{i=0}^{w-1}x_i\cdot2^i B2U(X)=i=0∑w−1xi⋅2i 有符号数： B2T(X)=−xw−1⋅2w−1+∑i=0w−2xi⋅2iB2T(X)=-x_{w-1}\cdot2^{w-1}+\sum_{i=0}^{w-2}x_i\cdot2^{i} B2T(X)=−xw−1⋅2w−1+i=0∑w−2xi⋅2i 左移：x向左移动k位，丢弃最高的k位，在右端补k个0；逻辑右移：在左端补k个0 算术右移：在左端补k个最高有效位的值 PS：移位操作优先级低于±，无符号数编码定义： B2Uw(x)=∑i=0w−1xi2iB2U_w(x)=\sum_{i=0}^{w-1}x_i2^i B2Uw(x)=i=0∑w−1xi2i 原码：正数是其二进制本身；负数是符号位为1,数值部分取X绝对值的二进制。最高位是符号位，用来确定剩下的位是应该取负权还是正权。 B2Sw(x)=(− ...

C语言函数参数传递的错误与避免

发表于 2021-08-04 | 更新于 2024-06-02 | SnowMoonの计算机基础知识 | 冒泡排序 • C语言 • 指针

今日第二更嘿嘿前言：博主在实现各种排序算法时很多函数的参数传递方法啥的出现了很多记忆的错误，因此停下来总结一下这些容易犯的错误同时方便自己将来复习函数参数的调用调用类型描述传值调用该方法把参数的实际值复制给函数的形式参数。对应下述ERROR1在这种情况下，修改函数内的形式参数不会影响实际参数。引用调用通过指针传递方式，形参为指向实参地址的指针，对应正确写法当对形参的指向操作时，就相当于对实参本身进行的操作。例：利用Swap函数交换变量a，b的常见错误 ERROR1——使用局部变量代替原始变量 123456789101112131415void Sawp_error1(int a,int b){ int tmp; tmp = a; a = b; b = tmp;}int main(){ int a = 10; int b = 20; Sawp_error1(a,b); printf("a = %d\nb = %d\n",a,b); ...

数据结构与算法刷题笔记8——排序（冒泡、插入、希尔）

发表于 2021-08-04 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 插入排序 • 冒泡排序

09-排序1 排序（冒泡、插入、希尔）给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：数据1：只有111个元素；数据2：111111个不相同的整数，测试基本正确性；数据3：10310^3103个随机整数；数据4：10410^4104个随机整数；数据5：10510^5105个随机整数；数据6：10510^5105个顺序整数；数据7：10510^5105个逆序整数；数据8：10510^5105个基本有序的整数；数据9：10510^5105个随机正整数，每个数字不超过100010001000。输入格式: 输入第一行给出正整数N(≤105)(≤10^5)(≤105)，随后一行给出N个（长整型范围内的）整数，其间以空格分隔。输出格式: 在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。输入样例: 123114 981 10 -17 0 -20 29 50 8 43 -5//结尾无空行输出样例: 12-20 -17 -5 0 4 8 10 2 ...

数据结构与算法刷题笔记7——公路村村通

发表于 2021-08-03 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 最小生成树 • Prim • Kruskal

08-图7 公路村村通 (30 分) 前言：本题来自浙大PTA上的数据结构练习题题目描述现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。输入格式: 输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。输入样例: 123456789101112131415166 151 2 51 3 31 4 71 5 41 6 22 3 42 4 62 5 22 6 63 4 63 5 13 6 14 5 104 6 85 6 3结尾无空行输出样例: 112 题目理解与思路本题是最小生成树的问题，可以采用Kruskal算法加并查集实现，或者使用简单的Prim算法实现。本文使用Kruskal算法来解题，代码如下 Kruskal 本解法越写越复杂 ...