程式師世界 >> 編程語言 >> 更多編程語言 >> 匯編語言 >> 計算機系統原理（十）二進制整數的乘法運算和除法運算

計算機系統原理（十）二進制整數的乘法運算和除法運算

編輯：匯編語言

2.5我們著重介紹了二進制整數的加、減運算，本次我們繼續介紹乘、除運算。本章是迄今為止最難的一章，希望各位猿友有所收獲，也別忘了“點個推薦哦”。

引言

運算一直是程序運行當中一個重要的環節，而在二進制的運算過程當中，加法運算又是重中之重，它基本上奠定了二進制運算的基礎。因為無論是減法還是乘法，都可以由加法運算來替代，唯有除法不能由加法替代。

了解計算機運算的規律，可以有助於我們理解很多程序代碼上無法理解的內容。比如上章提到的溢出問題，在了解了加法運算的原理之後，相信猿友們都可以輕松的知道為何有些運算會得到意想不到的結果。

這裡還需要提一點的是，不同的處理器所采取的運算方式可能是有細微的差別的，因此也不能一概而論。因此我們大多時候會盡量討論運算的抽象數學特性，抽象的東西大部分時候總是可靠的，這種特性為跨平台提供了基礎，不過也並非總是如此，畢竟LZ只聽說過浮點數運算標准，還沒聽說過整數運算標准，不知道究竟是LZ孤陋寡聞了，還是確無此物。

正因如此，我們了解一下這些運算的抽象性，會有助於我們理解程序代碼級無法理解的東西。

無符號乘法

無符號的乘法與加法類似，它的運算方式是比較簡單的，只是也可能產生溢出。對於兩個w位的無符號數來說，它們的乘積范圍在0到(2w-1)2之間，因此可能需要2w位二進制才能表示。因此由於位數的限制，假設兩個w位的無符號數的真實乘積為pro，根據截斷的規則，則實際得到的乘積為 pro mod 2w。

補碼乘法

與加法運算類似，補碼乘法也是建立在無符號的基礎之上的，因此我們可以很容易的得到，對於兩個w位的補碼數來說，假設它們的真實乘積為pro，則實際得到的乘積為 U2Tw(pro mod 2w)。

上面的式子我們有一個假設，就是假設對於w位的兩個補碼數來說，它們的乘積的低w位與無符號數乘積的低w位是一樣的。這意味著計算機可以使用一個指令執行無符號和補碼的乘法運算。

在書中給出了這一過程的證明，我們來大概看一下，這裡主要應用了無符號編碼和補碼編碼的關系，其中x’和y’分別代表x和y的補碼編碼。

這裡運用的主要技巧就是2w mod 2w = 0。

乘法運算的優化

根據我們小學所學的乘法運算，我們知道，假設兩個w位的二進制數相乘，則需要進行w次與運算，然後進行w - 1次加法運算才能得到結果。從此不難看出，乘法運算的時間周期是很長的。因此計算機界的高手們想出了一種方式可以優化乘法運算的效率，就是使用移位和加法來替代乘法。

上述優化的前提是對於一個w位的二進制數來說，它與2k的乘積，等同於這個二進制數左移k位，在低位補k個0。在書中對這一等式進行了證明，過程如下。

這個過程主要應用了無符號編碼的公式，各位猿友應該不難看懂。

有了上面的基礎，我們就可以使用移位和加法對乘法優化了。對於任意一個整數y，它總能使用二進制序列表示（假設不超過二進制的表示范圍），因此我們可以將x和y乘積的二進制序列表示為如下形式（此公式在書中沒有展現）。

x * y = x * (yw-12w-1 + ... + y020) = (x << w-1) * yw-1 +....+ (x << 0 ) * y0

我們舉個例子，對於x * 17，我們可以計算x * 16 + x = (x << 4) + x ，這樣算下來的話，我們只需要一次移位一次加法就可以搞定這個乘法運算。而對於x * 14，則可以計算 x * 8 + x * 4 + x * 2 = (x << 3) + (x << 2) + (x << 1) ，更快的方式我們可以這麼計算，x * 16 - x * 2 = (x << 4) - (x << 1) 。

