程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 匯編語言 >> 計算機系統原理(十) 二進制整數的乘法運算和除法運算

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

編輯:匯編語言

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的偏移量,我們來看結果。

可以看出,在偏置之後,在負結果捨入時,移位運算的結果將會是我們期望得到的,這樣我們便可以使用這一技巧進行優化了。

文章小結

到這裡,二進制整數的運算就介紹完了,本章難度較高,因此各位猿友可能要費點力氣了。下一章我們將進入浮點數的世界,一起期待吧。

作者:zuoxiaolong(左潇龍)

出處:博客園左潇龍的技術博客--http://www.cnblogs.com/zuoxiaolong

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved