所謂編程，就是通過計算機語言，對存放在一定位置上的比特信息進行一系列移動和處理，最終得到某些結(jié)果的過程。而高性能的編程就是通過降低開銷和改變操作方式來讓這些操作的代價最小化。

要了解哪些開銷是可以省去的，哪些操作是可以優(yōu)化的，就不得不從更底層的角度看待計算機。

計算機中的信息表示

計算機中，信息都是以0與1兩種狀態(tài)組成的序列。要了解計算機中信息的含義，我們除了需要了解進制以外，還需要人為制定一些規(guī)則，幫助我們規(guī)范信息的含義，這些規(guī)則包括了數(shù)據(jù)寬度和原碼補碼反碼的規(guī)則，在這些規(guī)則之上計算機才能夠進行基本運算。

進制

可能因為人生來有十個手指的關(guān)系，人在計數(shù)的時候天然選擇了十進制。而電子計算機的核心是由晶體管組成的，而晶體管只有通電和不通電兩種狀態(tài)。因此計算機天然就選擇了二進制。所謂進制，無非就是指定如何用一套符號進行計數(shù)和運算的規(guī)則。我們用0和1兩個符號計數(shù)，那么就是二進制；用0-9十個符號計數(shù)，就是十進制；再添上abcdef，就是十六進制了；

由于我們表示數(shù)字的符號系統(tǒng)（進制）不同，自然帶來了運算的不同，然而其基本思想是相同的。

譬如二進制下的加法，2+3等于多少呢？我們可以用二進制計數(shù)符號來寫下0-10的結(jié)果：

十進制對照：  0     1    2     3      4      5      6       7         8          9         10
二進制數(shù)字：00  01  10  11  100  101  110   111   1000  1001  1010

在十進制下，我們經(jīng)過多年教育，自然掌握了2+3的結(jié)果，那就是5。我們不妨回想下我們是如何知道這件事的：在小學(xué)的時候我們就熟記十進制加法表了。

可以說，運算的本質(zhì)，就是查表。怎么查？2+3，也就是從2開始，向后查3個數(shù)，對十進制來說，也就是5了。2*3又如何呢？乘法也就是找?guī)讉€幾的問題。我們從1開始（人類的自然計數(shù)都是從1開始的），向后查3次2個數(shù)，得到了6。而減法和除法又可以用加法與乘法進行表示，就不再贅述。

知道了這一點，我們也就可以采用同樣的方式來在二進制乃至任意進制下進行運算了：2+3在二進制中，無非也就是從2的二進制表示10開始，向后找3個數(shù)，得到了101，也就是十進制的5。

數(shù)據(jù)寬度

大多數(shù)計算機中使用8位的塊作為最小的可尋址的內(nèi)存單位，也就是字節(jié)（byte）。通過這樣的分割，計算機就可以將內(nèi)存視為一個由字節(jié)組成的很大的數(shù)組，而數(shù)組中的每個字節(jié)都有其對應(yīng)的唯一標識，稱為它的地址。對于32位計算機來說，有個地址，也就是能夠存儲4GB左右個地址（這也是32位機器內(nèi)存限制4GB的原因），而64位機器則有個地址，大約為16EB（所以我們通常說64位機器支持無線擴展內(nèi)存）。

這樣，通過地址，計算機就可以定位到內(nèi)存中的任意位置，進行數(shù)據(jù)的讀出和寫入?，F(xiàn)在的問題在于，我們的一次讀出和寫入，需要讀/寫多少位呢？這就需要數(shù)據(jù)寬度來指定。

在靜態(tài)編程語言中，我們通常能看到類型指定關(guān)鍵詞，如int, double, char等，這些關(guān)鍵詞就指明了數(shù)據(jù)在內(nèi)存中定義的寬度。通過地址定位以及數(shù)據(jù)寬度，我們就可以從存儲中進行正確的數(shù)據(jù)讀寫了（同時，也正是因為數(shù)據(jù)寬度，計算機對數(shù)字的保存從某種意義上來說是并不精確的，對于整數(shù)會產(chǎn)生溢出問題，對于浮點數(shù)會產(chǎn)生截斷問題）。

