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)容。比如上章提到的溢出問題，在了解了加法運(yùn)算的原理之后，相信猿友們都可以輕松的知道為何有些運(yùn)算會(huì)得到意想不到的結(jié)果。

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

在書中給出了這一過(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。在書中對(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)制序列表示為如下形式（此公式在書中沒有展現(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)化就取決于二者的速度了。