进位
来自维基百科,自由的百科全书
来自维基百科,自由的百科全书
在四則運算的加法及減法中,进位(carry)是指某两数或多数的某一位,经計算後產生一個數字,會影響此位左侧高一位的計算結果。在加法的算法中,一般會由最小位數開始計算,計算後若有進位,上一位數字計算時需考慮進位的結果。例如6和7相加後得到13,3是個位數,和6跟7相同,會進位1到十位數,此處的1即為進位。若在減法中,也會有類似的情形,稱為借位(borrow)。
进位也在更高等的數學中出現。在加法器的電路設計中,进位也是重要的一部份。只處理二個位元相加,無法考慮進位的稱為半加法器,能處理二個位元及一個進位位元相加的才稱為全加法器[1]。
以下是一個直式計算中,用到進位的例子:
¹ 27 + 59 ---- 86
7 + 9 = 16,最上方的1就是進位,一般會用較小的數字,避免和原來相加的數字混淆。
相反的是借位,以下是借位的例子:
−1 47 − 19 ---- 28
此處7 − 9 = −2,因此改用(10 − 9) + 7 = 8,其中的10是從上一位數借來的。有兩種教借位的方式:
進位是机械计算器的基本挑戰之一。其中有二個困難點:第一個是一個進位可能會讓一個至數個位數的數值變化,例如某三位數已是999,因下一位數進位要加1,就會造成四個位數的變動,另一挑戰是進位可能在較高位數計算完成前就已經出現。
大部份的机械计算器是在原始加法的運算之後,再另外有一個週期執行進位的運算。在加法過程中,若有進位,會在對應的位數記錄,在進位週期中,再根據記錄進位的位數處理進位。這個流程需要先確認最低位數,再依序確認較高的位數。
像帕斯卡計算器(目前已知第二古老,而且還可以找到的機械式計算器),使用另一種方式來處理:將數字從0加到9的過程中,觸動一個機械裝置儲存能量,若再由9進到0,釋放該該機械裝置的能量,讓下一個位數加1。帕斯卡在他的機器中用到了重物以及重力。另一個使用類似方式的機器是19世紀大為成功的Comptometer,用彈簧代替重力。
有些先進的计算器則是連續傳動(continuous transmission):在某一位數加1時,自動在較高一位數加1/10(這也會將再高一位數加1/100,以此類推)。一些早期先進的计算器(例如1870年柴比雪夫的計算器)[2],以及1886年Selling的設計[3])都使用此方法,但都不成功。1930年代初期Marchant calculator也引入了連續傳動方式,非常成功,開始了Silent Speed計算器。Marchant(後來的SCM企業)繼續使用此一技術並且創新,讓連續傳動的机械计算器到達非常快的速度,一直到1960年代末,机械计算器時代結束為止。
大部份的電腦,若數學運算後最高位元有進位(或是因為位元左移運算而出現的進位),會用特殊的旗標進位旗標記錄,之後運算較高位數時,可以進位。在減法出現借位時,也會設定相同的「進位旗標」,不過因為二補數運算的效果,其意義會相反。一般來說,進位旗標的1會讓算術邏輯單元進行一次加法,若相加的資料長度大於CPU一次可處理的長度,就要考慮進位旗標的影響。針對減法,有二種不同的作法,大部份的處理器會在有借位時設定「進位旗標」,但有些處理器(像是6502及PIC微控制器)是在有借位時清除「進位旗標」。