abstract

• 取模运算@求余运算@负数除法和余数及其在不同编程语言程序设计中的区别

负数除以正数求余数

这里的负数,正数主要针对整数,以数论中的风格来讨论

这里基于带余除法来讨论负数除以整数计算余数的方法

计算正数除以负数求余数是我们经常接触的,负数除以正数求余数则相对少见,但是确实会出现在一些地方

带余除法回顾

设 $a,b$ 是两个整数，其中 $b>0$，则[存在]惟一的一对整数 $q$ 及 $r$，使: $a=bq+r$(1),$(0\le r<b)$,$r=a-bq$

从除法算式的角度,可以表示为被除数$÷$除数=$商\cdots 余数$;

• 字母对应过来是$a,b,q,r$,有$a÷b=q\cdots r$
• 商是整数,可能为负数,0,正数,而关键的余数取值范围有严格要求,它是非负的,而且严格小于除数
• 在数论或者计算机某些学科中,我们的取模运算要求操作数为整数,并且第二个操作数是正整数(但在任何地方都不能是0,否则会遇到除法错误,因为求余数涉及到除法,除数(也就是取模运算符的第二个操作数,不能为0))
• (一般总是允许第一个操作数为任意整数),可以知道,第一个操作数为0时,第二个操作数非0时,取模结果为0
• 当$a<0$,$b>0,r⩾0$时,$q=(a-r)b<0$,因此负数除以正数求余数时,一定要把商往负数考虑,同时要控制余数为不超过除数的正数
  • 负数$a$除以正数$b$如果能够整除,那么显然余数为0
  • 关键在于不能整除的情况下,确定商或者余数

在程序设计语言中,取模运算在处理负数时可能有不同的行为,(处理两个正数的行为一般是一样的)参考后面的章节

例

按照上述带余除法的要求,计算以下问题

• $-1\mathrm{mod}5$
  • $-1=(-1)\times 5+4$,所以$-1$除以5的余数为4
• $-6\mathrm{mod}5$
  • $-3=(-2)\times 5+4$,所以$-6\mathrm{mod}5=4$

余数公式

• 事实上,对于上述带余除法的条件下,我们有求正整数余数公式$r=a-b\lfloor \frac{a}{b}\rfloor$,其对于$a\in \mathbb{Z}$都成立
  • 若令$q=\lfloor \frac{a}{b}\rfloor$,则$r=a-bq$;
  • 当$a<0$时,$q⩽-1$,从而$-bq⩾b$,这里有 q ∈ { − 1 , − 2 , ⋯ } q\in\set{-1,-2,\cdots} q∈{−1,−2,⋯}, − b q ∈ { b , 2 b , 3 b , ⋯ } -bq\in\set{b,2b,3b,\cdots} −bq∈{b,2b,3b,⋯}
  • 特别的,若$a<0,|a|<|b|$,则$r=a+b$(1)
  • 结合性质同余性质$km+c\equiv c(\mathrm{mod}m)$,可以让我们更快的口算一些求余运算
• 例如$-21\mathrm{mod}5$=$(-4\times 5-1)\mathrm{mod}5$=$-1\mathrm{mod}5$,在利用式(1),可得所求余数为4

推导

从带余除法$0⩽r=a-bq<b$(2)入手;

我们尝试确定$q$:

由式(2)可得$bq⩽a<b+bq$

那么$q⩽\frac{a}{b}<1+q$,可见,$q=\lfloor \frac{a}{b}\rfloor$

由此观之$r=a-bq=a-b\lfloor \frac{a}{b}\rfloor$

公式$r=a-b\lfloor \frac{a}{b}\rfloor$对于$a\in \mathbb{Z}$都成立

例如:$-6\mathrm{mod}5$=$-6-5\cdot (-2)$=$-6+10$=4

$-21\mathrm{mod}5$=$-21-5\cdot (-5)$=$4$

其他方案(负数除以正数求余)

设$m,t$为正整数,那么$(-m)\mathrm{mod}t$

$-m=-\lceil m/t\rceil \cdot t+r$,则$r=(-m)\mathrm{mod}t$=$\lceil m/t\rceil t-m$

如果令$q=\lceil m/t\rceil$,则$r=qt-m$

例如:$-6\mathrm{mod}5=2\cdot 5-6=4$

验算和检查

要知道计算余数(取模)计算结果$r=a-b\lfloor a/b\rfloor$是否错误(或者说是否有明显错误),可以检查$r$的取值范围是否满足$0⩽r<b$,如果不满足,那一定算错了

