logo

计算机基础补全 [WIP]

Thu Nov 02 2023 Posted last year

本文是关于《程序员的必修课》这本小册的简要记录。

二进制 #

N 进制的特点：

  1. 最大数字是 N-1，大于 N 就用两位数表示；高位的数字是低位的 N 倍。
  2. 任意一个数字，它的大小就是各个位置的数字，乘以 N 的这个位置（从低位到高位的位置）减 1 次方的和。

比如二进制： $$ abc=a×2 ^2+b×2 ^1+c×2 ^0 $$ 之所以采取二进制，是因为计算机底层基于晶体管实现，可以把晶体管理解为开关，1 代表开，0 代表关。

p 与 q 等于取交集，全部为 1 才为 1；p 或 q 等于取并集，全部为 0 才为 0。因此，对于二进制可以得出： $$ 100∩011=000，100∪011=111 $$ 如果数 x 是 2 的 n 次方，那么 x 的最高位就是 1，其余位全是 0，所以 x-1 的最高位是 0，其余位都是 1。设 x = 10000，则 x-1 = 01111，也就是说 10000 ∩ 01111 = 0，即 x ∩ (x-1) = 0

// 判断某数是否为 2 的 n 次方
function isPowerOfTwo(n) {
    return n > 0 && ((n & (n - 1)) === 0)
}

编码（原码、反码、补码） #

  • 原码：就是数字本身。比如 1110 的原码就是 1110。
  • 反码：将原码除符号位按位取反就是反码。比如 1110 的反码是 1001。
  • 补码：将反码加 1 就是补码。比如 1110 的反码是 1001，补码就是 1010。

正数的原码、反码、补码都相同，都等于原码；负数的反码等于除符号位按位取反，负数的补码等于反码末位加1。

补码的存在是为了简化减法运算（计算机只有加法器，没有减法器），即使用补码可以把减法变成加法。原理就是数 A 减去数 B 等于数 A 加上数 B 的补码，然后砍掉最高位。以十进制为例：十进制的补码等于用 9 减去各个位置的数字后末位再加 1，所以 81-21=81+(78+1)=81+79=160，去掉最高位的 1，结果就是 60。

套用到二进制上则是按位取反，末位再加 1。

比如 0110 - 0001，-0001 的原码为 1001，补码也就是 1111，换成补码计算就是 0110 + 1111，结果为 10101，去除最高位的结果是 0101，可以看到计算结果是正确的。也就是说 0110 - 0001 = 0110 +1111，而 0110 -0001 = 0110 + (-0001)，这也就意味着 -0001 等于 1111。于是我们可以得出这么一条结论：如果用补码表示二进制，那么高位就表示符号位置：如果高位是 1，就表示负数；如果高位是 0，就表示正数。所以 1111 就表示负数，它对应的原码等于对它再次求补码，1111 的反码是 1000，补码就是 1001，高位是 1，表示负数，所以就是 -0001，所以就有：1111 = (-0001)

事实上，计算机中所有的数字都是用补码表示，只不过正数的补码等于其原码，所以在一般计算中只需要注意负数就可以了。

位运算 #

按位与 & #

将各个数位的数字进行逻辑与，都是 1 才为 1，否则为 0。比如 110&011=010 ，1111&111=0111

使用与运算可以消除指定位置的数字。也可以判断是否具有某个标记。

比如如果我们需要取一个 8 位数的高 4 位，就可以让它和 1111 0000 进行按位与运算，运算后它的低 4 位一定是 0，而 高4 位则会保持不变，也就相当于消除了它的低 4 位，只取了它的高 4 位。

const vip = 0b00000001
const svip= 0b00000011

function isVip(flag) {
  return (vip & flag) === vip
}

function isSvip(flag) {
  return (svip & flag) === svip
}

console.log(isVip(0b11111111)) // true

按位或 | #

将各个数位的数字进行逻辑或，都是 0 才为 0，否则为 1。比如 110∣011=111，1111∣111=1111

使用或运算可以给指定位置添加标记。

比如我们要把 0011 1001 的低 4 位全部置为 1，而高 4 位不变，那么就可以 0011 1001|0000 1111=0011 1111

const svip= 0b00000011

function setSvip(flag) {
    return svip | flag
}

console.log(setSvip(0b00000000).toString(2)) // 11 即 00000011

异或 ^ #

将各个位置数字进行异或，相同为 0，不同为 1。比如 1111 ^ 1111 = 0000，0000 ^ 1111 = 1111

