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

引言

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

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

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

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

無符號乘法

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

補碼乘法

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

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

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

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

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

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

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

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

有了上面的基礎，我們就可以使用移位和加法對乘法優(yōu)化了。對于任意一個整數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ōu)化就取決于二者的速度了。