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

引言

運(yùn)算一直是程序運(yùn)行當(dāng)中一個(gè)重要的環(huán)節(jié),，而在二進(jìn)制的運(yùn)算過(guò)程當(dāng)中，加法運(yùn)算又是重中之重,，它基本上奠定了二進(jìn)制運(yùn)算的基礎(chǔ),。因?yàn)闊o(wú)論是減法還是乘法，都可以由加法運(yùn)算來(lái)替代,，唯有除法不能由加法替代,。

了解計(jì)算機(jī)運(yùn)算的規(guī)律，可以有助于我們理解很多程序代碼上無(wú)法理解的內(nèi)容,。比如上章提到的溢出問(wèn)題,，在了解了加法運(yùn)算的原理之后，相信猿友們都可以輕松的知道為何有些運(yùn)算會(huì)得到意想不到的結(jié)果,。

這里還需要提一點(diǎn)的是,，不同的處理器所采取的運(yùn)算方式可能是有細(xì)微的差別的，因此也不能一概而論,。因此我們大多時(shí)候會(huì)盡量討論運(yùn)算的抽象數(shù)學(xué)特性,，抽象的東西大部分時(shí)候總是可靠的，這種特性為跨平臺(tái)提供了基礎(chǔ),，不過(guò)也并非總是如此,，畢竟LZ只聽(tīng)說(shuō)過(guò)浮點(diǎn)數(shù)運(yùn)算標(biāo)準(zhǔn),，還沒(méi)聽(tīng)說(shuō)過(guò)整數(shù)運(yùn)算標(biāo)準(zhǔn)，不知道究竟是LZ孤陋寡聞了,，還是確無(wú)此物,。

正因如此，我們了解一下這些運(yùn)算的抽象性,，會(huì)有助于我們理解程序代碼級(jí)無(wú)法理解的東西,。

無(wú)符號(hào)乘法

無(wú)符號(hào)的乘法與加法類似，它的運(yùn)算方式是比較簡(jiǎn)單的,，只是也可能產(chǎn)生溢出,。對(duì)于兩個(gè)w位的無(wú)符號(hào)數(shù)來(lái)說(shuō)，它們的乘積范圍在0到(2w-1)2之間,，因此可能需要2w位二進(jìn)制才能表示,。因此由于位數(shù)的限制，假設(shè)兩個(gè)w位的無(wú)符號(hào)數(shù)的真實(shí)乘積為pro,，根據(jù)截?cái)嗟囊?guī)則,，則實(shí)際得到的乘積為 pro mod 2w。

補(bǔ)碼乘法

與加法運(yùn)算類似,，補(bǔ)碼乘法也是建立在無(wú)符號(hào)的基礎(chǔ)之上的,，因此我們可以很容易的得到，對(duì)于兩個(gè)w位的補(bǔ)碼數(shù)來(lái)說(shuō),，假設(shè)它們的真實(shí)乘積為pro,，則實(shí)際得到的乘積為 U2Tw(pro mod 2w)。

上面的式子我們有一個(gè)假設(shè),，就是假設(shè)對(duì)于w位的兩個(gè)補(bǔ)碼數(shù)來(lái)說(shuō),，它們的乘積的低w位與無(wú)符號(hào)數(shù)乘積的低w位是一樣的。這意味著計(jì)算機(jī)可以使用一個(gè)指令執(zhí)行無(wú)符號(hào)和補(bǔ)碼的乘法運(yùn)算,。

在書(shū)中給出了這一過(guò)程的證明,，我們來(lái)大概看一下，這里主要應(yīng)用了無(wú)符號(hào)編碼和補(bǔ)碼編碼的關(guān)系,，其中x’和y’分別代表x和y的補(bǔ)碼編碼,。

這里運(yùn)用的主要技巧就是2w mod 2w = 0。

乘法運(yùn)算的優(yōu)化

根據(jù)我們小學(xué)所學(xué)的乘法運(yùn)算,，我們知道,，假設(shè)兩個(gè)w位的二進(jìn)制數(shù)相乘,，則需要進(jìn)行w次與運(yùn)算,，然后進(jìn)行w - 1次加法運(yùn)算才能得到結(jié)果。從此不難看出,，乘法運(yùn)算的時(shí)間周期是很長(zhǎng)的,。因此計(jì)算機(jī)界的高手們想出了一種方式可以優(yōu)化乘法運(yùn)算的效率，就是使用移位和加法來(lái)替代乘法。

上述優(yōu)化的前提是對(duì)于一個(gè)w位的二進(jìn)制數(shù)來(lái)說(shuō),，它與2k的乘積,，等同于這個(gè)二進(jìn)制數(shù)左移k位，在低位補(bǔ)k個(gè)0,。在書(shū)中對(duì)這一等式進(jìn)行了證明,，過(guò)程如下。

這個(gè)過(guò)程主要應(yīng)用了無(wú)符號(hào)編碼的公式,，各位猿友應(yīng)該不難看懂,。

有了上面的基礎(chǔ)，我們就可以使用移位和加法對(duì)乘法優(yōu)化了,。對(duì)于任意一個(gè)整數(shù)y,，它總能使用二進(jìn)制序列表示（假設(shè)不超過(guò)二進(jìn)制的表示范圍），因此我們可以將x和y乘積的二進(jìn)制序列表示為如下形式（此公式在書(shū)中沒(méi)有展現(xiàn)）,。

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

我們舉個(gè)例子,，對(duì)于x * 17，我們可以計(jì)算x * 16 + x = (x << 4) + x ,，這樣算下來(lái)的話,，我們只需要一次移位一次加法就可以搞定這個(gè)乘法運(yùn)算。而對(duì)于x * 14,，則可以計(jì)算 x * 8 + x * 4 + x * 2 = (x << 3) + (x << 2) + (x << 1) ,，更快的方式我們可以這么計(jì)算，x * 16 - x * 2 = (x << 4) - (x << 1) ,。

這里最后需要提一下的是,，加法、減法和移位的速度并不會(huì)總快于乘法運(yùn)算,，因此是否要進(jìn)行上面的優(yōu)化就取決于二者的速度了,。