但是我們提到了，一個字節(jié)由8位組成，其值域在二進制中也就是，這種表達太過冗長，而十進制的與二進制之間轉(zhuǎn)換非常麻煩。為了簡化對位狀態(tài)的描述，十六進制就應(yīng)運而生了。一個十六進制數(shù)可以描述4個二進制位的狀態(tài)，一個字節(jié)也就可以用兩個十六進制數(shù)描述，其值域為。這也是我們通常在底層查看位狀態(tài)時看到的表示方法。

負數(shù)的表示 -- 原碼補碼和反碼

規(guī)則定義

通過了對寬度的定義，我們可以從計算機存儲中取得01序列并進行適當?shù)摹胺g”，得到它表示的整數(shù)（或者字符）。但是我們直到整數(shù)不止包括自然數(shù)，還包括負數(shù)，那么負數(shù)又應(yīng)該如何表示呢？答案就在于原碼補碼和反碼這套規(guī)則（在計算機體系中我們遇到的一切規(guī)則都是為了方便計算和其他操作人為定義的，畢竟自然界中并沒有野生的計算機）。

原碼補碼和反碼規(guī)則是用來表示負數(shù)的，因而它對于正負數(shù)的處理規(guī)則不同也是自然而然的：

• 對于正數(shù)和無符號數(shù)，原碼補碼和反碼都是相同的；
• 對于負數(shù)，原碼第一位為1，表示負數(shù)，剩余位和其正數(shù)相同；補碼保持符號位不變，剩余位取反；反碼在補碼基礎(chǔ)上+1

5的原碼補碼和反碼（只考慮8位）
原碼：0000 0101
反碼：0000 0101
補碼：0000 0101
--------------------
-5的原碼補碼和反碼
原碼：1000 0101
反碼：1111 1010
補碼：1111 1011

規(guī)則作用

為何需要這套規(guī)則呢？這是方便計算機將減法轉(zhuǎn)化為加法，比如我們需要計算8-5，那么直接用補碼相加就可以了：

用補碼相加計算8-5：
8的補碼:  0000 1000
-5的補碼: 1111 1011
補碼相加: 0000 0011  ===> 符號位為0，是正數(shù)；從而解析出結(jié)果為3
--------------------
用補碼相加計算2-5：
2的補碼:  0000 0010
-5的補碼: 1111 1011
補碼相加: 1111 1101 ===> 符號位為1，是負數(shù)；解析時需要向其原碼轉(zhuǎn)化
反碼：  1111 1100
原碼：  1000 0011 ===> 得到結(jié)果為-3

這樣，我們用兩個數(shù)的補碼直接相加，就能得到其對應(yīng)結(jié)果的補碼，無論加數(shù)是正是負。

規(guī)則原理

從原碼到補碼的原理其實也不復(fù)雜，用一個詞說明，就是同余。

我們先看一下mod的數(shù)學(xué)定義：

根據(jù)這個定義，我們不但可以應(yīng)付正數(shù)的mod，還可以處理負數(shù)：

求-25 mod 12
-25 mod 12 = -25 - 12 * (-3) = 11

這里我們就看到一個很有意思的性質(zhì)：11 mod 12 = 11，-25 mod 12 = 11，也就是說11和-25對于12是同余的。正如我們看到的鬧鐘，上面有12個代表小時的刻度，我們將一根時針向前撥動11個小時，和向后撥動25個小時，最后的位置是相同的。進一步地，所有的同余數(shù)對于我們的指針造成的影響都是相同的：向前撥動11小時，向前撥動23小時，向后撥動1小時，向后撥動25小時，最后指針停的位置都是相同的 。

下圖演示了作用于鬧鐘時針上的同余數(shù)：

1-同余數(shù).png

知道了同余數(shù)之后，我們就可以將減法和加法在一定進制和數(shù)據(jù)寬度下進行轉(zhuǎn)化了。對上面的圖，我們可以看做12進制下寬度為1的運算，此時1-1和1+11的結(jié)果是相同的。

我們計算機的原碼和補碼也是相同的道理，取一個字節(jié)作為例子，一個字節(jié)能表示的數(shù)范圍是，也就可以看做是256進制下寬度為1的數(shù)。

