编程中非常关键、非常常用的数学技巧
1 编程中非常关键、非常常用的数学技巧面向日常写代码含系统/嵌入式时反复出现的数学工具偏可落地与正确性不追求定理证明。需要示例处用C/C涉及未定义行为UB与溢出时会标明。1.1 如何使用本文原理一句话解决什么问题。公式/不变量写对代码前先在纸上写清楚。坑溢出、浮点、有符号/无符号混用。1.2 位运算与 2 的幂最高频1.2.1 解决什么问题标志位、权限掩码、寄存器、协议字段、内存对齐、环形缓冲区索引、快速乘除 2 的幂。1.2.2 核心技巧判断 2 的幂正整数 n/* n 0 时成立 */intis_pow2(unsignedn){returnn!(n(n-1));}向上/向下对齐到 2^kalign 为 2 的幂#includestdint.huintptr_talign_up(uintptr_tx,uintptr_talign){return(xalign-1)~(align-1);}uintptr_talign_down(uintptr_tx,uintptr_talign){returnx~(align-1);}用移位代替乘除 2 的幂仅当语义等价且类型宽度明确unsignedmul_pow2(unsignedx,unsignedk){returnxk;}unsigneddiv_pow2(unsignedx,unsignedk){returnxk;}/* 无符号右移 */设置/清除/翻转/测试某位#defineBIT(n)(1u(n))#defineSET_BIT(v,n)((v)|BIT(n))#defineCLR_BIT(v,n)((v)~BIT(n))#defineFLIP_BIT(v,n)((v)^BIT(n))#defineTEST_BIT(v,n)(((v)BIT(n))!0)1.2.3 实现要点align必须是 2 的幂否则 ~(align-1)无意义。左移1u n时若n 类型位宽是UB协议里位域宽度要限制n。有符号右移在 C 中对负数实现定义算术右移常见但 portable 代码慎用符号位技巧。1.2.4 常用库C20std::has_single_bit、std::bit_ceil、std::popcount。GCC/Clang__builtin_popcount、__builtin_clz嵌入式/内核常见。1.3 补码与有符号整数边界1.3.1 解决什么问题理解INT_MIN、溢出、比较陷阱读硬件寄存器、序列化二进制格式。1.3.2 核心事实32 位示例范围INT32_MIN…INT32_MAXINT32_MIN的绝对值不能用同类型abs()安全表示。无符号减法a - b当a b时按模 (2^{32}) 回绕比较要用同类型或显式转换。#includelimits.h#includestdint.h/* 安全判断 a b 是否溢出 int32a,b 为 int32_t */intadd_overflow_i32(int32_ta,int32_tb,int32_t*out){if(b0aINT32_MAX-b)return1;if(b0aINT32_MIN-b)return1;*outab;return0;}1.3.3 坑size_t与int混比较负int会被提升为大无符号数。嵌入式协议用固定位宽类型uint32_t比int/long更可移植。1.4 模运算与环形索引缓冲区、哈希桶1.4.1 解决什么问题环形队列下标、时间轮、分片取模、避免%开销当模数为 2 的幂时。1.4.2 核心公式环形前进(i 1) % N后退(i N - 1) % N。当N 为 2 的幂时i % N等价于i (N - 1)i为无符号且范围合理时。#defineRING_MASK(N)((N)-1)/* N 必须是 2 的幂 */unsignedring_next(unsignedi,unsignedN){return(i1)RING_MASK(N);}1.4.3 坑i % N中若i为有符号负数C 中%符号实现定义C99 商向零截断余数符号同被除数。哈希hash % bucket_count桶数取质数或2 的幂是两种常见工程选择后者配合位掩码更快。1.5 对数复杂度、二分、树高1.5.1 解决什么问题估计算法步数O(log n)二分、平衡树高度、页表级数、分块次数。1.5.2 核心直觉每次把问题规模减半约需 (\lceil \log_2 n \rceil) 步。二分查找前提索引空间单调有序数组、或答案在某区间上满足单调性。/* 在 [lo, hi] 上找第一个使 pred(mid)true 的位置经典 lower_bound 思想 */size_tlower_bound_size_t(size_tlo,size_thi,int(*pred)(size_tmid,void*ctx),void*ctx){while(lohi){size_tmidlo(hi-lo)/2;/* 防 (lohi) 溢出 */if(pred(mid,ctx))himid;elselomid1;}returnlo;}1.5.3 实现要点用mid lo (hi - lo) / 2而不是(lo hi) / 2避免大整数相加溢出。log2估内存n个元素、每元素s字节 → 至少n*s树/索引额外因子另算。1.6 浮点数比较、误差、特殊值1.6.1 解决什么问题传感器数据、图形、物理仿真避免直接比较浮点。1.6.2 核心技巧相对/绝对误差比较常见实用写法#includemath.hintfloat_near_equal(floata,floatb,floatabs_eps,floatrel_eps){floatdifffabsf(a-b);if(diffabs_eps)return1;floatscalefmaxf(fabsf(a),fabsf(b));returndiffrel_eps*scale;}注意 NaN / Inf#includemath.hintis_finite_float(floatx){returnisfinite(x);}/* 比较前若可能 NaN先过滤NaN 与任何值比较都为 false */1.6.3 坑float累加大量小数会漂移金融/计量有时用定点数或整数分见下节。嵌入式无 FPU 时避免热路径浮点用定点或查表。1.7 定点数嵌入式极常用1.7.1 解决什么问题无 FPU、确定性、可预测周期PID、滤波、音量、坐标缩放。1.7.2 核心表示Q 格式Qn.m表示n位整数 m位小数值 raw / 2^m。例Q16.16用int32_t raw表示缩放因子116。#includestdint.h#defineQ16_SHIFT16#defineQ16_ONE(1Q16_SHIFT)int32_tq16_mul(int32_ta,int32_tb){/* 注意中间结果用 int64_t 防溢出 */return(int32_t)(((int64_t)a*b)Q16_SHIFT);}1.7.3 坑乘法先扩到更宽类型再右移除法先左移再除。饱和int32_t乘积可能溢出int64_t边界前要限制输入范围。1.8 最大公约数 GCD 与最小公倍数 LCM1.8.1 解决什么问题周期对齐两个定时器同时触发、分数约分、部分哈希/桶设计、调度节拍公倍数。1.8.2 欧几里得算法#includestdint.huint64_tgcd_u64(uint64_ta,uint64_tb){while(b){uint64_tta%b;ab;bt;}returna;}uint64_tlcm_u64(uint64_ta,uint64_tb){if(a0||b0)return0;returna/gcd_u64(a,b)*b;/* 先除后乘防溢出 */}1.9 排列组合工程里用得少但关键处很硬1.9.1 解决什么问题枚举子集、密码学/采样规模估算、测试用例数量上界。1.9.2 常用公式实现前用整数类型估上界组合(C(n,k) n! / (k!(n-k)!))n稍大就会溢出uint64_t应边乘边除或提前return overflow。全排列n!用于判断n12左右就不该暴力枚举。/* 仅小 n 适用 */uint64_tcomb_small(unsignedn,unsignedk){if(kn)return0;if(kn-k)kn-k;uint64_tr1;for(unsignedi1;ik;i)rr*(n-ki)/i;returnr;}1.10 概率与采样负载、测试、监控1.10.1 解决什么问题抽样日志、 reservoir 采样、简单负载随机、碰撞概率粗算。1.10.2 核心直觉生日悖论约 ( \sqrt{N} ) 量级样本在 (N) 个桶时碰撞概率显著上升哈希表设计心里有数。伯努利试验以概率p记录日志if (rand() p * RAND_MAX)注意rand()质量与线程安全生产用更好的 RNG。均匀 [0, n) 整数C 推荐#includerandomintuniform_index(intn,std::mt19937gen){std::uniform_int_distributionintdist(0,n-1);returndist(gen);}1.11 基础几何2D 碰撞、UI、游戏、机器人1.11.1 解决什么问题点是否在矩形内、两圆相交、线段距离导航、触控、简单物理。轴对齐矩形包含点intpoint_in_aabb(floatpx,floatpy,floatx0,floaty0,floatx1,floaty1){returnpxx0pxx1pyy0pyy1;}两圆相交圆心距 r1r2#includemath.hintcircles_overlap(floatx1,floaty1,floatr1,floatx2,floaty2,floatr2){floatdxx1-x2,dyy1-y2;floatdist2dx*dxdy*dy;floatrr1r2;returndist2r*r;/* 避免 sqrt */}1.11.2 技巧能比较平方距离就不要sqrt热路径。1.12 数论与编码进制、校验、Base64 长度1.12.1 解决什么问题十六进制 dump、IP/MAC 解析、CRC、容量估算。1.12.2 进制转换心智位 ↔ 十六进制每4 bit一个 hex 位。Base64 编码后长度上界4 * ((n 2) / 3)n为原始字节数。1.12.3 异或校验简单协议uint8_txor_checksum(constuint8_t*buf,size_tlen){uint8_tc0;for(size_ti0;ilen;i)c^buf[i];returnc;}1.13 不等式与 clamp防越界万能胶1.13.1 解决什么问题配置项限幅、PWM 占空比、数组索引、颜色通道 0…255。#includestddef.hintclamp_int(intv,intlo,inthi){if(vlo)returnlo;if(vhi)returnhi;returnv;}/* C17 */#if__cplusplus201703L#includealgorithmtemplateclass TTclamp(T v,T lo,T hi){returnstd::clamp(v,lo,hi);}#endif线性映射把[a,b]映射到[c,d]先 clamp 再算floatlerp(floata,floatb,floatt){returnat*(b-a);/* t 常 clamp 到 [0,1] */}1.14 大 O 与增长选型不是炫技1.14.1 解决什么问题选容器与算法何时哈希O(1)均摊、何时排序O(n log n)、何时暴力O(n^2)不可接受。1.14.2 只记几条工程阈值n ≈ 10^6O(n log n)通常可接受O(n^2)往往不行。n ≈ 10^3O(n^2)有时仍可接受取决于常数与平台。内存O(n)额外数组对n10^8可能直接不可行4*n字节量级估算。1.15 矩阵与向量图形、ML、最小二乘入门1.15.1 解决什么问题3D 变换、姿态、简单最小二乘日常业务代码未必手写但要会读库 API。1.15.2 核心只列程序员必知向量点积|a||b|cosθ叉积3D法向量方向。齐次坐标 4×4 矩阵连乘顺序先应用的变换在乘法右侧约定因库而异以文档为准。手写大矩阵求逆在业务里少见用Eigen、glm等自己写只限小矩阵且注意数值稳定性。1.16 快速参考该用哪条数学场景首选技巧内存/协议对齐2 的幂、align_up/down环形缓冲模运算 / (N-1)有序数据查找二分、lower_bound寄存器/标志位掩码无 FPU 控制Q 格式定点浮点相等判断epsilon 处理 NaN定时器对齐GCD/LCM越界配置clamp碰撞粗测距离平方、AABB1.17 进一步学习按收益《Hacker’s Delight》位技巧经典注意与 C 标准/UB 对照。《What Every Computer Scientist Should Know About Floating-Point Arithmetic》Goldberg浮点必读短文。《Introduction to Algorithms》二分、主定理、摊还分析建立复杂度数学语言。示例为教学用途安全关键与加密场景需使用经过审计的库与类型安全包装勿直接照搬位技巧到未验证边界。
)
