??計(jì)算機(jī)為什么會加減乘除骚揍？筆者是一直都沒了解過，認(rèn)為加減乘除就是理所當(dāng)然的事情啰挪，但計(jì)算機(jī)中的萬物皆為0信不、1嘲叔，筆者的認(rèn)為是不可能那么簡單的。
其實(shí)說直接點(diǎn)抽活，就是計(jì)算機(jī)的原理是什么硫戈？
1. 二進(jìn)制
二進(jìn)制就是計(jì)算機(jī)使用的“語言”。簡單舉例來說就是：人類使用十進(jìn)制來計(jì)數(shù)酌壕，它的運(yùn)算規(guī)則是“逢十進(jìn)一”掏愁。二進(jìn)制就是“逢二進(jìn)一”的運(yùn)算規(guī)則。
為什么計(jì)算機(jī)使用二進(jìn)制呢卵牍？這個(gè)可以歸結(jié)于一個(gè)人有十根手指果港，所以人類普遍認(rèn)知是使用十進(jìn)制。計(jì)算機(jī)是由一大堆電子電路組成的糊昙，使用二進(jìn)制正好對應(yīng)電路里的高低電平（大部分電子器件只有兩種狀態(tài)）辛掠，這就好比計(jì)算機(jī)只有“兩根手指”。
1.1 原碼
原碼是二進(jìn)制的一種表現(xiàn)形式释牺。其為一個(gè)整數(shù)絕對值的二進(jìn)制萝衩，加上符號位（0為正，1為負(fù)）没咙。
| 整數(shù) | 絕對值 | 絕對值的二進(jìn)制 | 原碼 |
|---|---|---|---|
| +3 | 3 | 000 0011 | 0000 00011 |
| +3 | 3 | 000 0011 | 1000 00011 |
- 原碼是給人看的二進(jìn)制猩谊，不是計(jì)算機(jī)保存的，不直接參與計(jì)算祭刚。
1.2 反碼
針對負(fù)數(shù)做處理牌捷，在原碼基礎(chǔ)上，除了符號位涡驮，其它位取反暗甥。
| 整數(shù) | 絕對值的二進(jìn)制 | 原碼 | 反碼 |
|---|---|---|---|
| +3 | 000 0011 | 0000 00011 | 0000 00011 |
| +3 | 000 0011 | 1000 00011 | 1111 11100 |
- 反碼是在計(jì)算機(jī)存儲的二進(jìn)制，但不是真正的二進(jìn)制值捉捅，它不直接參與計(jì)算撤防。
1.3 補(bǔ)碼
補(bǔ)碼是真正的二進(jìn)制值，主要針對負(fù)數(shù)做處理棒口，在反碼的基礎(chǔ)上加1寄月。
| 整數(shù) | 原碼 | 反碼 | 補(bǔ)碼 |
|---|---|---|---|
| +3 | 0000 00011 | 0000 00011 | 0000 00011 |
| +3 | 1000 00011 | 1111 11100 | 1111 11101 |
1.4 理解補(bǔ)碼
假如一個(gè)時(shí)鐘現(xiàn)在顯示的是10點(diǎn)鐘，如何將它調(diào)到6點(diǎn)鐘无牵？
解：有兩種方法漾肮，一是向后撥8個(gè)小時(shí)，二是向前撥4個(gè)小時(shí)
在這個(gè)例子中合敦，8 和 4 互為補(bǔ)數(shù)初橘，也就是說4的補(bǔ)碼是8,8的補(bǔ)碼是4，而這個(gè)時(shí)鐘的模就是12
注意：可能有人會想，在往后調(diào)8個(gè)小時(shí)雖然也調(diào)到了6點(diǎn)保檐，但是他實(shí)際上比原來日期多了12小時(shí)耕蝉。是的，的確如此夜只，但是你的時(shí)鐘有地方存儲了這多余的12個(gè)小時(shí)嗎垒在？答案是沒有，所以在你調(diào)完后扔亥，你沒有記錄這12個(gè)小時(shí)场躯，換句話說，你把這溢出的12個(gè)小時(shí)自動(dòng)舍棄了旅挤。當(dāng)?shù)诙€(gè)人來查看鬧鐘時(shí)間的時(shí)候踢关，他看到的時(shí)間就是準(zhǔn)的。
二進(jìn)制補(bǔ)碼表示負(fù)數(shù)是最方便的方式粘茄，它的便利體現(xiàn)在签舞，所有的加法運(yùn)算（加正數(shù)、加負(fù)數(shù)）可以使用同一種電路完成柒瓣。
我們以-8作為例子儒搭。
假定有兩種表示方法。一種是直覺表示法芙贫，即10001000搂鲫；另一種是2的補(bǔ)碼表示法，即11111000磺平。請問哪一種表示法在加法運(yùn)算中更方便魂仍？
隨便寫一個(gè)計(jì)算式，16 + (-8) = ?其中褪秀，16的二進(jìn)制表示是 00010000蓄诽，-8的二進(jìn)制表示是 10001000
- 直覺表示法：
⊙ρ怠０００１００００
＋１０００１０００
－－－－－－－－－
∶铰稹１００１１０００
可以看到，如果按照正常的加法規(guī)則乙埃，就會得到10011000的結(jié)果闸英，轉(zhuǎn)成十進(jìn)制就是-24。顯然介袜，這是錯(cuò)誤的答案甫何。也就是說，在這種情況下遇伞，正常的加法規(guī)則不適用于正數(shù)與負(fù)數(shù)的加法辙喂，因此必須制定兩套運(yùn)算規(guī)則，一套用于正數(shù)加正數(shù)，還有一套用于正數(shù)加負(fù)數(shù)巍耗。從電路上說秋麸，就是必須為加法運(yùn)算做兩種電路。
- 補(bǔ)碼表示法：
【嫣０００１００００
＋１１１１１０００
－－－－－－－－－
１００００１０００
可以看到灸蟆，按照正常的加法規(guī)則，得到的結(jié)果是100001000亲族。注意炒考，這是一個(gè)9位的二進(jìn)制數(shù)。我們已經(jīng)假定這是一臺8位機(jī)霎迫，因此最高的第9位是一個(gè)溢出位斋枢，會被自動(dòng)舍去。所以知给，結(jié)果就變成了00001000杏慰，轉(zhuǎn)成十進(jìn)制正好是8，也就是16 + (-8) 的正確答案炼鞠。這說明了缘滥，2的補(bǔ)碼表示法可以將加法運(yùn)算規(guī)則，擴(kuò)展到整個(gè)整數(shù)集谒主，從而用一套電路就可以實(shí)現(xiàn)全部整數(shù)的加法朝扼。
2. 按位運(yùn)算
以Python為例，常用位運(yùn)算符包括以下6中：
- 按位與 &
- 按位或 |
- 按位異或 ^
- 按位翻轉(zhuǎn) ~
- 左移運(yùn)算 <<
- 右移運(yùn)算 >>
2.1 按位與（&）
即按照對應(yīng)位置的二進(jìn)制進(jìn)行 and運(yùn)算霎肯，其中運(yùn)算規(guī)則為 1 & 1 = 1擎颖，1 & 0 = 0，0 & 1 = 0观游，0 & 0 = 0搂捧。
下面的 5 & 3示意如下:
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
& &&&&
3 --> 0000 0011
= ||||
1 <-- 0000 0001
- 位運(yùn)算判斷奇偶性
n&1 == 1 # 奇數(shù)返回1，偶數(shù)返回0
2.2 按位或（|）
即按照對應(yīng)位置的二進(jìn)制進(jìn)行 or運(yùn)算懂缕，其中的運(yùn)算規(guī)則為 1 | 1 = 1允跑，1 | 0 = 1，0 | 1 = 1搪柑，0 | 0 = 0
下面的 5 | 3示意如下:
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
| ||||
3 --> 0000 0011
= ||||
7 <-- 0000 0111
- 向上取奇數(shù)
map(lambda x:x|1, range(6)) # 結(jié)果為[1, 1, 3, 3, 5, 5]
2.3 按位異或（^）
即按照對應(yīng)位置的二進(jìn)制進(jìn)行 xor運(yùn)算聋丝，其中的運(yùn)算規(guī)則為 1 ^ 1 = 0，1 ^ 0 = 1工碾，0 ^ 1 = 1弱睦，0 ^ 0 = 0
下面的 5 ^ 3示意如下:
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
^ ^^^^
3 --> 0000 0011
= ||||
6 <-- 0000 0110
- 只出現(xiàn)一次的數(shù)字
reduce(lambda x,y: x^y, [1,1,3,2,4,3,4]) # 累積進(jìn)行異或運(yùn)算，找出只出現(xiàn)一次的數(shù)字為2渊额，出現(xiàn)兩次的數(shù)字就抵消掉了
2.4 按位翻轉(zhuǎn)（~）
即1變成0况木，0變成1垒拢。
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
~ ~~~~ ~~~~
-6<-- 1111 1010
翻轉(zhuǎn)相當(dāng)于跟 -1做異或運(yùn)算，即~n = n ^ (-1)
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
^ ^^^^
-1--> 1111 1111
= ||||
6 <-- 1111 1010
2.5 左移運(yùn)算（<<）
左移運(yùn)算是將二進(jìn)制數(shù)值整體向左邊移動(dòng)n個(gè)位置火惊，空出來的位置補(bǔ)0子库。
下面的 5 << 2示意如下:
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
<< << 2
20<-- 0001 0100
- 用于乘法計(jì)算
5 * 7
= (101 * 111)_2
= (101 * (100 + 10 + 1))_2
= (101 * 100 + 101 * 10 + 101 * 1)_2
= 5 << 2 + 5 << 1 + 5 << 0
= (10100 + 01010 + 00101)_2
= 20 + 10 + 5
= 35
2.6 右移運(yùn)算（>>）
左移運(yùn)算是將二進(jìn)制數(shù)值整體向右邊移動(dòng)n個(gè)位置，空出來的位置補(bǔ)上符號位的數(shù)值矗晃。即正數(shù)補(bǔ)0仑嗅，負(fù)數(shù)補(bǔ)1。
下面的 5 >> 2张症、-5 >> 2示意如下:
十進(jìn)制 二進(jìn)制
5 --> 0000 0101
>> >> 2
1 <-- 0000 0001
十進(jìn)制 二進(jìn)制
-5--> 1111 1011
>> >> 2
-1<-- 1111 1110
- 用于除法
5 / 3
= 5 >> 2
= (101 / 100)_2
= (001)_2
= 1
2.7 位運(yùn)算實(shí)現(xiàn)加減乘除
def add(num1, num2):
while num2 != 0:
temp = num1 ^ num2
num2 = (num1 & num2) << 1
num1 = temp
return min(max(-2147483648, num1), 2147483647)
def sub(num1, num2):
return add(num1, add(~num2, 1))
def mul(num1, num2):
sign = (num1 > 0) is (num2 > 0)
if num1 < 0:
num1 = add(~num1, 1)
if num2 < 0:
num2 = add(~num2, 1)
result = 0
while num2:
if num2 & 1:
result = add(result, num1)
num1 = num1 << 1
num2 = num2 >> 1
if not sign:
result = - result
return result
def div(num1, num2):
sign = (num1 > 0) is (num2 > 0)
if num1 < 0:
num1 = add(~num1, 1)
if num2 < 0:
num2 = add(~num2, 1)
result = 0
while (num1 >= num2):
tmp, i = num2, 1
n = 4
while(num1 >= tmp):
num1 -= tmp
result += i
tmp = tmp<<n
i = i << n
n = n >> 2
if not sign:
result = -result
return min(max(-2147483648, result), 2147483647)
在早期版本中仓技，如Python2.7，整數(shù)的有int和long兩個(gè)類型俗他。int類型是一個(gè)固定位數(shù)的數(shù)脖捻；long則是一個(gè)理論上可以存儲無限大數(shù)的數(shù)據(jù)類型。當(dāng)數(shù)大到可能溢出時(shí)兆衅，為了避免溢出地沮，Python會把int轉(zhuǎn)化為long。
而Python3.x之后整數(shù)只有一個(gè)可以放任意大數(shù)的int了羡亩∧σ桑可是無論哪種，都是采用了特殊的方法實(shí)現(xiàn)了不會溢出的大整數(shù)畏铆。
在進(jìn)行負(fù)數(shù)的按位加法時(shí)雷袋，有可能發(fā)生在最高位還要向前進(jìn)一位的情形，正常來說辞居，這種進(jìn)位因?yàn)槌隽艘粋€(gè)int可以表示的最大位數(shù)楷怒，應(yīng)該舍去才能得到正確的結(jié)果。但在Python中因?yàn)樯鲜鲈驎a(chǎn)生一個(gè)不會溢出的大整數(shù)瓦灶，所以在進(jìn)行負(fù)數(shù)的按位加法時(shí)鸠删，結(jié)果會不斷變大。
這個(gè)問題在 Java贼陶、C刃泡、C++ 中不會存在，這也是Python效率低的一個(gè)原因每界。