一个数和 0 异或等于它本身。一个数和自身异或等于 0。

let a = 10
let b = 20

a = a ^ b;
b = a ^ b;
a = a ^ b;

console.log(a, b) // 20,10
  • a = a ^ b; 此时 a 就是 a^b;
  • b = a ^ b; 也就是 b = (a^b)^b = a^b^b = a^(b^b)；而相同的数字异或等于 0，那就是 a^0，也就是 a，此时 b=a 了。
  • a = a ^ b; 此时经过第一步运算 a=a^b，经过第二步运算 b=a，所以 a = a^a^b = 0^b，也就是 b。
function findUniqueNumber(nums) {
   let result = nums[0];
   for (let i = 1; i < nums.length; i++){
       result ^= nums[i];
   }
   return result;
}

console.log(findUniqueNumber([1,3,4,2,6,3,2,1,4])) // 6

非 ! #

将所有位置的数字取反，原来是 0 就变为 1，原来是 1 就变为 0。

左移 << #

将所有数字向左边移动 n 位，右边补 0。

在 2 进制中，左移动 n 位，就等于乘以 2 的 n 次方倍。

比如计算 a * 15 时，可以计算为 a << 4 - a

右移 >> #

将所有数字向右边移动 n 位，左边补符号位，正数就补 0，负数就补 1。比如：0111>>1=0011，因为是正数，所以左边补 0。

但对于负数的右移要转为补码来计算。

比如：要计算-5右移1位，

  • 先计算-5的补码，也就是1011
  • 执行位运算: 1011>>1=1101，因为1011是负数，所以高位补1
  • 再把1101求一次补码，得到原码: 1011，因为1101是负数，所以就是-3。

如何快速计算负数的右移：先使用正数做右移，完了再转成负数就行了

比如，还是-5，我们想除以2，我们可以先计算5的右移:

0101>>1=0010，也就是2，也就是0010，我们把最高位符号位改为1，就是1010，也就是-2的原码，这样我们就计算出了-5除以2的结果。

正数的右移运算等于做除法，负数的右移不等于做除法。

在 2 进制中，正数右移 n 位，就等于除以 2 的 n 次方倍。

无符号右移 >>> #

无符号右移跟右移一样，只不过左边永远补 0。比如 1111 0100 >>> 4 = 0000 1111

移位运算分为逻辑移位和算数移位，如果你用二进制表示数值，那么高位就是符号位，此时为算术移位，右移则高位补符号位。如果你用二进制表示逻辑，比如上述的flag，那此时就是逻辑移位，右移则高位永远补0。

数据类型 #

以下类型以 Java 为准

值类型 #

  • 比特类型（byte）：8 位二进制。
  • 短整型（short int）：16 位二进制。
  • 整型（int）：32 位二进制。
  • 长整型（long）：64 位二进制。
  • 布尔类型（boolean）：默认是使用 int 表示的，也就是 32 位二进制。
  • 字符类型（char）：16 位二进制。
  • 单精度浮点（float）：32 位二进制。
  • 双精度浮点（double）64 位二进制。

其中，我们将 8 位二进制称作一个字节，也就是 1byte，也就是: 1byte = 8bit，也就是 8 个二进制位；因为最高位要用来表示符号位，所以，1 个 byte 的大小范围就是 $−2^7 \sim 2^7−1$

引用类型 #

  • 字符串
  • 数组
  • 对象

字符串略过，与 JS 的字符串有所不同，Java 中的字符串本质上是引用类型，但被编译器做了特殊处理（字符串改变时会开辟一个新的内存地址，只改变变量的指向），所以看上去像是基本类型。

数组会占用一块连续的内存空间，所以只需要知道第一个元素的位置，就可以根据数组存储的变量类型的大小计算出数组中每个元素在内存中的地址了。优点是读取快，因为它是连续的内存地址。缺点是内存要求高，拓展性较差，不如链表。

对象具有生命周期，亦或者说作用域，局部变量的作用域仅限于它所在的函数（这里指 Java）。当一个对象不再被引用时会被垃圾回收。

如何挑选数据类型 #

优先考虑空间筛选，即在满足需求的情况下优先选择更小的数据类型，比如性别只需要两种标识，所以可以使用 byte 来标识，0 表示女，1 表示男。同时，我们也应该优先选择容易改变的数据类型，比如链表相较于数组就更容易进行拓展（数组需要指定长度来分配内存，而链表不需要）