考察-5的補碼：
1111 1011  ===> 轉(zhuǎn)化為10進制就是251
251 mod 256 = 251
-5 mod 256 = 251

根據(jù)上面描述過的原理，a-5和a+251在256進制下寬度為1時運算結(jié)果是等價的。這也就是補碼的原理：找到原碼描述的數(shù)字的同余數(shù)，從而幫助計算機將減法轉(zhuǎn)化為加法。

位運算

基本的位運算有：與運算、或運算、異或運算、非運算，以及位移動。

其中與運算、或運算、異或運算都是雙目運算符，我們可以簡單的用開關(guān)和燈泡來形象化理解：

2-與或異或.png

其中兩個開關(guān)分別代表參與運算的兩個位a與b的狀態(tài)，燈泡的狀態(tài)則代表輸出c。

對于與運算a&b=c，只有當a和b都是1時，c才是1。

對于或運算a|b=c，當a與b任一為1時，c為1。

對于異或a^b=c，當a與b狀態(tài)不同時，c為1。

非是單目運算符，也就是對輸入位狀態(tài)進行取反：當輸入為1（開關(guān)閉合時），輸出為0（燈不亮）；當輸入為0（開關(guān)打開時），輸出為1（燈泡亮）。

3-非.png

而位移動就是對位狀態(tài)的直接操作，分為<<左移和>>右移兩種操作。

<<左移，相當于在寬度給定的數(shù)據(jù)范圍內(nèi)，對數(shù)據(jù)*2
例如：
在寬度為8的情況下，5的二進制表示為：
5:         0000 0101
5<<1:  0000 1010 ===> 也就是10

>>右移，相當于在寬度給定的數(shù)據(jù)范圍內(nèi)，對數(shù)據(jù)/2（小數(shù)部分直接舍去）
例如：
在寬度為8的情況下，9的二進制表示為：
9:        0000 1001
9>>1: 0000 0100 ===> 也就是4

基本計算的實現(xiàn)

通過位運算，我們就能夠很方便的實現(xiàn)加減乘除這四種基本運算。在這四種基本運算中，最核心的是加法，之前我們已經(jīng)展示了減法如何能用加法進行表示。而乘法也無非加法的擴展，除法則是乘法的一種變形。只要能夠進行加法運算，那么一切就迎刃而解。

計算機是如何進行加法的呢？關(guān)鍵就在于異或和位移動兩種位運算，異或也叫不進位加法，而通過位移動，則可以實現(xiàn)等同于進位的功效。我們可以先用語言描述以下計算機進行加法的操作過程，然后通過例子來理解。

假設(shè)我們需要計算a+b

• Step1: 首先通過異或，獲得沒有進位的加法結(jié)果 sum=a^b
• Step2: 通過與運算判斷哪一位會產(chǎn)生進位，carry=a&b；
• Step3: 通過左移實現(xiàn)進位carry <<= 1
• Step4: 在結(jié)果上累加進位newsum = sum^carry
• Step5: 檢查sum與carry的累加是否會產(chǎn)生進位，如果sum&carry != 0，那么回到步驟1，此時a=newsum,b=carr<<1；如果不產(chǎn)生進位，則完成了加法

我們來看一個例子，用11+25為例：

* iter1: a = 11，b=25
0000 1011
0001 1001
                   +
-----------------
0001 0010   ---> Step1: 異或運算得到的sum
0000 1001   ---> Step2: 與運算得到carry
0001 0010   ---> Step3: carry左移一位
0000 0000   ---> Step4: newsum^=carry
0001 0010   ---> Step5: sum&carry不為0，需要進入下一次迭代

* iter2: a = 0，b=36
0000 0000
0010 0100
                   +
-----------------
0010 0100   ---> Step1: 異或運算得到的sum
0000 0000   ---> Step2: 與運算得到carry
0000 0000   ---> Step3: carry左移一位
0010 0100   ---> Step4: newsum^=carry
0000 0000   ---> Step5: sum&carry為0，不需要進入下一次迭代

最終結(jié)果即為0010 0100，也即是十進制的36