模

模除（又称模数、取模操作、取模运算等，英语：modulo 有时也称作 modulus）得到的是一个数除以另一个数的余数。给定两个正整数：被除数 a 和除数 n，a modulo n (缩写为 a mod n)得到的是使用欧几里德除法时 a/n 的余数。 举个例子：计算表达式 "5 mod 2" 得到 1，因为 5÷2=2...1（5 除以 2 商 2 余1）；而 "9 mod 3" 得到 0，因为 9÷3=3...0；注意：如果使用计算器做除法，不能整除时，你不会得到商，而是会得到一个小数，如：5÷2=2.5。虽然通常情况下 a 和 n 都是整数，但许多计算系统允许其他类型的数字操作，如：对浮点数取模。一个整数对 n 取模的结果范围为： 0 到 n − 1（a mod 1 恒等于 0；a mod 0 则是未定义的，在编程语言里可能会导致除零错误）。 有关概念在数论中的应用请参阅模算数。当 a 和 n 均为负数时，通常的定义就不适用了，不同的编程语言对结果有不同的处理。在数学中，取模运算的结果就是欧几里德除法的余数。当然也有许多其他的定义方式。计算机和计算器有许多种表示和储存数字的方法，因此在不同的硬件环境下、不同的编程语言中，取模运算有着不同的定义。几乎所有的计算系统中，a 除 n 得到商 q 和余数 r 均满足以下式子：q ∈ Z a = n q + r | r | < | n | {displaystyle {begin{aligned}q,&in mathbb {Z} \a,&=nq+r\|r|,&<|n|end{aligned}}}( 1 )然而这样做，当余数非 0 时，余数的符号仍然是有歧义的：余数非 0 时，它的符号有两种选择，一个正、一个负。 通常情况下，在数论中总是使用正余数。但在编程语言中，余数的符号取决于编程语言的类型和被除数 a 或除数 n 的符号。 标准 Pascal 和 ALGOL 68 总是使用 0 或正余数；另一些编程语言，如 C90 ，当除数 a 和除数 n 都是负数时，C90 标准并没有做具体的规定，而是留给编译器去定义并实现。 在大多数系统上 a mod 0 时未定义的，虽然有些系统定义它就等于 a。更多详情参见表格。因此由等式 1 有，余数和除数符号一致。因为使用了取底函数，商总是向下取整，即使商已经是负数。在这种情况下：或者等价的：这里的 sgn 是符号函数，因此当取模的结果与被除数符号相同时，可能会导致意想不到的错误。举个例子：如果需要判断一个整数是否为奇数，有人可能会测试这个数除 2 的余数是否为 1：但在一个取模结果与被除数符号相同的编程语言里，这样做是错的。因为当被除数 n 是奇数且为负数时， n mod 2 得到 −1，此时函数返回“假”。一种正确的实现是测试取模结果是否为 0，因为余数为 0 时没有符号的问题：或者考虑余数的符号，有两种情况：余数可能为 1 或 -1。一些计算器有取模 mod() 按钮，很多编程语言里也有类似的函数，通常像 mod(a, n) 这样。 有些语言也支持在表达式内使用 "%"、"mod" 或 "Mod" 作为取模或取余操作符。或或者在一些没有 mod() 函数的环境中使用等价的： （注意 'int' 事实上等价于截断函数a/n，进行了向 0 取整）一些取模操作，经过分解和展开可以等同于其他数学运算。这在密码学的证明中十分有用，例如：迪菲-赫尔曼密钥交换。可以通过依次计算带余数的除法实现取模操作。特殊情况下，如某些硬件上，存在更快的实现。 例如：2 的 n 次幂的模，可以通过逐位与运算实现：例子，假定 x 为正数：在进行位操作比取模操作效率更高的设备或软件环境中，以上形式的取模运算速度更快。编译器可以自动识别出对 2 的 n 次幂取模的表达式，自动将其优化为 expression & (constant-1)。这样可以在兼顾效率的情况下写出更整洁的代码。这个优化在取模结果与被除数符号一致的语言中（包括 C 语言）不能使用，除非被除数是无符号整数。这是因为如果被除数是负数，则结果也是负数，但 expression & (constant-1) 总是正数，进行这样的优化就会导致错误，无符号整数则没有这个问题。