CRC数学原理：多项式除法、模2运算与生成多项式
说真的，CRC 看起来挺吓人——一堆多项式、除法、余数。但你把它拆开看，核心就三样东西：一个不走寻常路的“加法”，一个只关心余数的“除法”，还有一个固定的“除数”叫做生成多项式。搞懂这三样，CRC 就不神秘了。
我先从最基础的东西讲起——模2运算。这是整个 CRC 的数学地基。
模2运算：没有进位的算术
平时我们做二进制加法，1+1=10，要进位对吧？但模2加法不一样，它不要进位，1+1=0。说白了，这就是个异或（XOR）操作。
- 0 + 0 = 0（没变化）
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0（没有进位！）
模2减法也一样——因为减法和加法在模2里是同一回事。1 - 1 = 0，0 - 1 = 1。你想想看，它跟异或完全等价。
我记得刚接触时，总是不自觉想“进位”，结果算错好几遍。后来我干脆在脑中把“加法”俩字替换成“异或”，一下就顺了。
多项式除法：比特串怎么当“多项式”用
CRC 里说的“多项式”，不是数学课上那种 x² + 2x + 1，而是系数只有 0 或 1 的多项式。每个比特位对应一个幂次。比如二进制 1101 就对应多项式：
1·x³ + 1·x² + 0·x¹ + 1·x⁰ = x³ + x² + 1为什么这么搞？因为这样就能用多项式的除法来算余数——而余数就是我们要的 CRC 校验码。
多项式除法和普通除法的区别：减法替换成异或。其他步骤照旧：对齐、减、拉下一位、重复。
举个简单的例子。数据是 110101，生成多项式选 1011（对应 x³ + x + 1）。
步骤：
1. 数据后面补3个0（因为多项式最高次是3），得到 110101000
2. 用 1011 去除，每一步用异或代替减法
3. 最后剩下的3位余数就是 CRC
手工推演：
110101000 ÷ 1011
第一步：1011 对齐到 1101，异或得 0110，拉下下一位 0 -> 01100
第二步：1011 不能整除 0110（最高位0），直接拉下一位 0 -> 011000
第三步：1011 对齐 1100，异或得 0111，拉下最后一位 0 -> 01110
第四步：1011 对齐 1110，异或得 0101，无法再除，余数 101
所以 CRC = 101
你看，全程只有异或和移位。没有进位，没有借位。这就是模2除法。
生成多项式的表示方法
生成多项式就是 CRC 里那个固定的“除数”。不同标准用不同多项式，直接影响检错能力。常见的表示方法有三种：
| 表示方式 | 示例 (CRC-8) | 说明 |
|---|---|---|
| 多项式符号 | x⁸ + x² + x + 1 | 最高次8，系数仅0/1 |
| 二进制 | 1 0000 0111 | 9位，对应各幂次系数 |
| 十六进制 | 0x107 | 省去高位的1，常写成0x07 |
0x4D，先补齐最高位隐藏的1，再转二进制，就等于把 x⁸ 那一位补上，共9位。比如 CRC-8 默认最高次8，隐藏的1是 x⁸。
常用生成多项式一览
实际项目中用的多项式都是业界标准。我整理了几个最常见的：
| 标准名称 | 多项式（十六进制，含隐藏1） | 应用场景 |
|---|---|---|
| CRC-8 | 0x107 | 1-Wire、SMBus |
| CRC-16-IBM | 0x18005 | USB、Modbus |
| CRC-16-CCITT | 0x11021 | 蓝牙、PPP |
| CRC-32 | 0x104C11DB7 | 以太网、ZIP、PNG |
核心流程：一张图看懂 CRC 数学
下面这张图把刚才讲的三部分串起来——从数据到多项式除法，再到余数校验码。你看着它就能回忆整个计算链条。
总结一下本章的硬知识点
- 模2运算 = 异或。加、减、乘、除都基于它。
- 多项式除法：把比特串看成多项式，用异或替换减法，反复对齐、异或、拉位，最后余数就是 CRC。
- 生成多项式：一个固定比特模式，常用十六进制表示（注意隐藏的最高位 1）。不同标准多项式不同，选错会导致漏检甚至无法通过一致性测试。
嗯，数学原理就这些。我觉得最难的不是概念，而是手工算的时候总忘了“模2减法 = 异或”这件事。多练两次，脑子里形成条件反射就好了。下次你看到以太网的 CRC-32，就知道那背后是一长串异或和移位操作，不是什么玄学。