程序語言中的取余是如何實現的?

01-05

RT。各種語言用的演算法一樣嗎?
另外，如果除數非常非常大，會不會導致計算的速度也非常慢呢?
目前已知RNG和Hash table 中都會大量用到取余操作。除此，還有哪些地方會用到取余?

並行除法器電路

80x86彙編裡面除法指令div(idiv).

8位運算結果，商放在累加器低位AL，餘數放在累加器高位AH。

16位運算，商存放在累加器AX，餘數放在數據寄存器DX里。and so on。

底層運算里，餘數和商是同時算出來的。

計算餘數不是一個單獨的功能。

這是硬體邏輯的工作。

補：

彙編的除法本質是重複的減法

減到最後被除數不夠除數減了，剩下的自然就是餘數

具體的步驟可以看這篇文章

彙編除法原理

————————————

計算機一次也就只能處理32/64位二進位數運算。

除數大了要將計算拆分，當然會慢。

」如果除數非常非常大，會不會導致計算的速度也非常慢呢?「

我想是的。

————————————

取餘數在密碼學理論上使用極為普遍。

實際這些功能多數直接由硬體電路實現，非常快。

取余操作如果除數是 2 的整數次冪可以優化為移位操作。所以常用的取余（比如 hashtable）都必須令除數為 2 的整數次冪。否則確實會有嚴重影響。

僅回答第一個問題，「取余是如何實現的」

言歸正傳，上面的答案都或多或少有問題。

C是高級語言，a-(a整除b)*b就不用說了，「整除」是怎麼來的？

但相對於二進位運算，彙編也算一種「高級」語言，那麼我問，「div」是怎麼來的？

@馮東說的不太清楚。

來看一個例子，如果除數的數是2的冪次的話（求商部分來源於@鋼盅郭子）：

除數2，二進位為0000 0010，被除數5，二進位為0000 0101。除數-1，即此時除數變為0000 0001，兩者進行與操作，結果為0000 0001，餘數為1。兩者進行或操作，得0000 0111，右移除數的位數，此時為一位，得到商0000 0010，也就是2。
除數4，二進位為0000 0100，被除數13，二進位為0000 1101。除數-1，即此時除數變為0000 0011，兩者進行與操作，結果為0000 0001，餘數為1。兩者進行或操作，得0000 1111，右移除數的位數，此時為兩位，得到商0000 0011，也就是3。
除數8，二進位為0000 1000，被除數47，二進位為0010 1111。除數-1，即此時除數變為0000 0111，兩者進行與操作，結果為0000 0111，餘數為7。兩者進行或操作，得0010 1111，右移除數的位數，此時為三位，得到商0000 0101，也就是5。

原理明白了吧，但這種方法僅僅適用於除數為2的冪次數的時候。

另，這種方法會出現在點陣圖法的位向量操作中，看著是與操作，實際上就是取余。

#define MAX 1000000 #define SHIFT 5 #define MASK 0x1F #define DIGITS 32

int a[1+MAX/DIGITS]; //置指定位為1 void setbit(int n) { a[n&>&>SHIFT] |= (1&<&<(nMASK)); } //清空指定位 void clearbit(int n) { a[n&>&>SHIFT] = ~(1&<&<(nMASK)); } //檢測指定位是否已設置為1 int test(int n) { return a[n&>&>SHIFT] (1&<&<(nMASK)); }

再次言歸正傳。

取余是通過電路進行二進位除法來實現的，簡略的原理圖（具體的要複雜很多）我記得在數電的教科書上有，改天我查到了補上。

那麼二進位除法是怎樣的呢？其實網上一搜一堆原理。（TAT我在高鐵上還以為是我自創來著）

（我們可以直接用減法來實現，但這樣的話，如果是10324除以3，就會循環非常多次。）

針對這種情況，我的想法是：

1，將除數左移，至與被除數的最高位對齊或者小一位。（小一位是因為待會得用被除數減去左移後的除數，這個時候被除數肯定&>（除數*某個2的n次））

2，被除數減去左移後的除數。

3，除數左移，這個時候，被除數肯定&>（除數*某個2的n1次）

。。。。

不停迭代，直至被除數&<除數，這個時候被除數就是餘數。

我們先來看不考慮商，僅僅考慮取余

我們隨便找兩個數，假設是2381除以7。

2381，二進位為1001 0100 1101

7，二進位為111

用2381的最高位1001減去111，得10。相當於2381-7*256 = 589 （這個縮小得很快的，所以其實除非除數和被除數非常大，或者超出機器位數，每次操作要多讀幾遍，肯定會有性能損失）

589 = 剛才的答案10+之前沒用過的右邊01001101 = 1001001101

