Adrian's Space

编程中非常关键、非常常用的数学技巧

14分钟阅读

1 编程中非常关键、非常常用的数学技巧

面向日常写代码（含系统/嵌入式）时反复出现的数学工具：偏可落地与正确性，不追求定理证明。需要示例处用 C/C++；涉及未定义行为（UB）与溢出时会标明。

1.1 如何使用本文

  • 原理一句话：解决什么问题。
  • 公式/不变量：写对代码前先在纸上写清楚。
  • 坑：溢出、浮点、有符号/无符号混用。

1.2 位运算与 2 的幂（最高频）

1.2.1 解决什么问题

  • 标志位、权限掩码、寄存器、协议字段、内存对齐、环形缓冲区索引、快速乘除 2 的幂。

1.2.2 核心技巧

判断 2 的幂（正整数 n）

/* n > 0 时成立 */
int is_pow2(unsigned n) { return n && !(n & (n - 1)); }

向上/向下对齐到 2^k（align 为 2 的幂）

#include <stdint.h>
 
uintptr_t align_up(uintptr_t x, uintptr_t align) {
	return (x + align - 1) & ~(align - 1);
}
 
uintptr_t align_down(uintptr_t x, uintptr_t align) {
	return x & ~(align - 1);
}

用移位代替乘除 2 的幂（仅当语义等价且类型宽度明确）

unsigned mul_pow2(unsigned x, unsigned k) { return x << k; }
unsigned div_pow2(unsigned x, unsigned k) { return x >> k; } /* 无符号右移 */

设置/清除/翻转/测试某位

#define BIT(n)        (1u << (n))
#define SET_BIT(v, n)   ((v) |= BIT(n))
#define CLR_BIT(v, n)   ((v) &= ~BIT(n))
#define FLIP_BIT(v, n)  ((v) ^= BIT(n))
#define TEST_BIT(v, n)  (((v) & BIT(n)) != 0)

1.2.3 实现要点

  • align 必须是 2 的幂；否则 & ~(align-1) 无意义。
  • 左移 1u << n 时若 n >= 类型位宽，是 UB；协议里位域宽度要限制 n。
  • 有符号右移 >> 在 C 中对负数实现定义（算术右移常见，但 portable 代码慎用符号位技巧）。

1.2.4 常用库

  • C++20：std::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_MAX；INT32_MIN 的绝对值不能用同类型 abs() 安全表示。
  • 无符号减法 a - b 当 a < b 时按模 (2^{32}) 回绕，比较要用同类型或显式转换。
#include <limits.h>
#include <stdint.h>
 
/* 安全判断 a + b 是否溢出 int32（a,b 为 int32_t） */
int add_overflow_i32(int32_t a, int32_t b, int32_t *out) {
	if (b > 0 && a > INT32_MAX - b) return 1;
	if (b < 0 && a < INT32_MIN - b) return 1;
	*out = a + b;
	return 0;
}

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 为无符号且范围合理时）。
#define RING_MASK(N) ((N) - 1) /* N 必须是 2 的幂 */
 
