本文知识点针对《计算机科学导论》中的“Fixed-size computation”（定长计算）。强调在计算机中的算术运算是mod运算，并归纳其运算规则。

当我们学习某种理论体系的时候，往往从它的弱点开始。计算机的弱点是什么？

也许我们首先要知道，计算机所有的计算都是有限计算，这非常重要。什么是有限计算？我们现在只知道二进制是0/1比特串，可以进行加法和乘法（上次我们已经从乘二中得到了任意的乘法）。那么有限就体现在，计算机只能做有限比特的加法和乘法？这似乎有悖于我们对计算机对认识，计算机不是连围棋高手都打败了吗？是的，无论它表现得似乎无所不能，本质上，它只是做有限比特的加法与乘法。

好吧，那么有限到什么程度？也许有些计算机只能做8比特的运算，有些能做16比特或者32比特，而你们现在购买的64位机就是做64比特的运算而已。是不是有点为自己那几大千RMB感到遗憾？请大家要明白，你买32位机或者64位机，其实是说你的cpu在执行一次运算时候能做多少比特的运算。

几个概念：

8比特为一个byte（字节）。
C语言中的Byte类型就是8个比特的数据类型。
C语言中的char类型是8比特的字符类型。
*注意：都是8比特，有什么区别吗？*
C语言中的int类型是表示整数类型，32比特，即4个字节。

直观上，给定任意一个变量，我们可以把它看成能装n个比特的“盒子”，比如一个byte变量就是可以装8个比特的盒子。

那么，比如把37（16进制）装进盒子里，就得到：

0 0 1 1 0 1 1 1

请注意开头的3个0，这里必须写，因为我们需要把8个比特写出来。大家计算这个16进制数等于10进制的几？对它乘2等于在末尾补零，对这种形象化的说法，我们可以有更直观的认识，即把比特值向左移动一个比特位，得到：

0 1 1 0 1 1 1 0

除2等于向右移动一个比特位，在左边补零，得到：

0 0 0 1 1 0 1 1 

这些规则都是在第一章中已经归纳出来的内容，这里只是在有限计算的框架下重新陈述。同样，我们还可以重新理解这里的加法与乘法。

我们怎么再认识计算机的有限计算呢？比如，对于加法，我们可以这样玩一下：

byte a = 255, b = 2;
a = a + b;
printf("a ＝＝ %d", a);

比如，对于乘法，我们这样编程尝试一下嘛：

int n = 16; #你们可以尝试不同的数值；
byte a = 1；#或者尝试一下int类型；我不会告诉你们什么unsigned的！
for(int i = 1; i < = n; i++){
    a = a*2；
    printf("我这里偷个懒，你们直接输出a的值嘛，%d", a)；
｝

当n等于什么的时候a的值会出现异常？这种异常代表什么？如果a的初始值为任意数，比如3，或者5，又会如何？

通过尝试，也许我们会发现，其实，这里的所谓加法或者乘法，只是一种mod运算，mod什么？mod的是2的某个次方，比如int类型，mod 2^32（2的32次方）。byte类型mod什么？请一定要设置特定数值进行尝试一下。

这里也许需要解释一下，经典书籍当中所谓的“溢出”。这里没有什么溢出，只是mod运算。

好了，现在我们需要了解一下mod运算的好处了。运算规则如下，希望你们中学的时候学过：

(a + b) mod n ＝＝( (a mod n) + (b mod n)) mod n
(a * b) mod n ＝＝( (a mod n) * (b mod n)) mod n

作业：请证明以上两条规则。

这个时候，你们之前写的代码就可以这样玩一下了。如果写了factorial，不妨看看，当n变得很大时候会怎么样？比如n＝100，1000，10000......可以看到，其实mod 2^n并不好玩！（非常可惜对于我提示的这些计算，很少有同学会自觉去编程玩一下！）怎么样才好玩？我们会回来的。不过，现在我们还是先停顿一下。

之前有不少同学已经迫不及待地问到八进制，16进制。其实，这并不是很特殊到东西。如果我们把比特三位为一组去认识，就得到八进制，四位为一组去认识就得到16进制。比如：

000 ，001，...，110， 111，这里有多少个数？2的3次方，8个。
111 + 1 == ?，1000 ？对不起，我们只有3个比特，所以是0！即，逢八进一。

同样，0000到1111，有16个数，逢16进一，是16进制。

这里要注意，1010，1011，到1111，这几个数还没有名字，所以，起名为A，B，...，F。 没有什么特别！对吧？

16进制的命名：

 1000  为 8；  1001  为 9   #老名字，以下是新名字
 1010  为 A；  1011  为 B
 1100  为 C；  1101  为 D
 1110  为 E；  1111  为 F

为什么我们需要8进制，16进制，而不是3进制，5进制？哪种进制的效率最高？

给定变量的长度我们就能立即知道这个变量所能表示数据的范围，反之，给定一个数字，我们能知道这个数值需要用多长的比特变量来表达。

例子：

8比特变量能表达的范围是：00 ~ FF，256个数值；
16比特能表达的范围是：0000 ~ FFFF，65536个数值；

例子：

 表达234这个十进制值需要 8 个比特；
 表达4294967295这个十进制值需要32个比特；

这里的一个观点是，长度n能表达的最大范围是2^n；而某个数x需要n比特进行表达，则是n ＝＝ log x （以2为底的对数）。这里的指数与对数的对应关系值得注意！

2017-06-29整理