进制只是“数数的规则”，就像我们日常用十进制（逢10进1），计算机底层用二进制（逢2进1）
一、进制转换：二进制、八进制、十六进制
本质：进制只是“数数的规则”，就像我们日常用十进制（逢10进1），计算机底层用二进制（逢2进1）。
| 进制 | 基数 | 数字范围 | 特点 |
|---|---|---|---|
| 二进制（Binary） | 2 | 0, 1 | 计算机唯一能直接识别的，对应开关（开=1，关=0） |
| 八进制（Octal） | 8 | 0–7 | 已较少用，但1位八进制 = 3位二进制（因8=238 = 2^38=23） |
| 十六进制（Hex） | 16 | 0–9, A–F（A=10, B=11, …, F=15） | 1位十六进制 = 4位二进制（因16=2416 = 2^416=24），简洁表达长串二进制（如内存地址、颜色码#FF5733） |
✅转换方法（通俗口诀）：
二 → 八：从右向左，每3位一组，补零凑齐 → 每组转为1个八进制数字
例：101101₂→ 分组101 | 101→ 补前导零成001 | 011 | 010？错！应从右分：101101→101 | 101（共6位，刚好两组）→5 | 5→55₈二 → 十六：从右向左，每4位一组 → 每组转1个十六进制数字
例：11010111₂→1101 | 0111→D | 7→D7₁₆八/十六 → 二：反向展开（每位→固定位数二进制）
例：27₈→010 | 111→010111₂；A3₁₆→1010 | 0011→10100011₂任意进制 ↔ 十进制：按权展开（位置从右起编号0,1,2…，权重 = 基数^位置）
例：1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8+0+2+1 = 11₁₀2F₁₆ = 2×16¹ + 15×16⁰ = 32 + 15 = 47₁₀
二、补码（Two’s Complement）——计算机存负数的标准方式
🔹为什么需要补码？
避免+0/-0两种表示；让减法变加法（硬件只需加法器）；符号位自然参与运算。
🔹定义（n位有符号整数）：
- 正数（含0）：原码 = 反码 = 补码（最高位为0）
- 负数：补码 = 反码 + 1；而反码 = 原码（除符号位外）各位取反
✅计算步骤（以8位为例）：
+5：原码00000101→ 补码00000101-5：- 原码（符号位1+绝对值）：
10000101 - 反码（符号位不变，其余取反）：
11111010 - 补码（反码+1）：
11111011
- 原码（符号位1+绝对值）：
✅表示范围（n位补码）：
- 最小值：
−2^(n−1) - 最大值：
2^(n−1) − 1 - 8位：
−128到+127（共256个数，无歧义） - 16位：
−32768到+32767
💡验证：−128的8位补码是10000000（无法用原码表示，但补码可直接定义）；−1是11111111，加1得00000000（溢出归零），完美闭环！
三、四种机器数表示法对比
| 表示法 | 正数 | 负数生成规则 | 0的表示 | 范围（8位） | 优点 | 缺点 |
|---|---|---|---|---|---|---|
| 原码 | 符号位+绝对值 | 符号位=1，数值同正数 | 00000000,10000000（+0/−0） | −127 ~ +127 | 直观易懂 | 零不唯一；减法需额外判断符号 |
| 反码 | 同原码 | 符号位=1，数值位取反 | 00000000,11111111 | −127 ~ +127 | 加减可统一用加法（但需循环进位） | 零不唯一；运算复杂 |
| 补码 | 同原码 | 反码+1 | 仅00000000 | −128 ~ +127 | 零唯一；加减统一；硬件最简 | 理解稍难；负数不能直读数值 |
| 移码（常用于浮点数阶码） | 补码符号位取反 | 移码 = 真值 + 2^(n−1) | 10000000表示0 | −128 ~ +127（但顺序升序） | 阶码大小比较直观（像无符号数） | 不用于普通运算，仅特定场景 |
✅ 实际应用：现代CPU所有整数运算均用补码；IEEE浮点数阶码用移码（偏置码）。
四、IEEE 754 浮点数标准（以单精度32位为例）
结构：1位符号(S) | 8位阶码(E) | 23位尾数(M)
👉 对应公式：
值=(−1)S×(1.M)2×2E−127 \text{值} = (-1)^S \times (1.M)_2 \times 2^{E - 127}值=(−1)S×(1.M)2×2E−127
（隐含前导1，称“规格化数”；E=0或255为特殊值）
🔹关键设计：
- 符号位 S：0=正，1=负
- 阶码 E：8位移码，偏置值=127（即真指数 = E − 127）
- 尾数 M：23位，但实际精度24位（因隐含
1.）
✅举例：5.75的单精度表示
5.75₁₀ = 101.11₂ = 1.0111₂ × 2²- S=0；真指数=2 → E = 2 + 127 = 129 =
10000001₂ - M =
01110000000000000000000（取小数点后23位） - 合并：
0 10000001 01110000000000000000000 - 十六进制：
0x40B80000
⚠️ 特殊值：
E=0, M=0→ ±0E=0, M≠0→ 非规格化数（表示极小数，支持“逐渐下溢”）E=255, M=0→ ±∞E=255, M≠0→ NaN（Not a Number）
五、校验码原理与应用
| 类型 | 原理 | 位数开销 | 检错能力 | 典型应用 |
|---|---|---|---|---|
| 奇偶校验码 | 添加1位使总1的个数为奇/偶 | +1位 | 仅检奇数个错，无法纠错 | UART串口、内存简单校验（EDO DRAM） |
| 海明码（Hamming Code） | 在2^k位置插入校验位，每位校验多个数据位（覆盖范围由位权决定） | 约 log₂(n+k)+1 位 | 可定位并纠正1位错，检2位错 | ECC内存（服务器/工作站）、早期硬盘 |
| CRC（循环冗余校验） | 将数据视为多项式，用预设生成多项式做模2除法，余数作校验码 | 通常16/32位 | 强抗突发错误（如噪声、干扰），检错率极高 | 网络协议（Ethernet, WiFi）、ZIP文件、SD卡 |
✅海明码小例（4位数据d1d2d3d4）：
- 插入校验位 p1(p1在1位), p2(2位), p3(4位) → 总7位：
p1 p2 d1 p3 d2 d3 d4 - p1校验位：1,3,5,7 → 覆盖所有bit中第1位为1的位置（二进制索引）
- 类似地，p2→2,3,6,7；p3→4,5,6,7
- 每个p_i = 对应位异或结果 → 出错时，p3p2p1组合即错误位置（如
101→第5位错）
六、逻辑代数基本运算与化简
| 运算 | 符号 | 规则 | 举例 |
|---|---|---|---|
| 与（AND） | ·或∧ | 全1为1，否则0 | A·B = 1仅当 A=1且B=1 |
| 或（OR） | +或∨ | 全0为0，否则1 | A+B = 0仅当 A=0且B=0 |
| 非（NOT） | ¬或′ | 取反 | A′ = 1当 A=0 |
| 异或（XOR） | ⊕ | 相异为1，相同为0 | A⊕B = A′B + AB′；1⊕1=0,1⊕0=1 |
✅化简技巧（布尔代数定律）：
- 吸收律：
A + AB = A - 摩根律：
(AB)′ = A′ + B′；(A+B)′ = A′B′ - 配项法：
AB + A′C + BC = AB + A′C（因为BC被前两项吸收）
🔹例题化简：F = A′B′C′ + A′B′C + AB′C′ + AB′C
→ 提取A′B′(C′+C) + AB′(C′+C) = A′B′ + AB′ = B′(A′ + A) = B′
✅ 结果极简：F = B′
七、排列组合 & 概率论在算法中的作用
排列组合应用：
- 算法时间复杂度分析：冒泡排序比较次数 = C(n,2) = n(n−1)/2
- 密码学：密钥空间大小 = 排列数（如AES-128密钥数 = 2¹²⁸）
- 随机算法：洗牌算法（Fisher-Yates）依赖等概率排列
- 图论：哈密顿路径计数是NP-hard，本质是全排列约束问题
概率论在算法分析中至关重要：
- 随机化算法：快速排序随机选基准 → 期望时间 O(n log n)，避免最坏O(n²)
- 蒙特卡洛/拉斯维加斯算法：用概率保证正确性或运行时间（如素数测试Miller-Rabin）
- 负载均衡：散列表冲突概率分析（生日悖论）指导扩容阈值
- 机器学习：贝叶斯推断、EM算法、dropout正则化均基于概率建模
八、命题逻辑 vs 谓词逻辑
| 维度 | 命题逻辑（Propositional Logic） | 谓词逻辑（First-Order Logic, FOL） |
|---|---|---|
| 基本单位 | 原子命题（P, Q, R），真假值 | 谓词（P(x), Loves(x,y)）、变量、量词（∀, ∃）、函数 |
| 表达能力 | 只能描述简单事实关系（如 P→Q） | 可表达“所有人类都会死”：∀x (Human(x) → Mortal(x)) |
| 程序设计应用 | 条件语句、断言（assert x > 0）、电路设计（门级逻辑） | 形式化验证（TLA+, Coq）、数据库查询（SQL语义）、AI知识表示（Prolog） |
| 局限性 | 无法刻画内部结构或量化对象 | 更强，但判定问题不可判定（哥德尔不完备性） |
✅ 实际案例：
- 编译器优化中，用命题逻辑做常量传播（
x=5; y=x+1⇒y=6） - 安全协议验证（如Needham-Schroeder）必须用谓词逻辑建模主体、密钥、时间戳等
九、矩阵运算在计算机图形学中的核心应用
所有3D变换 =4×4齐次矩阵 × 齐次坐标向量（(x,y,z,1)ᵀ）
| 变换 | 矩阵形式 | 说明 |
|---|---|---|
| 平移（Tx,Ty,Tz） | [[1,0,0,Tx], [0,1,0,Ty], [0,0,1,Tz], [0,0,0,1]] | 普通3×3矩阵无法表示平移，齐次坐标解决！ |
| 旋转（绕x轴θ） | [[1,0,0,0], [0,c,−s,0], [0,s,c,0], [0,0,0,1]]（c=cosθ, s=sinθ） | 同理可写绕y/z轴矩阵 |
| 缩放（Sx,Sy,Sz） | diag(Sx,Sy,Sz,1) | |
| 投影（透视） | 复杂非线性 → 用矩阵实现“除以w”效果（GPU自动执行） | 如OpenGL透视矩阵将远近裁剪面映射到[−1,1]³ |
✅管线流程：
局部坐标 → 模型矩阵 → 世界坐标 → 视图矩阵 → 相机坐标 → 投影矩阵 → 标准设备坐标 → 视口变换 → 屏幕坐标
✨ 所有变换可合并为一个 MVP 矩阵（Model-View-Projection），一次乘法完成！
十、数值计算误差与插值方法
🔹误差来源：
- 模型误差：数学模型本身简化现实（如忽略空气阻力）
- 截断误差：算法近似（如用泰勒前3项代替sin x）
- 舍入误差：有限精度浮点表示（
0.1 + 0.2 ≠ 0.3） - 数据误差：输入测量不准（传感器噪声）
- 累积误差：迭代中误差放大（如病态方程组求解）
🔹常用插值法：
| 方法 | 公式特点 | 优缺点 | 应用 |
|---|---|---|---|
| 线性插值 | 两点连直线：f(x) ≈ f₀ + (f₁−f₀)(x−x₀)/(x₁−x₀) | 简单快，但不光滑 | 游戏动画帧间过渡、ADC采样重建 |
| 拉格朗日插值 | 构造n次多项式通过n+1个点：L(x) = Σ yᵢ·ℓᵢ(x) | 精确过所有点，但高次易振荡（龙格现象） | 小数据点拟合、秘密共享（Shamir方案） |
| 牛顿插值（差商） | N(x) = a₀ + a₁(x−x₀) + a₂(x−x₀)(x−x₁) + ... | 易增删节点，数值稳定 | 工程查表、自适应网格生成 |
| 三次样条插值 | 分段三次多项式，保证C²连续（位置、斜率、曲率连续） | 光滑自然，无振荡 | CAD建模、字体轮廓（TrueType）、机器人轨迹规划 |