其次应该考虑时间筛选，即优先选择数字类型。因为数字类型在进行算数运算、逻辑运算或者比较运算时效率更高，并且也方便使用效率更高的移位操作。

代码运行流程 #

代码就是使用控制语句去操作数据类型来实现特定的逻辑，并交其给计算器去执行。即高级语言 => 机器码 => 放入内存 => CPU 执行

其中 CPU 由三部分组成：控制器、运算器以及寄存器

控制器 #

顾名思义，用来控制程序的执行流程

程序计数器是控制器的一部分，它的作用是控制代码被编译为机器码后，当前该执行哪一行。

const a = 10
const b = 10
const c = a + b

image-20231102212551703

在代码的执行过程中，每执行一行代码，程序计数器就会加 1，当执行的指令占据多个内存地址时，就会增加与指令长度相应的数值。然后，控制器就会参照程序计数器的数值，从内存中读取命令并执行。也就是说，程序计数器决定着程序的流程。

运算器 #

运算器的作用就是执行运算，以上面的代码为例，执行到 0102 时运算器会把两个值从寄存器中取出，然后进行加法运算，之后再把结果放入寄存器。

寄存器 #

寄存器内存放着从内存中读取的数据，但数据并不是直接从内存读到寄存器的，而是先读入到一个高速缓存中再读入寄存器。CPU 会预先把数据读入高速缓存中，当真正用到的时候，再从高速缓存中读入寄存器以供使用，当寄存器使用完毕后，会再把数据写回到高速缓存中，然后高速缓存会在合适的时机把数据写入到存储器。

程序的执行流 #

我们的代码先被编译成一条一条的指令，要执行的时候就先读入高速缓存，然后将要执行的指令地址放在程序计数器中，控制器控制着这些指令按序执行，遇到数据就读入寄存器来让运算器执行，执行完毕后就放回寄存器执行下一条，全部执行完毕后就把数据写回高速缓存，高速缓存在合适时机就将数据同步回内存。

程序的执行流程可以分为三种：顺序执行、条件分支以及循环执行。

const a = 2
const b = 10
let c
if(a > 3) {
    c = a + b
} else {
    c = 2 * a
}

image-20231102213446472

在执行到指令 0102 时候，由于不满足a>3这个条件，就直接跳转到 0104 这个指令去执行了；而且，计算机很聪明，如果它在编译期间发现 a 永远不可能大于 3，它就会直接删除 0103 这条指令，然后，0104 这条指令就变成了下一条指令，直接顺序执行，也就是编译器的优化。

计算机中的比较操作，就是做减法，结果大于 0 就是大于，结果小于 0 就是小于，结果等于 0 就是相等。

const a = 10
const b = 10
const sum = add(a, b)
console.log(sum)

function add(num1, num2) {
    return num1 + num2
}

image-20231102213814849

执行函数时使用的是 call 指令，而 call 指令总是会和 return 指令成对出现，即有函数调用一定会要函数返回。

call指令会把调用函数后的下一条指令存入栈中，然后执行函数逻辑，在函数执行完后，return指令会把栈中的下一条指令弹出，并写入程序计数器中，这样就接着执行下一条指令了。

CPU 的指令类型大概分为以下四种：

  • 数据传送指令：执行数据的读取操作，比如从寄存器读数据，将数据写入寄存器。
  • 运算指令：执行算数运算和逻辑运算，比如加法运算，按位与运算，比较运算。
  • 跳转指令：条件分支、循环、跳转等操作。
  • 调用/返回指令：函数调用/返回操作。

面向过程与面向对象 #

需求修改不频繁时可以使用面向过程，因为效率更高。

面向对象 #

  • 封装。将具体的事物抽象为类，并且设置权限。
  • 继承。让一个类拥有另一个类的数据和函数，增加代码复用性。
  • 多态。一个类的子类可以有不同表现，增加代码拓展性。

继承与实现的关系：实现接口代表类具有某种功能，继承则表示子类本质上就是父类。

数据结构 #

线性数据结构 #

数据元素之间的关系是一对一。

1. 顺序表 #

顺序表是紧密相邻的线性数据结构。便于查找元素，不便于插入和删除元素。比如数组的实现就是顺序表。

2. 链表 #

链表是非直接相邻的顺序表。便于插入删除，不便于查找。

3. 栈 #

栈是先进后出（FILO）的线性结构。适合用来模拟历史的回溯，即向上追溯历史。常见的场景如函数的调用栈，最先被调用的函数一定最后返回。

4. 队列 #

队列是先进先出（FIFO）的线性结构。适合用来模拟历史的回放，即按照顺序将历史重演一遍。