unsigned ring_next(unsigned i, unsigned N) {
	return (i + 1) & 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_t lower_bound_size_t(size_t lo, size_t hi,
			  int (*pred)(size_t mid, void *ctx), void *ctx) {
	while (lo < hi) {
		size_t mid = lo + (hi - lo) / 2; /* 防 (lo+hi) 溢出 */
		if (pred(mid, ctx))
			hi = mid;
		else
			lo = mid + 1;
	}
	return lo;
}

1.5.3 实现要点

  • 用 mid = lo + (hi - lo) / 2 而不是 (lo + hi) / 2，避免大整数相加溢出。
  • log2 估内存：n 个元素、每元素 s 字节 → 至少 n*s；树/索引额外因子另算。

1.6 浮点数：比较、误差、特殊值

1.6.1 解决什么问题

  • 传感器数据、图形、物理仿真；避免 == 直接比较浮点。

1.6.2 核心技巧

相对/绝对误差比较（常见实用写法）

#include <math.h>
 
int float_near_equal(float a, float b, float abs_eps, float rel_eps) {
	float diff = fabsf(a - b);
	if (diff <= abs_eps)
		return 1;
	float scale = fmaxf(fabsf(a), fabsf(b));
	return diff <= rel_eps * scale;
}

注意 NaN / Inf

#include <math.h>
 
int is_finite_float(float x) { return isfinite(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 表示，缩放因子 1<<16。
#include <stdint.h>
 
#define Q16_SHIFT 16
#define Q16_ONE   (1 << Q16_SHIFT)
 
int32_t q16_mul(int32_t a, int32_t b) {
	/* 注意中间结果用 int64_t 防溢出 */
	return (int32_t)(((int64_t)a * b) >> Q16_SHIFT);
}

1.7.3 坑

  • 乘法先扩到更宽类型再右移；除法先左移再除。
  • 饱和：int32_t 乘积可能溢出 int64_t 边界前要限制输入范围。

1.8 最大公约数 GCD 与最小公倍数 LCM

1.8.1 解决什么问题

  • 周期对齐（两个定时器同时触发）、分数约分、部分哈希/桶设计、调度节拍公倍数。

1.8.2 欧几里得算法

#include <stdint.h>
 
uint64_t gcd_u64(uint64_t a, uint64_t b) {
	while (b) {
		uint64_t t = a % b;
		a = b;
		b = t;
	}
	return a;
}
 
uint64_t lcm_u64(uint64_t a, uint64_t b) {
	if (a == 0 || b == 0) return 0;
	return a / 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!：用于判断 n>12 左右就不该暴力枚举。
/* 仅小 n 适用 */
uint64_t comb_small(unsigned n, unsigned k) {
	if (k > n) return 0;
	if (k > n - k) k = n - k;
	uint64_t r = 1;
	for (unsigned i = 1; i <= k; i++)
		r = r * (n - k + i) / i;
	return r;
}

1.10 概率与采样（负载、测试、监控）

1.10.1 解决什么问题

  • 抽样日志、 reservoir 采样、简单负载随机、碰撞概率粗算。

1.10.2 核心直觉

  • 生日悖论：约 ( \sqrt{N} ) 量级样本在 (N) 个桶时碰撞概率显著上升（哈希表设计心里有数）。
  • 伯努利试验：以概率 p 记录日志：if (rand() < p * RAND_MAX)（注意 rand() 质量与线程安全，生产用更好的 RNG）。

均匀 [0, n) 整数（C++ 推荐）

#include <random>
 
int uniform_index(int n, std::mt19937 &gen) {
	std::uniform_int_distribution<int> dist(0, n - 1);
	return dist(gen);
}

1.11 基础几何（2D 碰撞、UI、游戏、机器人）

1.11.1 解决什么问题

  • 点是否在矩形内、两圆相交、线段距离（导航、触控、简单物理）。

轴对齐矩形包含点

int point_in_aabb(float px, float py,
		  float x0, float y0, float x1, float y1) {
	return px >= x0 && px <= x1 && py >= y0 && py <= y1;
}

两圆相交（圆心距 ⇐ r1+r2）

#include <math.h>
 
int circles_overlap(float x1, float y1, float r1,
		    float x2, float y2, float r2) {
	float dx = x1 - x2, dy = y1 - y2;
	float dist2 = dx * dx + dy * dy;
	float r = r1 + r2;
	return dist2 <= r * 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_t xor_checksum(const uint8_t *buf, size_t len) {
	uint8_t c = 0;
	for (size_t i = 0; i < len; i++)
		c ^= buf[i];
	return c;
}

1.13 不等式与 clamp（防越界万能胶）

1.13.1 解决什么问题

  • 配置项限幅、PWM 占空比、数组索引、颜色通道 0..255。
#include <stddef.h>
 
int clamp_int(int v, int lo, int hi) {
	if (v < lo) return lo;
	if (v > hi) return hi;
	return v;
}
 
/* C++17 */
#if __cplusplus >= 201703L
#include <algorithm>
template <class T>
T clamp(T v, T lo, T hi) { return std::clamp(v, lo, hi); }
#endif

线性映射：把 [a,b] 映射到 [c,d]（先 clamp 再算）

float lerp(float a, float b, float t) {
	return a + t * (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^6：O(n log n) 通常可接受；O(n^2) 往往不行。
  • n ≈ 10^3：O(n^2) 有时仍可接受（取决于常数与平台）。
  • 内存：O(n) 额外数组对 n=10^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
碰撞粗测距离平方、AABB

1.17 进一步学习（按收益）

  • 《Hacker’s Delight》：位技巧经典（注意与 C 标准/UB 对照）。
  • 《What Every Computer Scientist Should Know About Floating-Point Arithmetic》（Goldberg）：浮点必读短文。
  • 《Introduction to Algorithms》：二分、主定理、摊还分析（建立复杂度数学语言）。

示例为教学用途；安全关键与加密场景需使用经过审计的库与类型安全包装，勿直接照搬位技巧到未验证边界。

关系图谱

反向链接