一、进制转换二进制、八进制、十六进制本质进制只是“数数的规则”就像我们日常用十进制逢10进1计算机底层用二进制逢2进1。进制基数数字范围特点二进制Binary20, 1计算机唯一能直接识别的对应开关开1关0八进制Octal80–7已较少用但1位八进制 3位二进制因8238 2^3823十六进制Hex160–9, A–FA10, B11, …, F151位十六进制 4位二进制因162416 2^41624简洁表达长串二进制如内存地址、颜色码#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⁰ 8021 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补码反码111111011✅表示范围n位补码最小值−2^(n−1)最大值2^(n−1) − 18位−128到127共256个数无歧义16位−32768到32767验证−128的8位补码是10000000无法用原码表示但补码可直接定义−1是11111111加1得00000000溢出归零完美闭环三、四种机器数表示法对比表示法正数负数生成规则0的表示范围8位优点缺点原码符号位绝对值符号位1数值同正数00000000,100000000/−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称“规格化数”E0或255为特殊值关键设计符号位 S0正1负阶码 E8位移码偏置值127即真指数 E − 127尾数 M23位但实际精度24位因隐含1.✅举例5.75的单精度表示5.75₁₀ 101.11₂ 1.0111₂ × 2²S0真指数2 → E 2 127 129 10000001₂M 01110000000000000000000取小数点后23位合并0 10000001 01110000000000000000000十六进制0x40B80000⚠️ 特殊值E0, M0→ ±0E0, M≠0→ 非规格化数表示极小数支持“逐渐下溢”E255, M0→ ±∞E255, M≠0→ NaNNot a Number五、校验码原理与应用类型原理位数开销检错能力典型应用奇偶校验码添加1位使总1的个数为奇/偶1位仅检奇数个错无法纠错UART串口、内存简单校验EDO DRAM海明码Hamming Code在2^k位置插入校验位每位校验多个数据位覆盖范围由位权决定约 log₂(nk)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 d4p1校验位1,3,5,7 → 覆盖所有bit中第1位为1的位置二进制索引类似地p2→2,3,6,7p3→4,5,6,7每个p_i 对应位异或结果 → 出错时p3p2p1组合即错误位置如101→第5位错六、逻辑代数基本运算与化简运算符号规则举例与AND·或∧全1为1否则0A·B 1仅当 A1且B1或OR或∨全0为0否则1AB 0仅当 A0且B0非NOT¬或′取反A′ 1当 A0异或XOR⊕相异为1相同为0A⊕B A′B AB′1⊕10,1⊕01✅化简技巧布尔代数定律吸收律A AB A摩根律(AB)′ A′ B′(AB)′ 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局限性无法刻画内部结构或量化对象更强但判定问题不可判定哥德尔不完备性✅ 实际案例编译器优化中用命题逻辑做常量传播x5; yx1⇒y6安全协议验证如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]]ccosθ, ssinθ同理可写绕y/z轴矩阵缩放Sx,Sy,Szdiag(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次多项式通过n1个点L(x) Σ yᵢ·ℓᵢ(x)精确过所有点但高次易振荡龙格现象小数据点拟合、秘密共享Shamir方案牛顿插值差商N(x) a₀ a₁(x−x₀) a₂(x−x₀)(x−x₁) ...易增删节点数值稳定工程查表、自适应网格生成三次样条插值分段三次多项式保证C²连续位置、斜率、曲率连续光滑自然无振荡CAD建模、字体轮廓TrueType、机器人轨迹规划