Yuchen You

位操作 Bit Manipulation 如果我们要将一个十六进制数 0x2020 取出从低到高第二位的值，我们最直接的方法就是使用 mask, 即 12a = 0x2020;a = a & 0x00F0; 如果要将这几位输出，我们就要 a = a >> 4; 就可以将数据向右 bit shift 4 位，然后我们就可以得到 0x0002 的值 为什么不能用 (a << 8) >> 12? 对于向右位移，我们可能会将超过长度的内容赋值 0, 但是向左位移则不是这样，向左的位移会被认为是 直接扩大数字 如果是 int 数据类型向左位移 100 位，这个等价于 << 100 % 32 因为 int 长 4 字节 32 位，编译器会将这一步截断到 4 位从而不为 0 编译器对于补码的理解 如果输入的数字是一个负数，对其进行 >> 操作得到的结果会和正数情况下不同，编译器会按照补码与否来进行操作，如果是 负数，就会填充 F; 如果是 正数，就会填充 0，因此如果要用循环来进行位提取，负数的终点是 0xFF⋯0\text{x}F ...

在使用抽象数据类型的时候，我们往往会需要考虑数据结构的存取api的使用逻辑，这我就需要考虑栈和队列了 数据的存储有两种形式: 连续的 array 型存储 和 离散的 linked list 型存储，我们接下来也会对比二者的效果 栈 Stack 栈的存储顺序是 LIFO, 即 last in - first out 需要两个指针: 指向栈底的 base_ptr 与 指向栈顶的 top_ptr , 其中 top_ptr 指向的是栈顶的下一个位置(悬空) Method Implementation Array Complexity List Complexity push 1. 可能需要申请二倍空间 2. 或者单纯将数据复制到 top 指针并且向后移动一位 top O(n)O(1) O(1)O(1) pop 向前移动 top 指针 O(1) O(1) top 返回 top 前一个指针并且去引用 O(1) O(1) size 用 top 地址减去 base 地址 O(1) O(1) empty 返回 base_ptr == top_ptr O(1) O(1) ...

ISA 可以看作是连接汇编层代码和硬件的操控指令集合, 例如 汇编会有 ADD r1, r2, r3 的指令，我们利用 ISA 就会将指令转换为 r2 + r3 -> r1 常见分类 Classification x86 架构 由 intel 公司开发，为 32 位处理器，一般在上世纪末的电脑中比较常见 由于 232≈22×230=4×10003=4GB2^{32}\approx 2^2 \times 2^{30} = 4\times 1000^3 = 4GB232≈22×230=4×10003=4GB 即地址循迹的范围小于等于 4GB, 也就是内存大小不超过 4G amd64 架构 由 amd 公司在上世纪发明，一般为 64 位处理器，后面 intel 公司也制造这个架构 现在被大量的 pc 使用 ARM 板 Advanced RISC Machine 设计公司是 arm, 非常适用于移动通信领域, 具有 低成本、高性能、低耗电的特性 现在用于大量的手机等可移动设备使用 近年来的 mac silicone 用 arm 架构 RISC-V 锐克五代 开源 学术界青睐，因为没有昂 ...

对于计算机而言，我们常常会讨论到“磁盘”的概念，磁盘就是存储数据信息的重要电子元件，那么，这里就让我们从头开始，看看怎么存储 1 位的数据，再到怎么存储 1 字节的数据，以后再以此类推，我们就可以做出更大的“寄存器”了 1 位寄存器 首先，我们要明确这个寄存器的必备功能: 写入以及输出 写入应该需要有一个信号，不能随便来一个数据就能写入; 输出也要有一个信号，需要的时候输出 输入实现 首先，在输入的时候如果写入信号为 假，那么我们就要保持输出上一帧的数据 那么我们就要想到使用一个常见的基本电路元件 —— 延迟线，即能将输入的信号晚一帧输出 如果将一个延迟线首尾相连并在这个回路中接入一个输入信号(不考虑不输出时候的短路可能性)，那么这个回路就会实现锁存. 但是这时候我们就会面临一个数据选择的问题: 锁存还是更新？那么我们就用一个数据选择器进行分流，通过 写入 信号对选择器控制 这样我们就实现了1位信号的存储 输出实现 这个很简单，我们使用二进制开关就能明确数据输出与否 8 位寄存器 很简单，我们将8个1位寄存器并联就得到了8位寄存器 计数器 我们需要一个优秀的电子元件来记录我们做了一项 ...

