上一節(jié)程序員的數(shù)學(xué)筆記1–進(jìn)制轉(zhuǎn)換是介紹了進(jìn)制，特別是十進(jìn)制和二進(jìn)制之間的轉(zhuǎn)換，移位操作和邏輯操作。

今天介紹的是余數(shù)，看完本節(jié)筆記，你會(huì)發(fā)現(xiàn)生活中有很多東西都有余數(shù)的影子。

---

余數(shù)

余數(shù)的特性

整數(shù)是沒有邊界的，它可能是正無窮，也可能是負(fù)無窮。

**但余數(shù)卻總是在一個(gè)固定的范圍內(nèi)。**假如除數(shù)是 m，那么余數(shù)的范圍就是 0~(m-1)。

生活中，余數(shù)可以用來算星期，web 編程中可以用于分頁。

同余定理

兩個(gè)整數(shù) a 和 b，如果它們除以正整數(shù) m 得到的余數(shù)相等，我們就可以說 a 和 b 對(duì)于模 m 同余。

同余定理可以用來做分類，或者說是均分操作。因?yàn)榭梢詫?duì)同個(gè)正整數(shù) m 相除得到的余數(shù)相等的分在同一個(gè)類中。

哈希函數(shù)

每個(gè)編程語言都有對(duì)應(yīng)的哈希函數(shù)，哈希有時(shí)候也被翻譯為散列，**它是指將任意長(zhǎng)度的輸入，通過哈希算法壓縮為某一固定長(zhǎng)度的輸出。**這其實(shí)就是一個(gè)求余的過程。

例如，假設(shè)對(duì)于 100 萬條數(shù)據(jù)記錄，要做到高速存取，最理想情況是開辟一個(gè)連續(xù)的空間存放這些數(shù)據(jù)，減少尋址的時(shí)間，但很多時(shí)候條件并不允許。這個(gè)時(shí)候我們可以考察一下，系統(tǒng)是否可以提供若干個(gè)較小的連續(xù)空間，每個(gè)空間可以存放一定數(shù)量的記錄。比如找到100個(gè)較小的連續(xù)空間，每個(gè)空間可以容納 1 萬條數(shù)據(jù)連續(xù)存放。那么我們可以采用余數(shù)和同余定理來設(shè)計(jì)一個(gè)散列函數(shù)，并實(shí)現(xiàn)哈希表的結(jié)構(gòu)。

這個(gè)函數(shù)可以如下所示：

f(x) = x mod size

x表示等待被轉(zhuǎn)換的數(shù)值，size表示有限存儲(chǔ)空間的數(shù)量，mod表示取余操作。通過余數(shù)，你就能將任何數(shù)值，轉(zhuǎn)換為有限范圍內(nèi)的一個(gè)數(shù)值，然后據(jù)這個(gè)新的數(shù)值，來確定將數(shù)據(jù)存放在何處。

而在我們這個(gè)例子中，size=100，那么對(duì)于記錄標(biāo)號(hào)分別是 1 和 101 的兩條數(shù)據(jù)，根據(jù)上述公式進(jìn)行取余操作，得到的余數(shù)都是 1，那么它們就會(huì)分到同一個(gè)存儲(chǔ)的空間中。

這種的做法好處不僅是設(shè)定一個(gè)存放分類的規(guī)則，而且取余操作簡(jiǎn)單快速，不會(huì)增加尋址時(shí)間。

更進(jìn)一步，如果想增加數(shù)據(jù)散列的隨機(jī)程度，可以加入一個(gè)較大的隨機(jī)數(shù) MAX，如下所示：

f(x) = (x + MAX) mod size

比如對(duì)標(biāo)號(hào)為 1 的記錄，隨機(jī)數(shù)是590199，那么計(jì)算結(jié)果是得到余數(shù)為 0，而標(biāo)號(hào)為 101，隨機(jī)數(shù)變成 627901，對(duì)應(yīng)余數(shù)是 2。這樣在新的計(jì)算公式下，這兩個(gè)記錄就分配到不同的存儲(chǔ)空間了。

這種做法更適合需要將數(shù)據(jù)重新洗牌的應(yīng)用場(chǎng)景，比如加密算法、MapReduce 中的數(shù)據(jù)分發(fā)、記錄的高速查詢和定位等。

舉個(gè)例子，對(duì)于一個(gè)加密算法，如果我們要加密一組三位數(shù)，那我們?cè)O(shè)定一個(gè)這樣的加密規(guī)則：

先對(duì)每個(gè)三位數(shù)的個(gè)、十和百位數(shù)，都加上一個(gè)較大的隨機(jī)數(shù)。

然后將每位上的數(shù)字都除以 7，用所得到的余數(shù)代替原來的三位數(shù)；

最后將第一位和第三位交換。

這就是一個(gè)基本的加密變換過程。

例如對(duì)數(shù)字 625 加密，根據(jù)剛剛的規(guī)則，隨機(jī)數(shù)采用 590127，百、十和個(gè)位數(shù)都分別加上這個(gè)隨機(jī)數(shù)，分別得到的是 590133、590129、590132，接著分別除以 7，得到的余數(shù)分別是 5,1,4，然后交換得到最終的結(jié)果是 415。而如果需要解密，因?yàn)榧用艿娜藭?huì)知道加密規(guī)則、隨機(jī)數(shù)和求余所用的除數(shù) 7 以及求余操作中的商，就可以解密還原回原來的數(shù)字。

更多的采用余數(shù)和求余操作的應(yīng)用例子：

• 尾號(hào)限行
• 最大公約數(shù)、模冪運(yùn)算(DES、AES、RSA)，凱撒密碼，孫子定理
• 進(jìn)制的轉(zhuǎn)換，應(yīng)該說十進(jìn)制轉(zhuǎn)換成其他進(jìn)制都是循環(huán)求余操作

關(guān)于余數(shù)的一些應(yīng)用例子，你是否還想到其他的應(yīng)用呢？

可以留言回復(fù)，和我進(jìn)行交流！

---

歡迎關(guān)注我的微信公眾號(hào)–機(jī)器學(xué)習(xí)與計(jì)算機(jī)視覺，或者掃描下方的二維碼，大家一起交流，學(xué)習(xí)和進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的程序员的数学笔记2--余数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。