本文知識點針對《計算機科學(xué)導(dǎo)論》中的“Fixed-size computation”（定長計算）。強調(diào)在計算機中的算術(shù)運算是mod運算蛋欣，并歸納其運算規(guī)則础锐。
當我們學(xué)習(xí)某種理論體系的時候瞭郑，往往從它的弱點開始胳徽。計算機的弱點是什么？
也許我們首先要知道灭美，計算機所有的計算都是有限計算稿械，這非常重要。什么是有限計算冲粤？我們現(xiàn)在只知道二進制是0/1比特串美莫，可以進行加法和乘法（上次我們已經(jīng)從乘二中得到了任意的乘法）。那么有限就體現(xiàn)在梯捕，計算機只能做有限比特的加法和乘法厢呵？這似乎有悖于我們對計算機對認識，計算機不是連圍棋高手都打敗了嗎傀顾？是的襟铭，無論它表現(xiàn)得似乎無所不能，本質(zhì)上短曾，它只是做有限比特的加法與乘法寒砖。
好吧，那么有限到什么程度嫉拐？也許有些計算機只能做8比特的運算哩都，有些能做16比特或者32比特，而你們現(xiàn)在購買的64位機就是做64比特的運算而已婉徘。是不是有點為自己那幾大千RMB感到遺憾漠嵌？請大家要明白咐汞，你買32位機或者64位機，其實是說你的cpu在執(zhí)行一次運算時候能做多少比特的運算儒鹿。
幾個概念：
8比特為一個byte（字節(jié)）化撕。
C語言中的Byte類型就是8個比特的數(shù)據(jù)類型。
C語言中的char類型是8比特的字符類型约炎。
*注意：都是8比特植阴，有什么區(qū)別嗎？*
C語言中的int類型是表示整數(shù)類型圾浅，32比特掠手，即4個字節(jié)。
直觀上贱傀，給定任意一個變量，我們可以把它看成能裝n個比特的“盒子”伊脓，比如一個byte變量就是可以裝8個比特的盒子府寒。
那么，比如把37（16進制）裝進盒子里报腔，就得到：
0 0 1 1 0 1 1 1
請注意開頭的3個0株搔，這里必須寫，因為我們需要把8個比特寫出來纯蛾。大家計算這個16進制數(shù)等于10進制的幾纤房？對它乘2等于在末尾補零，對這種形象化的說法翻诉，我們可以有更直觀的認識炮姨，即把比特值向左移動一個比特位，得到：
0 1 1 0 1 1 1 0
除2等于向右移動一個比特位碰煌，在左邊補零舒岸，得到：
0 0 0 1 1 0 1 1
這些規(guī)則都是在第一章中已經(jīng)歸納出來的內(nèi)容，這里只是在有限計算的框架下重新陳述芦圾。同樣蛾派，我們還可以重新理解這里的加法與乘法。
我們怎么再認識計算機的有限計算呢个少？比如洪乍，對于加法，我們可以這樣玩一下：
byte a = 255, b = 2;
a = a + b;
printf("a ＝＝ %d", a);
比如夜焦，對于乘法壳澳，我們這樣編程嘗試一下嘛：
int n = 16; #你們可以嘗試不同的數(shù)值；
byte a = 1茫经；#或者嘗試一下int類型钾埂；我不會告訴你們什么unsigned的河闰！
for(int i = 1; i < = n; i++){
a = a*2；
printf("我這里偷個懶褥紫，你們直接輸出a的值嘛姜性，%d", a)；
｝
當n等于什么的時候a的值會出現(xiàn)異常髓考？這種異常代表什么部念？如果a的初始值為任意數(shù)，比如3氨菇，或者5儡炼，又會如何？
通過嘗試查蓉，也許我們會發(fā)現(xiàn)乌询，其實，這里的所謂加法或者乘法豌研，只是一種mod運算妹田，mod什么？mod的是2的某個次方鹃共，比如int類型鬼佣，mod 2^32（2的32次方）。byte類型mod什么霜浴？請一定要設(shè)置特定數(shù)值進行嘗試一下晶衷。
這里也許需要解釋一下，經(jīng)典書籍當中所謂的“溢出”阴孟。這里沒有什么溢出晌纫，只是mod運算。
好了永丝，現(xiàn)在我們需要了解一下mod運算的好處了缸匪。運算規(guī)則如下，希望你們中學(xué)的時候?qū)W過：
(a + b) mod n ＝＝( (a mod n) + (b mod n)) mod n
(a * b) mod n ＝＝( (a mod n) * (b mod n)) mod n
作業(yè)：請證明以上兩條規(guī)則类溢。
這個時候凌蔬，你們之前寫的代碼就可以這樣玩一下了。如果寫了factorial闯冷，不妨看看砂心，當n變得很大時候會怎么樣？比如n＝100蛇耀，1000辩诞，10000......可以看到，其實mod 2^n并不好玩！（非诚苄ぃ可惜對于我提示的這些計算，很少有同學(xué)會自覺去編程玩一下＝嵋）怎么樣才好玩外永？我們會回來的崎脉。不過，現(xiàn)在我們還是先停頓一下伯顶。
之前有不少同學(xué)已經(jīng)迫不及待地問到八進制囚灼，16進制。其實祭衩，這并不是很特殊到東西灶体。如果我們把比特三位為一組去認識，就得到八進制掐暮，四位為一組去認識就得到16進制蝎抽。比如：
000 ，001路克，...樟结，110， 111衷戈，這里有多少個數(shù)狭吼？2的3次方层坠，8個殖妇。
111 + 1 == ?，1000 破花？對不起谦趣，我們只有3個比特，所以是0座每！即前鹅，逢八進一。
同樣峭梳，0000到1111舰绘，有16個數(shù)，逢16進一葱椭，是16進制捂寿。
這里要注意，1010孵运，1011秦陋，到1111，這幾個數(shù)還沒有名字治笨，所以驳概，起名為A赤嚼，B，...顺又，F(xiàn)更卒。 沒有什么特別！對吧待榔？
16進制的命名：
1000 為 8逞壁； 1001 為 9 #老名字，以下是新名字
1010 為 A锐锣； 1011 為 B
1100 為 C腌闯； 1101 為 D
1110 為 E； 1111 為 F
為什么我們需要8進制雕憔，16進制姿骏，而不是3進制，5進制斤彼？哪種進制的效率最高分瘦？
給定變量的長度我們就能立即知道這個變量所能表示數(shù)據(jù)的范圍，反之琉苇，給定一個數(shù)字嘲玫，我們能知道這個數(shù)值需要用多長的比特變量來表達。
例子：
8比特變量能表達的范圍是：00 ~ FF并扇，256個數(shù)值去团；
16比特能表達的范圍是：0000 ~ FFFF，65536個數(shù)值穷蛹；
例子：
表達234這個十進制值需要 8 個比特土陪；
表達4294967295這個十進制值需要32個比特；
這里的一個觀點是肴熏，長度n能表達的最大范圍是2^n鬼雀；而某個數(shù)x需要n比特進行表達，則是n ＝＝ log x （以2為底的對數(shù)）蛙吏。這里的指數(shù)與對數(shù)的對應(yīng)關(guān)系值得注意源哩！
2017-06-29整理
