文章目錄
- 背景
- 探究
- 總結
被除數 dividend 用 a 表示；
除數 divisor 用 b 表示；
商 quotient 用 q 表示；
餘 remainder 用 rem 表示；
模 modulo 用 mod 表示。
背景
最近在一道 Java 習題中，看到這樣的一道題：
What is the output when this statement executed:
System.out.printf(-7 % 3);
正整數的取餘運算大家都很熟悉，但是對于負數、實數的取餘運算，确實給人很新鮮的感覺。于是我對此進行了一些探索。我發現，這裡面還是頗有一點可以探索的東西的。
探究
首先，看看自然數的取模運算（定義1）:
如果 a 和 b 是兩個自然數，b 非零，可以證明存在兩個整數 q 和 r，滿足且a = q*b + r
。其中，q 被稱為商，r 被稱為餘數。0 ≤ r < b
我們計算下
(-7) % 3
，這個表達式正常情況下是求餘數，計算過程如下圖所示：
按自然數的除法運算規則，得到商值：
-3
，餘數：
2
，且完全滿足上述兩個關系表達式：
-7 = (-3)*3 + 2
且
0 ≤ 2 ＜ 3
。
那麼，各種程式設計語言和電腦是否是按照這樣的規則計算呢？下面列舉了幾個程式運算的結果：
| 程式 | 語句 | 輸出 |
|---|---|---|
| C++（G++ 編譯） | cout << (-7) % 3; | -1 |
| Java（1.6） | System.out.println((-7) % 3); | -1 |
| Python 2.6 | (-7) % 3 | 2 |
| 百度電腦 | (-7) mod 3 | 2 |
| Google 電腦 | (-7) mod 3 | 2 |
可以看到，結果特别有意思。這個問題是百家争鳴的。看來我們不能直接把自然數的法則用在負數上。實際上，在整數範圍内，自然數的求餘法則并不被很多人所接受，大家大多認可的是下面的這個（定義 2）：
如果 a 和 b 是兩個自然數，b 非零，可以證明存在兩個整數 q 和 r，滿足且a = q*b + r
。其中，q 被稱為商，r 被稱為餘數。0 ≤ |r| < |b|
可以看到，上述定義導緻了有負數的求餘并不是我們想象的那麼簡單，根據上述的定義，我們計算下
(-7) % 3
，計算過程如下圖所示：
按自然數的除法運算規則（
定義 1），商和除數的乘積要小于等于被減數才行，但是很多程式并沒有遵循
定義 1的運算規則，是以依據
定義 2的規則，商和除數的乘積可以大于被減數，使用上圖所示的技巧計算時，商與除數的乘積必須接近被減數，然後計算得到結果，再驗證
定義 2的兩個表達式是否成立。當然了如果你直接使用
定義 2的兩個表達式硬套出
p
和
r
的值也可以，不過不推薦。
如上圖所示可以得到兩組結果：
- 商
-3
2
- 商
-2
-1
這兩組結果都滿足“定義 2”的表達式，也就是說 2 和 -1 都是
(-7) % 3
正确的結果， 是以問題來了到底餘數是 2 還是 -1 呢？這個問題最後會給出答案。
我們把 2 和 -1 分别叫做正餘數和負餘數。通常，整數 a 除以整數 b 時，如果得到正餘數為 r1，負餘數為 r2，那麼存在這樣的關系：
r1 = r2 + d
。
看完了
(-7) % 3
，下面我們來看一看
7 % (-3)
的情況。根據定義 2，計算過程如下圖所示：
如上圖所示，可以得到兩組結果：
- 商
-2
1
- 商
-3
-2
| 語言 | 語句 | 輸出 |
|---|---|---|
| C++（G++ 編譯） | cout << 7 % (-3); | 1 |
| Java（1.6） | System.out.println(7 % (-3)); | 1 |
| Python 2.6 | 7 % (-3) | -2 |
| 百度電腦 | 7 mod (-3) | -2 |
| Google 電腦 | 7 mod (-3) | -2 |
從中我們看到幾個很有意思的現象：
- Java 緊随 C++ 的步伐，而 Python、Google、百度步調一緻。難道真是物以類聚？聯想一下，Google 一直支援 Python，Python 也頗有 Web 特色的感覺，而且 Google Application Engine 也用的 Python，國内的搜尋引擎也不約而同地按照 Google 的定義進行運算。
- 可以推斷，C++ 和 Java 通常會盡量讓商更大一些。比如在 (-7) mod 3中，他們以 -2 為商，餘數為 -1。在 Python 和 Google 電腦中，盡量讓商更小，是以以 -3 為商。在 7 mod (-3) 中效果相同：C++ 選擇了 3 作為商，Python 選擇了 2 作為商。但是在正整數運算中，所有語言和電腦都遵循了盡量讓商小的原則，是以 7 mod 3 結果為 1 不存在争議，不會有人說它的餘數是 -2。
上述的認知其實是錯誤的，糾正如下：
Java 和 C++ 的
%
是求餘運算符，求餘遵循讓商向 0 靠近的原則（即商向 0 方向舍入取整），也就是說求餘是取 q 更趨近 0 時的 r，是以 Java 和 C++ 計算
7 % (-3)
的結果是 1，因為商 -2 更靠近 0；而 Python 的
%
是取模運算符，取模遵循讓商向負無窮靠近的原則（商向無窮小方向舍入取整，向負無窮方向舍入取整），也就是說取模是取 q 更趨近無窮小（負無窮）時的 r，是以 Python、百度、谷歌輸出的結果是 -2，因為 -3 更靠近負無窮的方向。
如果按照第二點的推斷，我測試一下
(-7) % (-3)
，結果應該是前一組語言（C++，Java）傳回 2，後一組傳回 -1。（請注意這隻是假設）
于是我做了實際測試：
| 語言 | 語句 | 輸出 |
|---|---|---|
| C++（G++ 編譯） | cout << -7 % (-3); | -1 |
| Java（1.6） | System.out.println(-7 % (-3)); | -1 |
| Python 2.6 | -7 % (-3) | -1 |
| 百度電腦 | -7 mod (-3) | -1 |
| Google 電腦 | -7 mod (-3) | -1 |
結果讓人大跌眼鏡，所有語言和計算機傳回結果完全一緻。
這個眼鏡也白跌了，上述結果完全符合求餘時商向 0 靠近的原則，取模時商向負無窮方向靠近的原則，是以都輸出
-1
根本就在預料之内。
我們看下
(-7) % (-3)
的運算過程，如下圖所示：
是以根據求餘時商向 0 靠近的原則，取模時商向負無窮方向靠近的原則，求餘和取模的商都選擇
2
，是以餘數和模數都是
-1
，結果輸出的都是
-1
。
總結
我們由此可以總結出下面兩個結論：
- 對于任何同号的兩個整數，其取餘結果沒有争議，所有語言的運算原則都是使商盡可能小。
- 對于異号的兩個整數，C++/Java語言的原則是使商盡可能大，很多新型語言和網頁電腦的原則是使商盡可能小。
這個總結也是錯誤的。
最後總結：除法運算遵循定義 2的規則，求餘是取 q 更趨近 0 時的 r，取模是取 q 更趨近負無窮的 r，如果被除數和除數符号相同，因為取相同的商值，是以餘數和模數相同，被除數和除數的符号不同，則餘數和模數會不同。