程序设计中的取整

一般在程序设计语言中,将一个浮点数类型转换为int时,会丢弃小数部分,直接保留整数部分,

这种情况下,若$a$是一个小数,当$a>0$时,int(a)相当于向下取整;当$a<0$时,相当于向上取整,可以用一个数轴清晰的表示这个结论

在python等语言中,提供了//,可以用来做向下取整运算,例如-3//5=-1,而不是0

取模运算和补数👺

在学习补码时,我们会接触到模这个概念,以时钟上有12的12个点为例

补数的概念

在日常生活中，常会遇到“补数”的概念。例如，时钟指示6点，欲使它指示3点，既可按顺时针方向将分针转9圈，又可按逆时针方向将分针转3圈，结果是一致的。

假设顺时针方向转为正，逆时针方向转为负，则有：

6 - 3 = 3
6 + 9 = 15

由于时钟的时针转一圈能指示12个小时，这“12”在时钟里是不被显示而自动丢失的，即15-12=3，故15点和3点均显示3点。

这样-3和+9对时钟而言其作用是一致的。在数学上称12为模，写作mod 12，而称+9是-3以12为模的补数，记作：-3 ≡ +9 (mod 12),可以读作**-3和+9对模12同余**

mod k这个记号在数论中称为模k同余

或者说，对模12而言，-3和+9是互为补数的。

注意:从带余除法的角度,$-3\mathrm{mod}12=9$,那么有同余的性质可知$-3,9$对模$12$同余,这个例子中余数为9,记为$-3\equiv 9(\mathrm{mod}12)$

同理有：

-4 ≡ +8 (mod 12)
-5 ≡ +7 (mod 12)

即对模12而言，+8和+7分别是-4和-5的补数。

我们可以用$km+c\equiv c(\mathrm{mod}m)$来生成类似的同余关系式;例如,取$k=-1,m=12$,$c\in 0,1,2,\cdots ,12$,比如$c=1$那么$-11\equiv 1(\mathrm{mod}12)$

可见，只要确定了“模”，就可找到一个与负数等价的正数来代替此负数，这样就可以把减法运算用加法实现。

常见程序设计语言中对取模运算的定义

不同语言的取模运算对于两个正整数的定义或运算结果一般是相同的,但是其他情况结果不一定相同,可以通过查阅语言参考或者做实验来判断取模运算对于负数,小数的处理

python

• Expressions — Python documentation这是python3对于二元运算的参考文档,其中包含了取模运算的定义
  • The % (modulo) operator yields the remainder from the division of the first argument by the second. The numeric arguments are first converted to a common type. A zero right argument raises the ZeroDivisionError exception. The arguments may be floating point numbers, e.g., 3.14%0.7 equals 0.34 (since 3.14 equals 4*0.7 + 0.34.) The modulo operator always yields a result with the same sign as its second operand (or zero); the absolute value of the result is strictly smaller than the absolute value of the second operand
• 表达式 — Python 3文档 - Python 中文
  • 取模运算符 % 返回第一个参数除以第二个参数的余数。
  • 数值参数首先被转换为相同类型。右操作数为零会引发 ZeroDivisionError 异常。
  • 参数可以是浮点数，例如 3.14%0.7 等于 0.34（因为 3.14 等于 4*0.7 + 0.34）。
  • 取模运算符始终返回一个与第二个操作数符号相同的（或零）结果；
  • 结果的绝对值严格小于第二个操作数的绝对值 [1]。
  • 基于这两点事实,我们可以用python的取模运算来计算数论中带余除法的余数,例如计算$-3\mathrm{mod}5=2$,其中2的绝对值小于第二个操作数5,并且符号和5相同
• operator — 标准运算符对应函数 — Python 3 文档

c++

%操作符计算两个数相除的余数，第一个数被第二个数除。在C/C++中该操作符只能被应用在整值类型（char、short、int 和 long）的操作数上。

• 当两个操作数都是正数时，结果为正。
• 但是，如果有一个（或两个）操作数为负，余数的符号则取决于机器(或编译器实现)。因此，移植性无法保证。
• %操作符被称作取模（modulus）或求余（remainder）操作符：

3.14 % 3; // 编译时刻错误：浮点操作数
21 % 6;   // ok: 结果是 3
21 % 7;   // ok: 结果是 0
21 % -5;  // 机器相关：结果为 -1 或 1int ival = 1024;
double dval = 3.14159;ival % 12;     // ok: 返回值在 0 和 11 之间
ival % dval;   // 编译时刻错误：浮点操作数