含有負數的取模運算 -开发者知识库

含有負數的取模運算 -开发者知识库,第1张

       前兩天做一套筆試題,碰到了關於負數取模的題目,又出錯了,一直沒弄清,今天去上網查了資料,看了一篇文章總結得不錯,特此轉載記錄下。

 

         System.out.println(7 % -3);      // 1         

         System.out.println(-7 % 3);      //-1

         正整數的取余運算大家都很熟悉,但是對於負數、實數的取余運算,確實給人很新鮮的感覺。於是我對此進行了一些探索。我發現,這里面還是頗有一點可以探索的東西的。

        自然數的取模運算的定義是這樣的(定義1):

如果ad是兩個自然數,d非零,可以證明存在兩個唯一的整數 q和 r,滿足 aqd  r 且0 ≤ rd。其中,q被稱為商,r被稱為余數。

 那么對於負數,是否可以沿用這樣的定義呢?我們發現,假如我們按照正數求余的規則求 (-7) mod 3 的結果,就可以表示 -7 為 (-3)* 3 2。其中,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

有道計算器(-7) mod 3 = -1 可以看到,結果特別有意思。這個問題是百家爭鳴的。看來我們不能直接把正數的法則加在負數上。實際上,在整數范圍內,自然數的求余法則並不被很多人所接受,大家大多認可的是下面的這個定義2

如果ad整數d 非零,那么余數r滿足這樣的關系:

a = qd r , q 為整數,且0 ≤ |r| < |d|。

可以看到,這個定義導致了有負數的求余並不是我們想象的那么簡單,比如,-1 和 2 都是 (-7) mod 3 正確的結果,因為這兩個數都符合定義。這種情況下,對於取模運算,可能有兩個數都可以符合要求。我們把 -1 和 2 分別叫做正余數負余數。通常,當除以d 時,如果正余數為r1,負余數為r2,那么有

r1 = r2 d

對負數余數不明確的定義可能導致嚴重的計算問題,對於處理關鍵任務的系統,錯誤的選擇會導致嚴重的后果。

看完了 (-7) mod 3,下面我們來看一看 7 mod (-3) 的情況(看清楚,前面是 7 帶負號,現在是 3 帶負號)。根據定義2,7 = (-3) * (-2) 1 或7 = (-3) * (-3) -2,所以余數為 1 或 -2。

C (G 編譯): cout << 7 % (-3); // 輸出 1

Java(1.6): System.out.println(7 % (-3)); // 輸出 1

Python 2.6:>>>  輸出 -2

百度計算器7 mod (-3) = -2

Google 計算器7 mod (-3) = -2

有道計算器:不支持
從中我們看到幾個很有意思的現象:
  1. Java 緊隨 C 的步伐,而 Python、Google、百度步調一致。難道真是物以類聚?聯想一下,Google 一直支持 Python,Python 也頗有 Web 特色的感覺,而且 Google Application Engine 也用的 Python,國內的搜索引擎也不約而同地按照 Google 的定義進行運算。
  2. 可以推斷,C 和 Java 通常會盡量讓商更大一些。比如在 (-7) mod 3中,他們以 -2 為商,余數為 -1。在 Python 和 Google 計算器中,盡量讓商更小,所以以 -3 為商。在 7 mod (-3) 中效果相同:C 選擇了 3 作為商,Python 選擇了 2 作為商。但是在正整數運算中,所有語言和計算器都遵循了盡量讓商小的原則,因此 7 mod 3 結果為 1 不存在爭議,不會有人說它的余數是-2。
  3. 如果按照第二點的推斷,我們測試一下 (-7) mod (-3),結果應該是前一組語言(C ,Java)返回 2,后一組返回 -1。(請注意這只是假設)

於是我做了實際測試:

C (G 編譯): cout << (-7) % (-3); // 輸出 -1

Java(1.6): System.out.println((-7) % (-3)); // 輸出 -1

Python 2.6:>>>  輸出 -1

百度計算器:-7 mod (-3) = -1

Google 計算器: -7 mod (-3) = -1

結果讓人大跌眼鏡,所有語言和計算機返回結果完全一致。

總結時間到
我們由此可以總結出下面兩個結論:
  • 對於任何同號的兩個整數,其取余結果沒有爭議,所有語言的運算原則都是使商盡可能小
  • 對於異號的兩個整數,C /Java語言的原則是使商盡可能大,很多新型語言和網頁計算器的原則是使商盡可能小。
最后是拓展時間。對於實數,我們也可以定義取模運算(定義3)。
當a 和 d 是實數,且d 非零, a 除以 d 會得到另一個實數(商),沒有所謂的剩余的數。但如果要求商為一個整數,則余數的概念還是有必要的。可以證明:存在唯一的整數商 q 和唯一的實數 r 使得: a = qd r, 0 ≤ r < |d|.

 

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复