這裡最後需要提一下的是，加法、減法和移位的速度並不會總快於乘法運算，因此是否要進行上面的優化就取決於二者的速度了。

無符號除法

除法與乘法不同，它不滿足加法的分配律，也就是設y = m + n ， x/y != x/m + x/n。而且不幸的是，它有時候會比乘法運算更慢，但是我們只能針對除數可表示為2k的除法運算進行優化，轉換為算數右移或者邏輯右移k位的運算（無符號數為邏輯右移，為正數時，邏輯右移與算術右移效果一樣）。

由於是除法，因此我們會涉及到捨入的問題。這裡定義└x/y┘的值為a'，x/y為a，則對於a'，它是唯一一個整數，滿足 a' =< a < a'+1。

比如└2.1┘的值就為2，而對於└-2.1┘則為-3，如果本身就是整數，則等於自身。

書中給出了無符號數除以2k等價於右移k位（w > k >= 0）的證明，這一證明過程相對比較復雜一點，LZ這裡給出一個相對簡單的證明方式，不采用書上的證明。如果各位看LZ的證明看不懂的話，也可以參照一下書上的方式。

我們假設對於一個w位的無符號數來說，假設它的位表示為[xw-1....x0]，則x = xw-12w-1 + .... + x020 。因此就有以下結果。

x/2k = xw-12w-1-k +... + xk20 + xk-12-1 +...+ x02-k = B2Uw-k([xw-1....xk]) + xk-12-1 +...+ x02-k

由於xk-12-1 +...+ x02-k <= 2-1 + .... 2-k = (1-(1/2)k) < 1 （這裡是證明的關鍵一步，先假設所有位為1，則利用等比數列求和公式即可得到），因此有└xk-12-1 +...+ x02-k┘ = 0。

因此我們可以得到└x/2k┘ = └B2Uw-k([xw-1....xk])┘ + └xk-12-1 +...+ x02-k┘ = └B2Uw-k([xw-1....xk])┘ = B2Uw-k([xw-1....xk]) = x >> k。

更直觀的，我們可以使用程序驗證這一結果，看下面的Java代碼。

public class Main {
        
    public static void main(String[] args) {
        int a = 17;
        int b = 8;
        int c = a/b;
        System.out.println("a:" + Integer.toBinaryString(a));
        System.out.println("b:" + Integer.toBinaryString(b));
        System.out.println("c:" + Integer.toBinaryString(c));
        System.out.println("a >> 3:" + Integer.toBinaryString(a >> 3));
    }
}

查看本欄目

除法的補救

既然在捨入時，一個負數右移k位不等價於把它除以2k。那麼為了使用這種優化，計算機界的大神們自然要想辦法解決這個問題。於是他們想出了一個辦法，即“偏置”這個值（不得不佩服這些大神們）。

首先我們定義┌x/y┐的值為a'，x/y為a，則對於a'，它是唯一一個整數，滿足 a'-1 < a <= a'。

在上面的定義基礎上，“偏置”的含義就是，我們有┌x/y┐ = └(x+y-1)/y┘。這一過程的證明不難理解，我們假設x = ky + r（我們考慮r > 0 ，此時會有捨入發生），則有。

└(x+y-1)/y┘ = └(ky+r+y-1)/y┘ = k + └(r+y-1)/y┘ = k + 1

可以看出在做了這個處理之後，也就是將x加上y-1的偏移量，此時在捨入時，結果會在原來的基礎上加1。這也正是“偏置”的含義所在，它會將捨入“偏置”到向上捨入。

下面我們將補碼除法當中的程序按照這種方式修復一下，看是不是這個結果，如下。

public class Main {
        
    public static void main(String[] args) {
        int a = -17;
        int b = 8;
        int c = a/b;
        System.out.println("a:" + Integer.toBinaryString(a));
        System.out.println("b:" + Integer.toBinaryString(b));
        System.out.println("c:" + Integer.toBinaryString(c));
        System.out.println("(a+b-1) >> 3:" + Integer.toBinaryString((a+b-1) >> 3));
        System.out.println("c:" + c);
        System.out.println("(a+b-1) >> 3:" + ((a+b-1) >> 3));
    }
}

此處我們將a“偏置”，也就是加上b-1的偏移量，我們來看結果。