模运算¶

模运算，又称取模或模除，是数学中一种基础的运算方式。模运算的符号通常为 $\bmod$，在编程语言中常用 % 表示。

给定两个整数 a 和正整数 b，模运算 $a \bmod b$ 的结果是 a 除以 b 所得的最小非负余数，其值满足以下关系：

\[ a \equiv r \pmod{b} \]

其中：

$\equiv$ 是同余符号，表示 $a$ 与 $r$ 在模 $b$ 的意义下相等
存在整数 $k$ 使得 $a = k \cdot b + r$
且 $0 \leq r < b$

例如：

$7 \equiv 1 \pmod{3}$，因为 $7 = 2 \cdot 3 + 1$
$10 \equiv 2 \pmod{4}$，因为 $10 = 2 \cdot 4 + 2$

C++ 中的 `%` 运算符¶

在 C++ 中，模运算使用 % 运算符实现。但需要注意，C++ 的 % 运算符计算的是余数（remainder），而不是数学中严格定义的模（modulus）。这在处理负数时尤为关键。

C++ 中的 `/` 运算符¶

C++ 中，整数除法 / 的行为是向零截断，而非数学中的向下取整。

向零截断：结果靠近 $0$
整数除法示例：
- 5 / 2 = 2 （原为 $2.5$，向 $0$ 截断后为 $2$）
- -5 / 2 = -2（原为 $-2.5$，向 $0$ 截断后为 $-2$）

C++ 与数学的 `%` 运算对比¶

C++ 的 % 运算定义为：a % b = a - (a / b) * b

注意：这里的 / 是向零截断。

而数学上的模定义为：

\[ a \bmod b = a - \left\lfloor \dfrac{a}{b} \right\rfloor \cdot b \]

其中 $\lfloor \cdot \rfloor$ 表示向下取整。

示例：详细过程对比¶

5 % 2
- C++：
  - 整数除法：5 / 2 = 2（向零截断）
  - 所以：5 % 2 = 5 - 2 * 2 = 1
- 数学：
  - 向下取整：$\left\lfloor \dfrac{5}{2} \right\rfloor = 2$
  - 所以：$5 \bmod 2 = 5 - 2 \cdot 2 = 1$
- ✅ 结果相同

5 % -2
- C++：
  - 整数除法：5 / -2 = -2（向零截断）
  - 所以：5 % -2 = 5 - (-2) * (-2) = 5 - 4 = 1
- 数学：
  - 向下取整：$\left\lfloor \dfrac{5}{-2} \right\rfloor = -3$
  - 所以：$5 \bmod (-2) = 5 - (-3) \cdot (-2) = 5 - 6 = -1$
- ❌ 结果不同

-5 % 2
- C++：
  - 整数除法：-5 / 2 = -2（向零截断）
  - 所以：-5 % 2 = -5 - (-2) * 2 = -5 - (-4) = -1
- 数学：
  - 向下取整：$\left\lfloor \dfrac{-5}{2} \right\rfloor = -3$
  - 所以：$-5 \bmod 2 = -5 - (-3) \cdot 2 = -5 + 6 = 1$
- ❌ 结果不同

-5 % -2
- C++：
  - 整数除法：-5 / -2 = 2（向零截断）
  - 所以：-5 % -2 = -5 - 2 * (-2) = -5 + 4 = -1
- 数学：
  - 向下取整：$\left\lfloor \dfrac{-5}{-2} \right\rfloor = 2$
  - 所以：$-5 \bmod (-2) = -5 - 2 \cdot (-2) = -5 + 4 = -1$
- ✅ 结果相同

对照表¶

表达式	`C++` `/`（向零截断）	`C++` `%` 结果	数学 `⌊a/b⌋`（向下取整）	数学 `a - ⌊a/b⌋·b`	是否相同
`5 % 2`	`5 / 2 = 2`	`1`	`⌊5/2⌋ = 2`	`5 - 2·2 = 1`	✅ 相同
`5 % -2`	`5 / -2 = -2`	`1`	`⌊5/(-2)⌋ = -3`	`5 - (-3)·(-2) = -1`	❌ 不同
`-5 % 2`	`-5 / 2 = -2`	`-1`	`⌊-5/2⌋ = -3`	`-5 - (-3)·2 = 1`	❌ 不同
`-5 % -2`	`-5 / -2 = 2`	`-1`	`⌊-5/(-2)⌋ = 2`	`-5 - 2·(-2) = -1`	✅ 相同

C++ 中修正模的写法¶

为了使模运算结果始终为非负数（与数学一致），可使用如下方式修正：

int mod(int a, int b) // 计算 a % b
{
    return (a % b + b) % b; // b 必须为正
}

也可以写作

int mod(int a, int b) // 计算 a % b
{
    int v = a % b;
    if (v < 0) v += b;
    return v;
}

拓展¶

为什么 C++ 要将整数除法定义为向零截断？¶

C++（和 C）中的整数除法使用“向零截断”（truncation toward zero），而不是数学中常见的“向下取整”（floor division）。这是出于多方面的考虑：

1. 历史兼容性（C语言的遗产）¶

C++ 是在 C 语言基础上发展而来的，而 C 最初的设计目标之一是面向底层、高效、可移植。C 最初的除法行为并未完全规定符号处理方式，但许多编译器实现（尤其是基于 x86 架构的）采用了向零截断的方式，后来这就变成了事实标准，C99 明确规定了此行为。

C++ 为了兼容 C 和已有大量代码，继续采用了相同的行为。

2. 向零截断更易于实现（底层硬件友好）¶

大多数现代处理器（例如 x86/x64）的整数除法指令（如 IDIV）返回的结果就是：

商：向零截断的结果
余数：满足 a = (a / b) * b + (a % b)

这意味着编译器不需要额外指令来处理符号、调整商值、重算余数，效率更高。

例如：

int q = a / b;
int r = a % b;
// 始终有：a == b * q + r

3. 余数定义必须和除法保持一致¶

在 C++ 中，a % b 的定义必须和 a / b 配合，满足下列恒等式：

a == (a / b) * b + (a % b)

这是 C/C++ 语言规范中对 % 的根本定义。如果将 / 改为向下取整（floor），就必须同时调整 % 的计算逻辑。

否则上述恒等式将不再成立，可能导致程序逻辑出错。

4. 向零截断具备“对称性”¶

向零截断在正负对称处理上更直观。例如：

5 / 2 = 2 => 5 % 2 = 1
-5 / 2 = -2 => -5 % 2 = -1

这意味着当操作数变号时，结果也会对称变号（除法和取余一起变化），便于处理镜像、坐标反向等场景。

为什么不按数学来设计？¶

数学中的模运算通常要求结果非负（0 <= r < b），这在数论、加法群、同余等场景中更有意义。但在实际编程中，模运算常用于：

数组索引环绕（如 i % n）
判断奇偶性（x % 2 == 1）
环状计数器、位移偏移
分布式哈希（如一致性哈希中的槽位映射）

这些应用更注重效率和一致性，而非符号严格性。

C++ 所采用的向零截断策略与处理器本身指令一致，避免了符号判断和修正计算，从而提升性能，也便于移植和兼容早期代码。

总结对比¶

方面	C++ / C 的设计选择	数学中的定义
除法 `/`	向零截断	向下取整（floor）
余数 `%`	与被除数同号	非负整数（`0 <= r < b`）
实现优先级	硬件一致性、性能、对称性	理论严谨、一致性
修正方式（程序员）	`(a % b + b) % b`	不需要额外处理