非线性数据结构 #

数据元素之间的关系是一对多，或者多对多的。

1. 树 #

树是一对多的数据结构。适合有层级关系的场景。

2. 图 #

图是多对多的数据结构。适合没有层级的网状关系。

进程与线程 #

软件分为系统软件和应用软件，操作系统就是系统软件的一种，其他所有的软件都是运行在操作系统之上的，而它的作用有两个：

  1. 负责跟系统硬件进行交互，将用户的操作（鼠标、键盘）告知计算机硬件，并把结果反馈给用户。
  2. 通过管理进程来管理其他的软件。

软件是程序的载体，而每个程序都有一个进程，线程是进程的一部分，线程是操作系统能调度的最小单元。

之所以引入线程的概念，是为了把串行任务变为并行任务，可以有效地提高效率。

  • 串行：一件事同一时刻只有一个人做。
  • 并行：一件事同一时刻有多个人做。

尽管多线程可以提高运行效率，但有个重要前提：程序不存在资源冲突，即多个线程在同一时刻操作同一个资源。这个发生冲突的资源就叫做临界资源。

线程是进程的一部分，是操作系统调度的最小单位。是调度的最小单位，不是持有资源的最小单位。也就是说，资源都是在进程中的，进程是持有资源的最小单位。

解决并发的基本操作 #

资源冲突的充要条件是同一时刻、同一目标，所以解决这个问题只要破坏其中任一条件即可。

破坏同一时间 #

可以通过加锁来限制同时只能有一个线程使用这个资源。

image-20231106174101335

破坏同一目标 #

破坏同一目标的核心就是分散目标，但前提是目标能被拆分。简单来讲就是让读和写的不是同一个目标。具体做法是写时拷贝（copy on write），即在操作资源前先拷贝出来一个新的资源，然后对新的资源进行操作，最后再把新的资源同步到原资源上。（感觉类似于函数式编程中的数据不可变性）

解决并发冲突的工具 #

并发的处理避免不了等待操作，共有两种情况：

  1. 等你完事了喊我一声。（假设会等很长时间，悲观处理）
  2. 我一直在这等着，每隔一段时间问你完没完事。（假设只等很短时间，乐观处理）

悲观锁 #

synchronized 线程会被阻塞

class A {
    int a = 0;
    // 开启一个线程不断增加a的值
    Thread t1 = new Thread() {
        // 加了synchronized关键字
        synchronized void run(){
            for(int i =0; i< 1000_000_000; i++) a++;
        }
    };
    t1.start();
    
    // 开启另一个线程不断增加a的值
    Thread t2 = new Thread() {
        // 加了synchronized关键字
        synchronized void run() {
            for(int i =0; i< 1000_000_000; i++) a++;
        }
    };
    t2.start();
}

乐观锁 #

CAS（Compare and swap）线程不会阻塞，因为线程一直在自旋。

class A {
    int a = 0;
    
    boolean lock = false;
    
    // 开启一个线程不断增加a的值
    Thread t1 = new Thread() {
        void run() {
            // 发现资源被锁了，进行自旋
            while(lock) {
               // ...
            }
            lock = true; // 加锁，防止别的线程操作资源
            for(int i =0; i< 1000_000_000; i++) a++;
            lock = false; // 执行完毕，释放锁
        }
    };
    t1.start();
    
    // 开启另一个线程不断增加a的值
    Thread t2 = new Thread() {
        void run() {
            while(lock) {
                // ...
            }
            lock = true;
            for(int i =0; i< 1000_000_000; i++) a++;
            lock = false;
        }
    };
    t2.start();
}

进程调度算法 #

调度算法指的是：CPU 对进程进行资源分配所采取的策略。

  1. 先来先服务，即优先处理先到达的作业（Job），对长作业有优势。
  2. 短作业优先，即优先处理耗时短的作业，对短作业有优势。
  3. 高优先权优先，即给每一个作业加权，优先处理权重大的作业。权重分为动态优先权和静态优先权。
  4. 高响应比优先，即根据每个作业的等待时间和执行时间计算出响应比，优先处理响应比大的作业。响应比 = (等待时间+执行时间) / 执行时间
  5. 时间片轮转，即给每个作业分配一小段时间执行，执行完了就让下一个作业执行，简单来讲就是并发执行。并发与并行的区别：并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生。并行是真正的并行，而并发是宏观上并行、微观上串行。

计算机网络 #

