求模，求余

发表于 更新于 分类于 阅读次数： 本文字数： 575 阅读时长 ≈ 2 分钟

%%%
计算机系统结构的GCD法引发的深思

求模与求余的区别

这是我们小学二年级就会的除法运算。

$
\begin{aligned}
5\div3&=1\cdots2\\
(-5)\div3&=(-1)\cdots(-2)\\
(-5)\div(-3)&=1\cdots(-2)\\
5\div(-3)&=(-1)\cdots2
\end{aligned}
$

数学定义

求模和求余的主要区别在于处理负数的方式。
首先，商的符号永远由被除数和除数一起决定。

  • 求余操作 (a % b)：
    • 余数的符号与被除数相同
    • 商 = abs(a)/abs(b)*sign(a)*sign(b)
    • 余数 = a-b*商 = abs(a)%abs(b)*sign(a)
  • 求模操作 (a mod b)：
    • 模的符号与除数相同
    • 商 = abs(a)/abs(b)-(sign(a)*sign(b)==1?0:abs(b))
    • 模 = a-b*商 = abs(abs(a)%abs(b)-(sign(a)*sign(b)==1?0:abs(b))*sign(b)

其中sign(a)为取a的正负符号,正为1，负为-1，0为0

实际对比

对于正数，两者结果相同：
对于负数，结果可能不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main() {
    //求余
    int a[]={5,-5,-5,5},b[]={3,3,-3,-3};
    for(int i=0;i<4;++i){
        cout<<a[i]<<" div "<<b[i]<<" = "<<a[i]/b[i]<<"···"<<a[i]%b[i]<<endl;
    }
    return 0;
}
//result
5 div 3 = 1···2
-5 div 3 = -1···-2
-5 div -3 = 1···-2
5 div -3 = -1···2
1
2
3
4
5
6
7
8
9
10
11
# 求模
a=[5,-5,-5,5]
b=[3,3,-3,-3]
for i in range(4):
    print(f'{a[i]} div {b[i]} = {a[i]//b[i]}···{a[i]%b[i]}')

# result
5 div 3 = 1···2
-5 div 3 = -2···1
-5 div -3 = 1···-2
5 div -3 = -2···-1

表格对比

表达式 求余 (C/Java) 求模 (Python)
5 % 3 2 2
-5 % 3 -2 1
-5 % -3 -2 -2
5 % -3 2 -1

转换公式

默认求模的程序语言：Python, Ruby
默认求余的程序语言：C, C++, Java, JavaScript

如果想在求余的语言中实现求模：

1
2
3
4
int mod(int a, int b) {
    int r = a % b;
    return r < 0 ? r + abs(b) : r;
}

如果想在求模的语言中实现求余：

1
2
3
4
5
def remainder(a, b):
    r = a % b
    if (a < 0 and b > 0) or (a > 0 and b < 0):
        return r - b
    return r

模意义下的加减乘除

$
(a+b)\bmod c=((a\bmod c)+(b\bmod c))\bmod c\\
(a-b)\bmod c=((a\bmod c)-(b\bmod c))\bmod c\\
(a\times b)\bmod c=((a\bmod c)\times (b\bmod c))\bmod c
$

但是注意，除法就不是这样的了

$
(a\div b)\bmod c=(a\times b^{-1})\bmod c=((a\bmod c)\times (b^{-1}\bmod c))\bmod c
$

$b^{-1}$是逆元