再次重複剛才的過程

589的最高位1001減去111，得10。相當於589-7*64 = 141

141 = 剛才的答案10+之前沒用過的右邊001101 = 10001101

。。。。。

如此循環，最後，當被除數剩1時即為餘數。

那麼商跑到哪裡去了呢？

請看二進位除法原理，原理和我這個是一樣的，只不過必須控制移位

繼續用剛才的例子，2381除以7

以下是不停計算的過程,{}里的是每一次計算的答案，()里的是每一次沒參加計算的位

1001 (0100 1101) //2381 -0111 //7 -------------------------- {0010}(0100 1101) //此時0010&>0，所以商的最高位為1 -0011 1 //這一次不夠減，所以商的次高位為0 除數繼續右移 0010 01(00 1101) -0001 11 ---------------------------- {0000 10}(00 1101) //此時000010&>0，所以商的第3高位為1 -0000 11 1 //此時100減111&<0，不夠減，所以商的第4高位為0

除數繼續右移

。。。。。。

如此循環，最後答案為101010100，最前面的1010就是前面四次計算的值。雖然很麻煩，但用電路來實現速度很快。

求余電路

對於第一個問題，取余不是機器語言層面的么？與高級語言有關係么？

簡單來說就是CPU先實現了加法，然後通過加一個負數還是怎麼滴弄出了減法（忘了）。

除法理論上來說就是除數不斷減被除數，然後記錄減的次數，然後減到最後再減就是負數了，就停下來，剩下的那個數就是餘數，做減法的次數就是商……

當然實際上優化更複雜，不過原理大體上是這樣，至於加法怎麼實現請看半加器和累加器電路，很簡單的。

也就是說乘法和除法都是 O(log n) 的。

補充和更正在評論……,

Intel一條除法指令時間差不多是乘法指令的七八倍。

我記得32位和64位乘法指令都是三四個周期，32位除法指令要二三十個周期，64位更慢。

顯然乘法指令用專門的乘法電路直接算出結果，除法指令就是笨辦法試商算出來的。

除以常量，一般都不執行除法指令，而是乘以它的倒數，浮點除法都這麼做。整數除法，基本思路一致，則是乘以除數的倒數的2的32次方倍來實現的。具體就是一個乘法，一個移位，就得到商。乘法的被乘數已經算好了的。

取余的運算是乘法-移位求出商，然後乘法-減法求出餘數。加減法一般1個周期，加起來不到10個周期，比除法指令快很多。

除以變數沒辦法。它的倒數不可能實現算好。只能老老實實執行除法指令

我想瞎說下。

圖靈機原型中只有兩種操作：

1，改變當前位置0和1的狀態；

2，將指針從一個位置移到另一個位置。

所以我認為，在計算機中，取餘數是比除法更基本的操作。a%b，即指針從a的起始每次移動b個單位直至剩餘。

我猜的。

a-(a 整除 b) * b

取余是先除法算出商然後得到餘數

除法顯然不是一個個減的之前回答的確定寫過代碼嘛？你一個100000000/1要算多久？

除法是類似D/C轉換電路的做法從高位算起在確定第i位的時候如果當前的商加2^i之後乘上除數比被除數小第i位就是1 否則是0

計算機中的取余，取模，本質上是除法運算，得到商的同時也會得到餘數，沒有所謂的演算法之說。

如果要說演算法，從數學上將，CPU中的ALU在算術上只幹了兩件事，加法，移位，頂多加上取反，在邏輯上，只有與或非異或。

加法-&>加法。

減法-&>取反，加法。

乘法-&>移位，邏輯判斷，累加

除法-&>移位，邏輯判斷，累減

至於乘法除法為什麼這樣，搜索二進位數如何進行乘法除法，說白了，和我們熟悉的十進位運算流程上一模一樣。

所以只需要加法器，移位器和基本邏輯門電路就構成一個簡單的ALU。

從硬體實現上講，可以看出，實現這四種基本運算只需要上述硬體組件就行。早期的cpu里結構簡單，只有這些組件，沒有專門的乘法器、除法器。但是可想而知效率也是低下的（其中除法效率最低，因為每次移位後比乘法還多出一次試錯操作），後來的cpu會集成專門的並行處理電路在cpu內建的協處理器（比如浮點運算器，很早的cpu是沒有專門計算浮點的電路的）中，在硬體上實現，這樣計算速度就快了。當然，計算的邏輯還是沒變。

另外，正如前面回答者提到的，當操作數為2的整數次冪時，乘法除法簡化為位移，幾乎沒有計算量，所以很多相應的設計就取2的整數次冪。