1. 从“MOD 运算”这个标题说起它到底在讲什么第一次看到“MOD 运算”这个标题加上“拷贝简书主要是为了自己个人学习”这句备注我大概能判断出这是一篇偏向基础、偏自学的笔记型内容。它不像是在讲某个游戏模组虽然热搜词里混进了“英灵神殿mod”“饥荒mod编写教程”这类词核心其实落在数学与编程里的取模运算上。取模英文就是 modulo缩写 mod指的是两个数相除后取余数。比如 10 mod 3 1因为 10 除以 3 商 3 余 1。这个运算看起来简单但它在编程、密码学、哈希、算法题、甚至日常做验证码干扰线里都无处不在。我写这篇东西是想把“MOD 运算”这个点彻底讲透。不是只给你一个%符号就完事而是从数学定义、编程实现、常见坑、实际应用几个角度拆开揉碎。适合谁看刚学编程的新手、准备算法面试的人、写业务代码时被负数取模坑过的开发者以及想搞懂“取模”和“取余”到底有没有区别的人。你可以把它当成一份学习笔记也可以当成速查手册。我会尽量用生活化的例子把抽象概念落到地上。热搜词里还出现了 gcd、位运算、浮点数运算、卷积运算、异或运算这些词说明大家搜“MOD”的时候往往是在一个更大的运算体系里遇到它的。所以这篇不会只孤立地讲取模还会把它和 gcd、位运算、哈希、加密这些场景串起来。你如果正在写 Python、Java、C或者只是单纯想弄明白“模 p”是什么意思往下看就对了。2. 取模运算的数学底子为什么余数不是随便定的2.1 从除法算式说起被除数、除数、商、余数小学数学里我们学过带余除法对于整数 a 和正整数 n一定存在唯一的整数 q 和 r使得 a q × n r其中 0 ≤ r n。这里的 r 就是 a 除以 n 的余数记作 a mod n。这个定义里有两个关键点一是 r 必须非负二是 r 必须小于 n。很多人觉得“余数”就是除不尽剩下的那部分但真正严谨的地方在于余数的范围是被限定死的。举个例子17 ÷ 5 3 余 2因为 17 3×5 2且 2 在 [0,5) 区间内。那如果是 -17 ÷ 5 呢按照上面的定义我们要找一个 q 和 r使得 -17 q×5 r且 0 ≤ r 5。试一下 q -4则 -4×5 -20-17 - (-20) 3所以 r 3。也就是说在数学定义下-17 mod 5 3而不是 -2。这一点非常关键因为很多编程语言里的%运算符给出的结果和数学定义不一致。注意数学上的取模结果永远是非负的除数正数时但编程语言里的取余可能带负号。这是后面所有坑的根源。2.2 取模与取余一字之差结果可能相反中文里“取模”和“取余”经常混着用但在计算机领域它们其实有细微差别。取余remainder通常采用截断除法商向零取整余数符号和被除数一致取模modulo采用地板除法商向下取整余数符号和除数一致。用公式表达取余a rem n a - trunc(a/n) × n取模a mod n a - floor(a/n) × n拿 -17 和 5 来试。trunc(-17/5) trunc(-3.4) -3所以 -17 rem 5 -17 - (-3)×5 -2。而 floor(-17/5) floor(-3.4) -4所以 -17 mod 5 -17 - (-4)×5 3。你看同样两个数取余得 -2取模得 3。在 Python 里%实现的是取模所以-17 % 5结果是 3在 C、Java、JavaScript 里%实现的是取余所以-17 % 5结果是 -2。这个差异在实际开发中经常导致 bug尤其是做数组下标循环、哈希分桶、时间计算的时候。2.3 模运算的封闭性与同余关系模运算真正强大的地方是它把整数集划分成了 n 个等价类。所有除以 n 余数相同的整数被认为在“模 n 意义下同余”记作 a ≡ b (mod n)。比如 3 ≡ 8 ≡ 13 ≡ -2 (mod 5)因为它们除以 5 都余 3。同余关系有一个非常好的性质它和加减乘运算兼容。也就是说如果 a ≡ b (mod n) 且 c ≡ d (mod n)那么 ac ≡ bd (mod n)a×c ≡ b×d (mod n)。这意味着我们可以在计算过程中随时取模而不会改变最终结果。这个性质在算法里太有用了。比如计算 2 的 100 次方对 1000000007 取模你不需要先算出那个天文数字而是可以在每一步乘法后都取模把中间结果控制在一个很小的范围内。快速幂算法就是基于这个原理。再比如哈希函数把任意长度的输入映射到固定范围的桶里靠的也是取模。没有同余的兼容性这些技巧都不成立。3. 编程语言里的 MOD语法、差异与底层实现3.1 各语言取模运算符行为对比不同编程语言对%的处理方式不一样我整理了一张表方便你快速对照。假设被除数 a -17除数 n 5语言运算符表达式结果规则Python%-17 % 53向下取整结果符号随除数Java%-17 % 5-2向零取整结果符号随被除数C / C%-17 % 5-2向零取整结果符号随被除数JavaScript%-17 % 5-2向零取整结果符号随被除数Go%-17 % 5-2向零取整结果符号随被除数Ruby%-17 % 53向下取整结果符号随除数Rust%-17 % 5-2向零取整结果符号随被除数从表里能看出Python 和 Ruby 是“取模派”其他多数语言是“取余派”。如果你写的是跨语言代码或者从 Python 转到 Java这里一定要小心。我见过一个真实案例某同学用 Python 写了一个环形缓冲区下标计算用(index - step) % size跑得好好的后来项目迁移到 Java同样的逻辑直接数组越界因为负数取余得到负下标。排查了半天才发现是语言差异。3.2 负数取模的修正方法如果你在 Java、C 这类语言里想要得到数学意义上的非负余数可以手动修正。通用公式是int mod(int a, int n) { int r a % n; if (r 0) { r n; } return r; }这个写法适用于 n 0 的情况。如果 n 可能为负还需要再调整。更稳妥的写法是int mod(int a, int n) { return ((a % n) n) % n; }先取余加上 n 保证非负再取一次余把范围压回 [0, n)。这个技巧在算法题里非常常用比如处理循环数组、计算日期偏移、做哈希时都离不开它。Python 里虽然%已经帮你处理好了但如果你用math.fmod()它又是向零取整的结果和%不一样。所以别以为换了函数就万事大吉关键还是搞清楚每个函数的行为。3.3 浮点数取模不常用但容易踩雷整数取模很常见浮点数取模也有比如 Python 的math.fmod()和%都支持浮点数。但浮点数本身有精度问题取模结果可能和你手算的不一样。比如5.3 % 2在 Python 里是 1.3但如果你用math.fmod(5.3, 2)也是 1.3看起来一样。可一旦涉及负数-5.3 % 2在 Python 里是 0.7而math.fmod(-5.3, 2)是 -1.3。原因还是取模和取余的区别。浮点数取模在实际业务里用得少但在图形学、游戏开发、信号处理里偶尔会遇到。比如计算角度归一化到 [0, 2π)或者纹理坐标循环。这时候建议统一用((x % n) n) % n的模式并且注意浮点误差。如果对精度要求高最好先把浮点数转成整数乘以一个足够大的倍数做完取模再转回去。不过这样又可能引入新的误差所以能避开就避开。4. MOD 在算法与工程中的典型应用场景4.1 哈希与散列把无限映射到有限哈希表的核心思想是把任意 key 映射到一个固定范围的桶下标。最简单的哈希函数就是hash(key) % bucket_count。这里取模的作用是把哈希值压缩到桶的数量范围内。比如你有 1000 个桶哈希值算出来是 123456789那么123456789 % 1000 789就放到第 789 号桶。取模保证了结果一定在 [0, 999] 之间不会越界。但这里有个讲究桶的数量最好选质数尤其是当哈希函数不够均匀的时候。为什么假设桶数是 10哈希值又恰好都是偶数那么所有 key 都会落到偶数下标桶里奇数桶全空冲突率飙升。如果桶数是质数比如 13那么即使哈希值有某种周期性取模后的分布也会更均匀。这就是为什么很多哈希表实现里初始容量和扩容后的容量都选质数。Java 的 HashMap 用的是 2 的幂次但它通过扰动函数把高位异或到低位再配合(n-1) hash代替取模本质上是等价的但要求 n 是 2 的幂。两种思路各有取舍。4.2 快速幂与模运算密码学的基石计算 a^b mod m 是 RSA 加密、Diffie-Hellman 密钥交换等算法的核心操作。直接算 a^b 再取模当 b 很大时比如 2048 位中间结果会大到无法存储。快速幂利用二进制拆分和同余性质把时间复杂度从 O(b) 降到 O(log b)。核心代码长这样def fast_pow(base, exp, mod): result 1 base base % mod while exp 0: if exp 1: result (result * base) % mod base (base * base) % mod exp 1 return result每一步乘法后都取模保证中间结果始终小于 mod。这里的exp 1和exp 1就是位运算用来逐位检查指数。位运算和取模经常搭档出现因为二进制拆分天然适合用位操作。热搜词里出现“位运算”和“基于miracl大数运算库实现sm2算法”说明很多人是在密码学场景下接触这些的。SM2 是中国商用密码算法底层同样依赖大数模运算。如果你要自己实现除了快速幂还需要模逆、模加、模乘等一套运算通常会用专门的大数库来处理。4.3 循环队列与环形缓冲下标回绕循环队列是取模运算最直观的应用之一。队列有固定容量 capacity入队时tail (tail 1) % capacity出队时head (head 1) % capacity。这样当指针走到末尾时自动回到 0形成一个环。如果没有取模你就得写if (tail capacity) tail 0;代码更啰嗦而且容易漏掉边界情况。环形缓冲在音视频处理、网络收发、日志系统里都很常见。我做过一个音频采集项目缓冲区大小是 4096 个采样点读写指针都用取模回绕。当时用的是 C 语言指针是int类型因为缓冲区大小是正数且指针始终非负所以%的结果也是非负的没遇到负数问题。但如果你的指针可能变成负数比如支持反向查找那就必须用前面说的修正公式。另外如果 capacity 是 2 的幂可以用 (capacity - 1)代替%因为位运算更快。这也是为什么很多底层库要求缓冲区大小必须是 2 的幂。4.4 时间与日期计算模 60、模 24、模 7时间计算里到处都是取模。秒数对 60 取模得到分钟内的秒数分钟数对 60 取模得到小时内的分钟数小时数对 24 取模得到一天内的小时数天数对 7 取模得到星期几。这些场景里被除数通常是非负的所以直接用%没问题。但如果你要计算“往前推 N 天是星期几”就可能出现负数。比如今天是星期三用 3 表示往前推 10 天(3 - 10) % 7在 Java 里是 -7 % 7 0对应星期日但实际应该是星期日吗3 - 10 -7-7 天前相当于 7 天前星期三往前 7 天还是星期三。所以正确答案是 3不是 0。这里就必须用((3 - 10) % 7 7) % 7 3。这种坑在日历类应用里非常常见写的时候一定要测试负数情况。5. 常见问题与排查技巧实录5.1 负数取模导致数组越界这是最经典的坑。场景你有一个长度为 n 的数组想访问arr[(i - k) % n]其中 i 和 k 都是非负整数但 i - k 可能为负。在 Python 里没问题因为%返回非负在 Java、C 里就会得到负下标直接抛异常或访问非法内存。排查方法在取模后打印结果看是否有负数。解决方法统一用((i - k) % n n) % n或者封装一个mod函数。我个人的习惯是只要涉及可能为负的取模一律走封装函数不直接写%。5.2 取模结果与预期不符先查语言规则如果你发现a % b的结果和手算不一样第一步就是查这个语言的%是取模还是取余。Python、Ruby 是取模Java、C、C、JavaScript、Go、Rust 是取余。第二步检查 a 和 b 的符号。如果 a 是负数取余结果就是负数或零如果 b 是负数情况更复杂。第三步如果涉及浮点数检查是否用了math.fmod之类的函数它们的行为可能又不一样。我一般会在代码里写单元测试专门覆盖正数、负数、零、边界值这几种情况跑一遍就清楚了。5.3 大数取模的性能问题在密码学或大数据场景下模数可能非常大几百甚至几千位取模运算本身就很耗时。这时候不能直接用语言内置的%因为内置类型可能溢出或者性能不够。通常会用大数库比如 Python 的int天生支持大数但%的实现是通用的未必最优。C/C 里可以用 GMP、MIRACL 这类库它们针对大数模运算做了优化比如蒙哥马利乘法、Barrett 约减。如果你只是做算法题模数通常是 10^97 这种级别用 64 位整数就够了不需要上大数库。但如果你在实现 SM2、RSA那就必须用专业库自己手写很容易出安全漏洞。5.4 取模与哈希冲突的排查哈希表性能下降时除了看负载因子还要看哈希函数和取模是否配合得当。如果桶数是 2 的幂而哈希函数低位分布不均匀就会导致大量冲突。排查方法统计每个桶的元素数量画个直方图看是否严重倾斜。如果倾斜可以尝试把桶数改成质数或者给哈希函数加扰动。Java 的 HashMap 用(n-1) hash代替%前提是 n 是 2 的幂并且 hash 的高位参与了运算。如果你自己实现哈希表建议先用质数桶数 %简单可靠等性能真的成为瓶颈再考虑优化。5.5 常见问题速查表问题现象可能原因排查方法解决方案数组下标为负语言%返回负数打印取模结果用((a % n) n) % n哈希冲突严重桶数选择不当统计桶分布改用质数桶数或加扰动快速幂结果错误中间结果溢出检查每步是否取模每步乘法后立即取模浮点取模结果异常精度误差或函数差异对比%和fmod转整数运算或统一函数时间计算偏差一天负数取模未修正测试跨天场景封装非负取模函数6. 从 MOD 延伸到 GCD 与位运算几个相关概念6.1 GCD 与模运算的天然联系GCD最大公约数和取模关系密切因为欧几里得算法就是基于gcd(a, b) gcd(b, a % b)反复迭代。比如求 gcd(48, 18)48 % 18 1218 % 12 612 % 6 0所以 gcd 是 6。这个算法简单高效是数论里最基础的算法之一。扩展欧几里得算法还能求模逆元即找到 x 使得 a×x ≡ 1 (mod m)这在 RSA 加密里用来求私钥。如果你搜“gcd”和“mod”一起出现多半是在做数论题或者密码学实现。6.2 位运算替代取模的条件当模数是 2 的幂时a % n等价于a (n - 1)前提是 a 非负。比如a % 8等价于a 7。这是因为 8 的二进制是 1000减一得 0111按位与就保留了低三位正好是除以 8 的余数。这个技巧在性能敏感的代码里很常用比如哈希表、内存对齐、环形缓冲。但要注意如果 a 是负数按位与的结果可能不符合数学取模。比如 -17 7 在补码表示下是 7而 -17 mod 8 数学上也是 7看起来一致但这是因为补码的特性。不同语言对负数的位运算处理可能不同所以最好还是确保操作数为非负。6.3 异或运算与模运算的对比异或XOR和取模都是常见的运算但用途不同。异或常用于加密、校验、交换变量取模常用于哈希、循环、数论。热搜词里同时出现“异或运算”和“MOD”可能是因为在学算法时一起遇到了。异或有一个性质a XOR a 0a XOR 0 a所以可以用来找唯一出现一次的数字。取模没有这种自反性但它在同余类上的封闭性更强。两者结合的场景也有比如某些哈希函数会先异或再取模以增加随机性。7. 我个人的实操心得与避坑建议写了这么多最后分享几点我在实际编码中总结的经验。第一永远不要假设%的行为在所有语言里都一样。我现在的习惯是只要涉及负数取模一律封装成函数函数名就叫mod内部实现用((a % n) n) % n这样不管换什么语言行为都一致。第二哈希表的桶数优先选质数除非你有明确的性能测试证明 2 的幂更好。质数桶数配合一个像样的哈希函数冲突率通常足够低而且实现简单不容易出错。第三快速幂里的每一步取模不能省哪怕你觉得中间结果不会溢出。我见过有人用 Python 写快速幂觉得 Python 整数不会溢出就不取模结果算 2 的 1000000 次方内存直接爆掉。取模不仅防溢出还能把数字控制在固定范围对性能也有好处。第四浮点数取模能不用就不用。如果业务逻辑里出现了浮点数取模先想想能不能转成整数。比如角度归一化可以先把角度转成毫弧度或者整数度做完取模再转回去。第五测试用例一定要覆盖负数、零、边界值。我写过一个取模函数正数测试全过上线后遇到负数直接崩了。后来补了单元测试覆盖a为负、n为负、a为零、n为 1 等情况才彻底放心。这些经验看起来琐碎但每一条都是踩过坑之后才记住的。你如果刚开始学 MOD 运算不妨把这些坑先记下来以后写代码时能省不少调试时间。