从1加到100：一道简单的数学题挑战下你的大脑
原创： 刘欣
码农翻身2017-01-03
2017年的第一篇， 写给刚刚踏入计算机编程领域的小白吧。
所谓编程，就是把自然语言的需求翻译成计算机语言， 让计算机去执行。 对于刚入行的人， 理解CPU和内存是怎么在一起工作的， 绝对是基础中的基础。
1
CPU和内存
如果我们简化一下， CPU和内存其实特别简单，内存就是一个个的小格子， 每个格子都有一个编号， 格子中的数据可以被CPU所读写。
CPU 内部的构造超级复杂， 但我们这次只关注两个东西：
一是运算器，可以做各种运算， 但是有个限制，这个运算器不能直接操作内存进行运算， 他在运算时使用的是内部的数据格子（学名叫寄存器）， 为了区分开， 我把他们叫做R1,R2,R3,R4,假设只有这么4个， 统称Rx。
CPU必须把数据装载到寄存器中才能运算。
CPU运行速度快的令人发指， 但是它能做的事情却简单的令人发指， 主要是以下四种：
(1) 从内存的某个格子中读取数据放入自己内部的寄存器Rx
(2) 把Rx的数据写入内存的某个格子中（会把原有数据覆盖）
(3) 进行数学运算和逻辑运算
(4) 根据条件进行跳转
数学运算就是加减乘除， 逻辑运算就是AND , OR 这样的基本运算，没接触过的暂时可以不用深究。
根据条件进行跳转就是从一个指令跳转到另外一个指令， 下文会详述。
2
从1加到100
现在我们试图用一个例子来揭开CPU和内存的神秘面纱， 这个例子就是把1， 2， 3， 4，..... 97, 98, 99, 100 这100个数字加起来 。
如果你看过数学王子高斯小时候的故事， 自然很简单，不就是 101 * 50 = 5050 吗 ？
作为码农， 我们需要用上面的简化计算机来解决这个问题： 我们需要精确的告诉CPU来指令， 让它去完成这个加法运算。
切记切记： 内存只是一个个可以读写的格子， CPU简单到只能做上面描述的4件事。
3
热身
在正式开始之前，我们先来热一下身，把你的思维切换一下， 用这个“简陋的”计算机计算一下 50 + 60 ， 我门需要告诉CPU这些指令：
指令1 ： 把数字50 放到编号为 #1 的格子里
指令2 ： 把数字60 放到编号为 #2 的格子里
指令3 ： 把格子#1的数字取出来，暂时放到CPU内部的寄存器R1中
指令4 ：把格子#2的数字取出来， 暂时放到CPU内部的寄存器R2中
指令5 ：把R1和R2的值相加， 结果放到R1中
指令6 ：把R1的结果放到编号为 #1的内存格子里。
真是不容易啊， 因为CPU不能直接操作内存进行加法操作， 需要把数据从内存和CPU之间搬来搬去， 最后才完成了这么一个简单的运算。
4
正式出发
热身完毕，正式出发 ！
回到那个从1加到100的题目， 我们的指令如下所示，CPU需要依次执行（除非遇到跳转指令）， 直到结束：
指令1 ： 把数字0 放到 编号为 #1 的格子里
指令2 ： 把数字1 放到 编号为 #2 的格子里
指令3 ： 把#1号格子的数取出放入CPU寄存器R1 （即 R1的初始值为0）
指令4 ： 把#2号格子的数取出放入CPU寄存器R2 （即 R2 的初始值为1）
指令5 ： 把R2的值和100 比较， 如果小于等于100，执行第6个指令， 否则执行第9个指令
指令6 ： 把R1和R2的数据加起来， 结果放入R1
指令7 ： 把R2的数值加1
指令8： 跳转到第5个指令
指令9： 把R1的值写回到 编号为 #1的格子里
(注：#1号格子的值就是结果)
这里提示一下： R2表示的就是从1到100这些数字， R1存放的就是中间和。
现在，请你在脑子里边模拟一下这个过程， 看看程序能不能成功结束， 把最终结果放到#1号格子里。
如果觉得脑子不够用， 建议拿一个纸和笔， 把自己当成CPU， 把上面的这些指令手工的执行一遍， 体会一下这个过程。
如果你是非科班出身，并且能迅速的理解上面这些指令是如何完成从1到100的加法的， 恭喜你， 你很适合学习编程， 光明的前途在前面向你招手。
我们上面所说的指令和汇编非常相似， 这是一种非常贴近机器， 非常“低级”的计算机语言。
用这种语言来编写大型程序，会把人活活累死。
当然话也不能那么绝对， 对于那些大神级别的程序员来说， 汇编也是小菜一碟。 Ken Thompson 和 Dennis Ritchie 不就用汇编写了第一版的Unix操作系统吗？ 求伯君不就用汇编写了WPS吗？
对于普通人来说，大神们给我们创造了高级语言让我们使用， 如果我们用高级语言把上面的例子再写一遍， 你应该很容易能看明白了：
不要被之前的“低级”指令吓住， 这才是码农每天打交道的代码，不过这种高级语言写的代码最终也要被编译成“低级”语言代码， 最终交由CPU来执行， 编译后的机器语言，其实和上面的指令差不多。
5
思考
为什么要拿这个例子来挑战小白的大脑呢？ 从本质上来说， 码农整天做的就是这样的事情， 告诉计算机使用这些指令去运算， 我们需要养成面向计算机的思维方式。
CPU能干的事情非常有限，笼统来说就是上面那四种， 但是我们现在上网、听歌、看视频、玩游戏，最终都会归结到这些操作中来， 这就是计算的本质。
此外， CPU是如此的冷酷， 以至于你的指令出一点点错误就不给你正确结果， 例如你把第3个指令中的“如果小于等于100”， 不小心写成了“如果小于100”，
CPU当然不会告诉你程序中有问题，他只会冷冷的执行， 最后你会发现：这结果怎么不对呢？
还有一个问题，CPU在运行的时候，从哪里取获得那些指令？
估计你已经想到了， 对，就是内存 ，指令也需要在内存中才能够被CPU访问到， CPU从内存读到指令以后，会进行分析（译码） ， 看看这个指令是干什么的， 然后再进行运算。
所以我们的内存小格子中不仅仅存放的是数据，还存放着至关重要的程序指令！ 我们需要告诉CPU第一条指令在什么地方， 然后CPU就可以疯狂的开始运行了：
这些指令在内存中肯定不是我们看到的自然语言， 而是二进制的表示。
那内存的数据又是从哪里来的？ 肯定是硬盘了， 我们写好的程序会放在硬盘上， 在运行的时候才调入内存。
张大胖的加法器
2016-12-28
加法器
热爱编程的张大胖在大学时最烦的一门课之一就是《数字电路》 ， 他一直觉得和编程没什么关系。
有一次课程设计是实现一个加法器， 大胖使用逻辑电路， 费了九牛二虎之力才实现了4位的加法。
这4个二进制位能表达的数有16个， 从0 到15 ：
大胖用他的加法器计算了一下 8+3 ：
8+3 = 1000 + 0011 = 1011 = 11
还不错， 再计算一下 9+7 ：
9+8 = 1001 + 1000= 0001
怎么变成了1 ？ 奥， 我这儿只有4位，能支持的最大数字就是 15 ， 而9+8的结果是 10001 （十进制16），计算结果溢出， 最高位的1被丢弃了！
其实这也符合要求， 大胖顺利的交了作业。
用加法来表示减法
可是下一次课还是课程设计， 老师竟然要求在这个加法器上实现减法 ， 这可把大胖给难住了， 在加法器上实现减法， 真是个变态的需求。
遇到了问题， 张大胖自然会“跪求”好基友， 电脑高手Bill。
Bill 说： “这个要求一点都不变态，用加法器同时实现加法和减法， 能极大的节省CPU的电路设计。 ”
“你就说该怎么实现吧”
Bill说：“我先给你说一下原理， 在你定义的4位二进制中，一共可以表达16个数， 我们引入一个‘补数 '的概念， 例如 3的补数 是 13， 4的补数是12， 5 的补数是11， 当你计算7减去3 的时候， 可以变成 7加上3 的补数， 即 7 + 13 ”
“可是7+13 是20 ， 但是7-3 等于4 啊”
“20其实已经超出你4位二进制能表达的16个数了， 已经溢出了，对吧， 所以20还得减去16 ， 就是4 了。 你用二进制算一下。”
7-3 = 0111- 0011 = 0111 + 1101（二进制13） = 10100
10101已经溢出了， 去掉最高位是 0100 ，就是十进制4 了。
“果然不错” 张大胖说 “这让我想到了钟表， 现在是7点， 我想让它回到4点， 有两种办法， 一种方法是让时针后退 3 格， 另外一种方法是让时针前进9格， 前进到12点的时候， 其实就相当于溢出了， 舍弃掉。 "
Bill 说， "看来你已经Get了， 数学上有个词叫做求模， 说的就是这个运算， 还以时钟为例"
向后退3格： 7 - 3 = 4
向前进9格 ： (7 + 9) mod 12 = 4
向前进21格： (7+9+12) mod 12 = 4
向前进33格： (7+9+12+12) mod 12 = 4
.....
“这是一种以进为退的策略” Bill 接着说 " 用这种办法就把减法变成了加法"
“但是我怎么得到所谓的补数呢？ 从3 怎么得到13 呢”
“这很简单， 对于二进制， 前辈们想出了一个异常简单， 又特别适合计算机的算法， 对二进制数的所有位取反， 然后加1 ”
“神奇啊， 前辈们竟能想出这么巧妙的办法 ！”
“这就是所谓的补码了” Bill总结道
负数的表示
Bill 问道： “刚才咱们说的都是整数的加减法， 负数你考虑了没有啊？ 大胖？”
“我也刚刚想到， 现在我知道 7-3 可以换算成 7+ 13 了， 如果是3 - 7 呢？ ”
“负数一引入， 系统就变得更复杂了， 首先你得用一个标志位来表示整数还是负数吧： ”
（表格1）
张大胖说： “明白了， 最高位的0 表示正数， 1 表示负数， 真正有效的数字只剩下3位了， 正数的范围是从1 到7 ， 负数的范围从 -1到-7 ， 不过这里出现了两个零！ 一个正0 ， 一个负0 ， 这不妥吧。”
“先别急， 之前说到减法可以变成加法， 秘密就是用补码， 例如8-3 相当于8+(-3)的补码 ， 那我们完全可以把表格1中的负数用补码表示， 然后把那个负0 特别当做 -8来处理： ”
Bill 接着说： “按照上面的表格， 现在我们来计算一下 7-4 , 7是 0111， -4是 1100， 注意我们把符号位也算进去了， 两者相加：
“让我试试4-7, ” 张大胖说， 4是0100 ， -7是1001， 两者相加：
“妙啊” 张大胖不禁赞叹起来， “把负数用补码表示，不但减法变加法， 连符号位都可以参与运算了！”
“ 是啊， 我们通过补码能极大的简化电路的设计， 你一定要记住， 在计算机内部，是使用补码来表示二进制数， 如果是一个正数， 补码就是它本身， 如果是个负数， 需要把除了符号位之外的二进制数进行取反加一的操作"
"此外， 我想你也能总结出来， 你这个4位的系统如果只表示无符号数(没有负数的话) ， 它的范围是[0 , 2 ^ 4] ，即[0, 16] ；
如果要想表达有符号数(负数和整数)， 它的范围就是[-2^3, 2^3-1] , 即[-8, 7] 。 在高级编程语言像C, Java ，你经常会看数据类型的取值范围， 你应该明白其中的原理了。 ”
（完）
一个翻译家族的发家史
原创： 老刘
2017-03-29
我是编程语言翻译家族的一员， 我们这个家族最重要的工作就是将一个语言描述的源程序翻译成另外一种语言描述的目标程序, 听起来有些抽象， 通俗一点就是把你们码农写的源码变成可以执行的程序。
我们这个家族可以说是伴随这计算机的发展而不断发展壮大的， 现在已经成为计算机软件系统不可缺少的一部分， 如果回顾一下发家史， 还是挺有趣的。
1机器语言
我听说计算机刚发明那会儿， 人们就是拨弄各种开关、操作各种电缆把程序给“输入”到计算机中去。
这所谓的程序， 可真的是0110000111这样的二进制， 我真是佩服这些程序的设计者和操作员们， 太不可思议了。
这种原始的方式也决定了难于诞生超大型程序， 因为太复杂了，远远能过人脑能思考的极限。
后来人们做了点改进， 把程序打到穿孔纸带上， 让机器直接读穿孔纸带， 这下子就好多了， 终于不用拨弄开关了。
但程序的本质还是没有变化， 依然是在使用二进制来编程。
如果这个样子一直持续下去， 估计这个世界上的程序员会少的可怜： 编程的门槛太高了。
比如说你的脑子里得记住这样的指令：
0000 表示从内存中往CPU寄存器装载数据
0001 表示把CPU寄存器的值写入内存
0010 表示把两个寄存器的值相加
你还得记住每个寄存器的二进制表示：
1000 表示寄存器A
1001 表示寄存器B
综合起来就像这样：
0000 1000 000000000001 它的意思是说， 把编号为1的内存中的值装载到寄存器A当中
0010 1000 1001 的意思是把寄存器A和寄存器B的值加起来，放到寄存器A中。
整天生活在这样的世界里， 满脑子都是0和1， 要是我估计就抑郁了。
当时的程序员像熊猫一样稀少， 不， 肯定比熊猫更少， 他们都要二进制写程序， 对我们翻译家族没有任何的需求。
2 汇编语言
既然二进制这么难记， 人们很快就想到： 能不能给这些指令起个好听的名称呢？
0000 ： LOAD
0001 : STORE
0010 : ADD
寄存器也是一样的：
1000 : AX
1001 : BX
这下读来容易多了：
ADD AX BX
人们给这些帮助记忆的助记符起了个名字： 汇编语言。
但是计算机是无法执行汇编语言的， 因为计算机这个笨家伙只认二进制， 所以还得翻译一下才行。
于是我们家族的一个重要成员： 汇编器 隆重登场了， 他专门负责汇编语言写的程序翻译为机器语言， 这个翻译的过程比较简单，几乎就是一一对应的关系。
汇编语言解放了人们的部分脑力， 可以把更多的精力集中在程序逻辑上了。 越来越多的人学会了使用汇编来编程， 写出了很多伟大的软件。
汇编的优点是贴近机器， 运行效率极高， 但是缺点也是太贴近机器， 直接操作内存和CPU寄存器， 不能结构化编程， 每次函数调用还得把手动把栈帧给管理好， 这对于一般的程序员来讲太难了！
我的祖先们把穿孔纸带和汇编语言都称为低级语言， 把这个时代称为机器语言编程时代。
生活在这个时代的祖先们是很幸福的， 因为翻译工作十分简单。
但是用汇编写程序的人还是太少， 找我们做翻译的也很少， 翻译家族也只是温饱而已。
3高级语言
人类的欲望是无止境的， 他们一直在探索用一种更高级的语言来写程序的可能性， 这种高级语言应该面向人类编写和阅读， 而不是面向机器去执行。
人类想要的高级语言是这样的：
声明各种类型的变量来表示数据，而不是用寄存器。 例如 :
int value = 100
能使用复杂的表达式来告诉电脑自己的意图：
salary = 1000 + salary * 12
可以用各种控制语句来控制流程：
if .. else , while(....) ....
还可以定义函数来封装、复用一段业务逻辑：
int get_primes(int max) {.....}
但是高级语言和低级语言之间存在着巨大的鸿沟， 怎么把高级语言翻译成可以执行的机器语言是个非常难的问题！
人类在黑暗中摸索了很久，这才迎来一丝光明， 1957年，第一个高级语言的编译器才在IBM704的机器上运行成功。 更重要的是乔姆斯基对自然语言结构的研究， 把语言文法做了分类，有了0型文法，1型文法， 2型文法，3型文法， 这一下子给我们的翻译工作奠定了理论基础。
由于翻译的复杂性， 除了汇编器之外， 很多新成员加入进来， 我们的家族迅速发展壮大， 甚至形成了一个专门翻译的流水线， 这个流水线的家族成员分工合作， 把高级语言翻译成低级语言。
我主要做的工作就是第一步词法分析， 大家经常给我开玩笑说： 你这是大刀向源程序头上砍去。
这其实挺形象的，比如高级语言的源程序是这样：
total = 1000 + salary * 12
我拿着“大刀”， 唰唰唰把他们砍成一个个的片段， 每个片段叫做Token。
1. 标识符 total
2. 赋值符号 =
3. 数字 1000
4. 加号 +
5. 标识符 salary
6. 乘号 *
7. 数字12
程序中的空格就被我无情的删除了， 我还会建立一个符号表让后面的人去使用：
接下来我二叔就会接管， 他非常厉害， 会做语法分析，据说他用了一个叫什么上下文无关语法的理论， 竟然能把我生成的Token 按照语法规则组建成一棵树
然后三舅就做语法分析， 他会看看这些标志符的类型，作用域是不是正确，运算是否合法， 取值范围有没有问题等等。
我大舅的工作最重要， 把中间代码生成， 代码优化，以及最后的代码生成都给承包了。
比如大舅根据语法树生成的中间代码如下：
temp1 = id2 * 12
temp2 = 1000 + temp1
id1 = temp2
(注意：id2 就是salary, id1 就是 total)
然后他再优化一下：
id1 = 1000 + temp1
然后翻译成汇编：
MOV id2 AX
MUL 12 AX
ADD 1000 AX
MOV AX id1
已经非常接近运行了！
但是等等， 这id1 （total）, id2 (salary) 只是两个符号， 计算机根本不知道是什么东西， 计算机只关心内存和寄存器， 所以还得给这两个家伙分配空间， 得到他们的地址。
如果这两个变量是在别的文件中定义的， 还需要做一件特别的事情： 链接！
通过链接的方式，把变量的真正地址获取到， 然后修改上面的id1, id2, 这样才能形成一个可以执行的程序。
在翻译的过程中，如果有任何步骤出了错误， 我们就会通知程序员， 告诉他哪个地方写错了， 改正后重新再来。
这就是我们家族的工作， 非常重要，没有我们的翻译工作， 人类就无法使用高级语言来编程， 像C, C++,Pascal, C#, Java 这样影响力巨大的语言就不会出现， 现在的软件编程行业也不会这么兴旺发达。
我们家族和操作系统、数据库、网络协议栈等软件一起，成为了计算机世界底层的基础软件。
其实我们都明白，现在所谓的高级语言一点也不高级，只有经过训练的专业人士才能使用 ， 也许在未来会出现完全用自然语言来写程序， 到那个时候我们家族会是什么样子？ 估计只有上天才知道了。
张大胖学递归
2016-11-14
张大胖上数据结构课， 老师讲汉诺塔问题， 使用了递归算法。
张大胖第一次接触递归， 一头雾水，想破了脑袋也没搞明白这递归是怎么回事， 他 一直很纳闷， 这么复杂的问题， 怎么可能就那么两三行代码就解决了？ 这怎么可能？
后来经好基友Bill指点， 总算明白一点， 但总是觉得还有点疑虑，不太敢确信自己是不是真的搞明白了。
Bill说： “给你来个简单点儿的例子，计算n的阶乘， 这个描述起来更直接”
Bill一边说，一遍写下了下面的代码：
“看看， 是不是特别简单， 所谓递归，就是一个函数调用了自己而已！”
“一个调用自己的函数， 这听起来就有点匪夷所思了” 张大胖感慨到。
“其实没那么复杂， 你就假想着调用了另外一个函数， 只不过这个函数的代码和上一个一模一样而已。”
“我们人不会这么做事情， 但是这是个程序， 它在机器层面到底是怎么执行的？ ” 张大胖问道。
Bill 说 “ 我给你画个图， 一个程序在内存中逻辑上看起来像这个样子”
“就拿我们的阶乘函数来说吧， 编译后会被放到代码段， 注意， 只有一套代码放在代码段。 ”
张大胖说： “只有一套代码， 那怎么实现自己调用自己的所谓递归啊？ ”
Bill说：“注意看堆栈中的栈帧啊， 每个栈帧就代表了被调用中的一个函数， 这些函数栈帧以先进后出的方式排列起来，就形成了一个栈， 拿放大镜栈帧放大来看就是这样：”
（码农翻身注： 返回值有时候用寄存器传递， 这里是为了展示阶乘的例子，特意把返回值画上了）
"如果我们忽略到其他内容， 只关注输入参数和返回值的话， 我们的阶乘函数factorial（4）会是这样" Bill接着又画了起来。
（码农翻身注： 栈顶在下边）
张大胖说：“明白了， 原来计算机是这么处理函数调用的啊，在计算factorial(4)的时候， 方法是4 *factorial(3) ， 现在4的值有了， 但是factorial(3) 的值还不知道是多少， 所以就需要形成新的栈帧来计算， 而factorial(3) 需要 factorial(2)， factorial(2) 需要 factorial(1)， 如果循环， 不， 是递归下去， 到最后才能得到 factorial(1) = 1， 然后每个栈帧逐次出栈， 就能计算出最终的factorial(4)了”
(点击看大图)
"注意， 每个递归函数必须得有个终止条件， 要不然就会发生无限递归了， 永远都出不来了。"
张大胖又问 ：”这个堆栈容量也是有限的吧， 如果n的值太大了， 是不是有可能爆掉？“
“是啊，每个栈帧都需要占用空间， 维护这些栈也挺费劲， 递归层次太深就会出问题。 ”
“那怎么办？ 这种函数的调用关系，好像只能这样了。 ”
“这是由我们的算法决定的， factorial(n) = n * factorial(n-1 ) , 所以之前的图中每个栈帧都需要记录下当前的n 的值， 还要记录下一个函数栈帧的返回值， 然后才能运算出当前栈帧的结果。 也就是说使用多个栈帧是不可避免的。 不过我们改下递归算法就有救了”
"这个方法看起来有点古怪啊， 还多传递了一个参数过来"
Bill说： ”不仅仅多了一个参数， 注意函数的最后一个语句， 就不是 n * factorial(n-1) 了， 而是直接调用factorial(....) 这个函数本身， 这就带来了巨大的好处。 ”
张大胖说：“不懂”
“你看看这个新算法的计算过程：”
“当你执行到factorial(1, 24)的时候， 还需要退回到factorial(2, xxx)这个函数吗？”
张大胖说：“看来不需要， 直接就可以返回结果了。”
“这就是妙处所在了， 计算机发现这种情况， 只用一个栈帧就可以搞定这些计算， 无论你的n 有多大。”
大胖感慨到： “果然是， 同一个栈帧，完全可以在递归中被复用啊， n 无论多大都不怕了。 ”
“这种方式就是我们常说的尾递归了， 当递归调用是函数体中最后执行的语句并且它的返回值不属于表达式一部分时， 这个递归就是尾递归。
现代的编译器就会发现这个特点， 生成优化的代码， 复用栈帧。 第一个算法中因为有个n * factorial(n-1) , 虽然也是递归， 但是递归的结果处于一个表达式中， 还要做计算， 所以就没法复用栈帧了， 只能一层一层的调用下去。 ”
“看来理解了计算机机器层面的东西才能更好的理解啊”
“没错， 计算机的基础非常重要。”