计算机网络的分类：

  • 广域网：覆盖几十到几千公里，比如我们日常说的上网，用百度、谷歌等，用的就是广域网。
  • 城域网：一般覆盖一个城市，大约 5 到 50 公里，比如有的城市的宽带。
  • 局域网：一般覆盖一公里左右，比如一个公司的内网。
  • 个人区域网：覆盖范围只有几米，比如自己给自己开热点。

判断网络质量的七个指标：

  • 速率：即传输速度。直接受到材料的影响，比如，相同条件下有线网肯定比无线网快；而同是有线网络，光纤就比电缆快。
  • 带宽：可以简单理解为传输的横切面大小。我们把计算机网络的传输看作是一个水管，速率就是传输的速度，带宽就是水管横切面大小，越大传输得肯定越快。
  • 吞吐量：单位时间内通过网络的数据量。这才是真正的传输速度，如果水管生锈了，那么速率是 100，也达不到 100，因为水锈会阻碍一部分传输，而吞吐量就是把所有因素都考虑进去之后，得出的最终的传输速度。
  • 时延：把数据从 A 端发送到 B 端所需要的时间。
  • 时延带宽积：发送数据时的延迟 x 带宽得出的结果。
  • 往返时间：从 A 发数据到 B，到 A 收到 B 的响应所需要的时间。
  • 利用率：网络在传输时信道的利用百分比。

我们把传输信号的介质统一称为：信道

计算机网络协议 #

TCP/IP 协议

  • 应用层
  • 传输层
  • 网络层
  • 数据链路层
  • 物理层

物理层 #

物理层规定传输媒介的一些特性：

  • 机械特性：指明接线器的形状和尺寸、引脚数目、排列方式等。
  • 电气特性：指明每条线上的电压范围。
  • 功能特性：指明每条线上每一个电平表示的意义。
  • 过程特性：指明各种事件的出现顺序。比如，哪根信号线先动，哪根信号线先出现什么电平等。

一般来讲，信道分为三种类型：

  • 单向通信：也叫单工通信，只能从一端到另一端通信，而不能反过来。比如我们收听的收音机广播。
  • 双向交替通信：也叫半双工通信，双端都可以收发，但不能同时进行。
  • 双向同时通信：也叫全双工通信，双方可以同时发送和接收。

数据链路层 #

数据链路层负责将数据透明地、无差错地进行传输。它负责把物理层传输的电子（以二进制形式）封装为数据帧，在数据的前后添加标记作为首部和尾部，同时还会对发送的数据进行差错检测。

网络层 #

网络层负责编址、寻址和转发。首先通过 DNS 来解析目标的 IP 地址，再通过地址映射协议（ARP Address Resolution Protocol）来根据 IP 地址找到对应的主机地址。

传输层 #

传输层的核心作用就是进行数据的传输。传输层需要具体的端口号来传输数据。数据传输有两种传输方式，一种是面向连接的，可靠的 TCP 协议；另一种就是无连接的，不可靠的 UDP 协议。

  • TCP（Transmission Control Protocol）：面向连接的，可靠的。
  • UDP（User Datagram Protocol）：无连接的，不可靠的。

应用层 #

比如 HTTP 协议

TCP 协议的实现 #

TCP 的传输的数据不会有差错并且全部都会被处理。为了实现这两件事，TCP 需要：1. 对传输出错的数据进行重传。2. 控制传输速度，让接收方来得及处理。

超时重传协议 #

即发送方在发送数据之后的规定时间内，如果没有收到接收方的确认，则重新传送数据。

超时重传的核心就是动态地计算超时时间，这部分内容 TCP 内部已经处理好了，所以可以把这个协议称为 自动重传递协议 ARQ（Automatic Repeat-reQuest）

停止等待协议 #

即发送方会调整发送速度，来等待接收方处理完之后，再进行发送。

因为 TCP 是双全工，为了发挥这一优势，TCP 使用了连续 ARQ 协议，而这个协议是基于滑动窗口协议的思想实现的：

  • 解决了什么问题：发送方和接收方速率不匹配时，保证可靠传输和包乱序的问题
  • 机制：接收方根据目前缓冲区大小，通知发送方目前能接收的最大值。发送方根据接收方的处理能力来发送数据。通过这种协调机制，防止接收端处理不过来。
  • 窗口大小：接收方发给发送端的这个值称为窗口大小

image-20231107173447595

ARQ 协议包括停止等待 ARQ 协议和连续 ARQ 协议

三次握手与四次挥手 #

// TODO: 单独写一篇文章