继电器 relay 输入小电流，输出大电流，起到中继的作用 为什么bug和虫子是一个意思？ 在早期ibm制造的继电器计算机中，经常会在故障的继电器中找到死掉的虫子，于是我们称计算机的问题为 bug 真空管 热电子发射是真空条件下加热金属的时候电子从材料表面逸出的现象 每一秒可以开闭数千次 与非门 符号 NAND 这是一切逻辑门的基础，我们首先要用原理图来认识它 从这里我们可以看出与非门最简单的形式就是采用两个开关进行控制，但是电路里面要实现自动化，我们就不能用销号人力的开关了，不如使用三极管，通过给基极传输高低电平实现通断来完成开关的功能 TTL 与 CMOS 控制 以下两个电路我们分别使用 TTL 和 CMOS 电路来实现功能 非门 通过将与非门两个输入端接入输入信号就是非逻辑了 与门 将与非门和非门串联 或非门 通过 德摩根定律，利用 A‾+B‾=A⋅B‾\overline{A}+ \overline{B} = \overline{A \cdot B}A+B=A⋅B 我们可以用两个输入分别取非逻辑实现或非门 或门 通过串联或非门和非门实现 恒高电平 ON 将非和原逻辑接入或 ...

全加器 考虑进位的加法称为全加，能够完成全加运算的电路称为全加器，一个基本全加器能够完成两个一位二进制数的全加运算，因此它具有三个输入端和两个输出端，其中 Xi,YiX_i, Y_iXi​,Yi​ 为加数，Ci−1C_{i - 1}Ci−1​ 相邻低位进来的进位数， SiS_iSi​ 为输出和，CiC_iCi​ 为向高位邻位进位数 和位 我们称 s 是和位输出，计算方法是对于 x_i, y_i c_i-1 的异或结果 s=x⊕y⊕cs = x\oplus y\oplus c s=x⊕y⊕c 那么在实际电路中我们只有二元输入的异或门，那么我们就可以用两个异或门进行组合完成 12xor g1(a,x,y);xor g2(s,a,c); 进位位 在三个变量中有两个变量是1的时候发生进位 c=(x⋅y)+(x⋅c)+(y⋅c)c = (x\cdot y) + (x\cdot c) + (y\cdot c) c=(x⋅y)+(x⋅c)+(y⋅c) 考虑到我们需要使用尽量少的逻辑门，那么我们需要对这个逻辑表达式进行化简 c=x⋅y+x⋅c+y⋅c=x⋅y+c⋅(x+y)c = x\cdot y + ...

O(1) — 常量空间复杂度 不管输入数据的规模如何，算法所需的内存空间大小是固定的。 数组中查找最大元素。这个操作只需要一个变量来保存当前找到的最大值，因此空间复杂度是O(1)。 O(log n) — 对数空间复杂度 需要的空间随输入数据的规模的对数增长。 递归实现的二分查找。在每次递归调用中，问题的规模都减半，因此最大的调用深度是log n，相应地，栈的空间也是O(log n)。 O(n) — 线性空间复杂度 需要的空间与输入数据的规模成正比。 动态数组（如C++中的 std::vector）。动态数组可能需要根据输入数据的数量动态调整大小，其空间复杂度通常是O(n)。 O(n log n) — 线性对数空间复杂度 空间复杂度介于线性和平方之间，通常见于一些特殊的排序算法中。 归并排序。在归并排序中，虽然每次合并操作都需要O(n)的空间，但由于其递归的性质，通常需要O(log n)层递归调用，因此整体的空间复杂度可能表现为O(n log n)。 O(n^2) — 平方空间复杂度 需要的空间与输入数据的规模的平方成正比。 一些特定的算法问题，如存储一个n x n的二维数组。

O(1) 常见的就是直接访问一个数组中某个元素的内容 这种算法一般不会受到输入数据大小的影响 1return array[i]; O(n) 线性时间复杂度，一般是遍历一阶数组中的所有元素 这会随着输入数据量的大小线性增大 O(log n) 对数时间复杂度，一般自常见的是用在对分查找。 或者常见的 m 叉树结构我们有 O(logmn)O(log_m n)O(logm​n) 的时间复杂度 O(n log n) - 线性对数时间复杂度 归并排序或快速排序。 说明：这些排序算法在最好或平均情况下的时间复杂度为n log n。 具体的算法的时间复杂度我们会在后面的细节讲解中提及. O(n^2) - 平方时间复杂度 冒泡排序或选择排序。 说明：这类算法通常涉及双重循环，对每对输入元素都进行操作。 容易搞混的地方在于，我们看每一层循环都容易看出是 一阶复杂度，然后我们会认为直接加起来就是一阶求和还是一阶复杂度，这就不对了 冒泡排序的时间复杂度推导 从最差角度考虑，冒泡排序需要比较 + 替换相邻元素的次数是 (n−1)+⋯+1=n(n−1)2(n - 1) + \cdots + 1 = \frac{n ...