SnowMoon-Haoyu's Blog

汇编入门（二） 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 ...

快速排序 算法思想 每次排序先选出一个主元，然后将比主元小的数放到左边，比主元大的放右边然后再分别进入左边右边快排。 需要注意的是 主元的选取方法，一般是选择头中尾三个数中的中位数，而非固定的某个位置的数字 当数据规模剩下的比较小的时候采用其它的排序来完成剩下的排序，防止数据规模不大时候仍然各种递归导致处理得很慢 遇到相等的元素也要进行交换，防止得到的两个子集大小相差较大 算法实现 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 ...

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 ...

前言：本文为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 - ...

浮点数 浮点数的定义： d=∑i=−nm2i×did=\sum_{i=-n}^m2^i \times d_i d=i=−n∑m​2i×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 通常是一个值在 [ ...

数据编码 假设字长(word size)为 www,也即数据的位数，则二进制向十进制的转换分别是： 无符号数： B2U(X)=∑i=0w−1xi⋅2iB2U(X)=\sum_{i=0}^{w-1}x_i\cdot2^i B2U(X)=i=0∑w−1​xi​⋅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−2​xi​⋅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−1​xi​2i 原码：正数是其二进制本身；负数是符号位为1,数值部分取X绝对值的二进制。 最高位是符号位，用来确定剩下的位是应该取负权还是正权。 B2Sw(x)=(− ...

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 ...

07-图6 旅游规划 (25 分) 前言：这篇文章是我的每日一文计划的第七篇文章，已经完成了一周的记录，在废物了几周之后感觉又一次找到了点好好学习的动力和不废物的目标感，希望自己能长期坚持！ PS:在文末我又立了点Flag👀👀，希望过一段时间以后这个Flag能够达成！🥳 题目描述 有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。 输入格式: 输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。 输出格式: 在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。 输入样例: 12345674 5 ...