@bintou
2019-09-24T12:08:52.000000Z
字数 3764
阅读 1640
CSI
二进制
本文为非常规的《计算机科学导论》课程讲义,适用于大一新生。初学者可能会觉得有点难。最好是不要畏难,跟上思路。相信没有那么难。--斌头老师
从计算机科学的本质开讲。学“计算机科学”到底是学什么?本质上,Computer Science不是学计算机,不是学计算机的使用也不是学计算机的制造。学的是“计算”-- Computation。
通常,大家进入这个专业多数是因误解而来,从今天开始,也许需要换一下思维了。这也就是我为什么一直推荐How to Think like a Computer Scientist(HTCS)而不是其他比如C++ Primer之类的书为入门书的原因。关键不在于是否学会编程,而是要如何改变思维。
那到底什么是计算?这个问题很复杂,然后具体落实到计算机的实现上却又非常简单。这是两个问题。第一,什么是计算?这个暂时还回答不了。第二是,怎么计算。这个可以有一个简单的初始到答案:二进制。
“世界上有10种人,一种懂二进制,一种不懂!”你们是其中的第一种。改变思维的第一步,就是认识二进制。
注:本章内容并不涉及负数,即统统考虑无符号数。
首先我们给出二进制数字的描述。
二进制:只有0和1两位数字,每一位我们称为一个bit(比特)。
计算规则:0+0 = 0,0+1 = 1,1+1 = 10,10+1 = 11
现在可以归纳一下规律了。
0,1,10,11,...,1111,..., 这样的数字有没有遍历完所有的我们之前认识的十进制正整数?答案是,yes!然后,我们还知道,二进制加法无非就是“逢二进一”。
十进制数无非就是偶数和奇数两种。请问,偶数在二进制中长什么样子?答:最后一个bit为0 。
于是我们有以下规则:
0结尾的二进制数是偶数;1结尾的二进制数是奇数。
例子:
2对应10,4,对应100,8对应1000,16对应10000
大家有没有看到10后面加个0等于是乘二?好像我们可以得出一个规律: 在一个二进制数后面补一个零等于乘二?
一般来说,没接触过二进制的同学在回答上面这个问题的的时候基本都是说:“No!”因为这里如果考虑奇数,那么,很可能不对!但是,乘二不是在后面补零?末尾为零不就是偶数?这......有什么不对呢?
例子:
十进制7 == 二进制 111
7*2 == 14 == 二进制 1110
似乎是这么个理?再演算一下其他数字......得到乘法规则如下:
二进制乘2运算等于在数字末尾补一个0.
思考一下,乘法是补0,除法呢?我们只考虑整除,即只取整数商。
例子:
十进制7的二进制为111,十进制7/2 == 十进制3 == 二进制 11
十进制11的二进制为1011,十进制11/2 == 十进制5 == 二进制101
除法规律:
二进制除2运算等于在砍掉数字末尾一个数位。
如何把任何的二进制数转换为十进制?这是下一节的内容。
补充练习:
给定一个整数v,如何判断v是否2的某次方(Power of 2)?
比如,v = 4 = 2^2,返回True;v = 9 并非2的次方,返回False。
请写一个C语言的函数来实现。
归纳一下之前的内容。首先,计算机科学是关于“计算”的科学,是关于“思维”的科学。然后,介绍了二进制,当然是非正式地介绍,为的是归纳出两个规则:在后补零等于乘2(扩展思考,除2怎么做?);尾数为0的数是偶数(尾数为1的是奇数)。现在,我们需要思考的是如何在二进制数与十进制数之间进行转换。特别是,我们不要满足于怎么做,还要思考为什么。更重要的是,我们想得到一个“过程”:一个计算机可以读懂的过程。
当我们思考一个过程的时候,首要必须确定的是:输入什么,输出什么。比如,我们命名将二进制转换为十进制的过程为B2D,这只是一个名字。
例子:
function B2D(a)
输入:一个二进制数a
输出:a所代表的十进制数
在完全描述出这个程序之前,我们先计算一些实例出来,比如:
例子:
输入0,立即输出0;输入1立即输出1!这太简单,但是请注意,这很重要!
考虑多比特输入。比如:
输入:1110;输出:1110代表的十进制(记为Res)。根据之前的规则,补零等于乘2,所以,这个数必然是
111
表示的十进制数乘2!!!所以,我们的计算结果就是2*B2D(111)。
但是,如果是奇数呢?比如,输入1111 。Ok,没关系,我们照样可以得到结果:2*B2D(111) + 1
,多加个1就好了。
所以,我们可以完成我们的程序描述了:
注意:#代表注释!
function B2D(a)
#输入:一个二进制数a
#输出:a所代表的十进制数
if a < = 1: #程序的终止条件
return a; #即,当a小于等于1,原样输出.
else: #否则
return 2*B2D(a/2) + lsb(a) #lsb(x)指的返回x的最后一个比特.
请注意一点,我们现在只有二进制数操作的两个规则:乘2等于补零;0为偶数,1为奇数。上面这个程序违反规则了没?有啊,怎么能用除法“/”?其实,这里的除法就是把a的最后一个比特删除。而lsb(a)指的是a的最后一个比特。
这个程序中最古怪之处是:2*B2D(a/2) + lsb(a)
。因为,这里B2D这个程序自己调用了自己!!!我们把这种自己调用自己的过程称为“递归”。
所有计算无非递归而已!所有的思维都是递归的!
作业:用C语言实现以上程序中的“除2”运算及lsb过程。
现在反过来,如果要从十进制得到二进制应该如何?通常,我们的课程会像这样教,如下图:
我们当然不能满足于知道这个方法,要多问一句,为什么?好,重新来,思维运动起来!现在我们要写一个名字为“D2B”的程序,输入一个十进制数,输出一个二进制数。
function D2B(a)
输入:一个十进制数a
输出:a所代表的二进制数
思路如下:
首先,我们需要得到程序的终止条件。如果 a< = 1,怎么样?输出a!然后,计算无非递归,递归起来!比如,7这个数,我们能知道它最后一个比特是什么吗?奇数,当然是1 。如果是16呢?偶数,当然是0 。就是说,对任意输入,我们至少知道了部分答案,a的最后一个比特。剩下的比特who care?交给递归啊!我们得到D2B(a')+lsb(a),其中a'是a删除最后一比特之后的数。呃,忘记了,a是十进制数呢?没事,除法嘛,除2。
程序:
function D2B(a)
# Input, a decimal number a;
# Output, the binary number of a;
if a <= 1: #终止条件!
return a;
else:
return D2B(a/2)||lsb(a)
D2B(a) = D2B(a/2) || b
,这样的过程为什么会结束?也许很多同学立即会担心,递归怎么会结束呢?
为什么递归会终止?因为每一个递归程序都有一个终止条件。而且,每次自己调用自己的时候,参数都在减小(这很重要),这就确保了终止条件一定会到达。
递归效率低?我的回答是:思维,不在乎效率;其次,递归并不总是低效率。相信提这个问题的同学学过一些,但是,对递归的理解不能那么片面。以后继续深入。
作业题:用C语言编程实现以下过程。
function fac(n)
输入:整数n
输出:n的阶乘
要求:必须使用递归
最后一个内容,这是世界上最有意思的问题之一。话说有两只兔子......
作业:斐波那契数列:1 1 2 3 5 8 13 21...... 请用C语言用递归的方法写出第n项斐波那契数。
function fib(n)
输入:整数n
输出:第n项斐波那契数
要求:必须使用递归
计算机的核心是CPU,我们总是希望这些个核心设备做尽可能少的“操作”,但是借助它又似乎无所不能。这似乎矛盾,其实又不矛盾。上面讲到二进制的加法和乘2。然后讲到用递归的方法去思考。
接下来,先延续上面的思路,出一道题,实现二进制数的乘法:
function multiply(a,b)
输入: a和b,两个任意长的二进制数;
输出:a*b 。
要求:请用递归的方法,并且只能用加法和乘2操作来完成,不要写程序,用我昨天的描述方法即可。
建立、改变思维方式应该放第一位,请不要小看这些似乎没用的东西。
例子:
11*1 =11;11*0 ==0;
11 * 10 ==110,实际就是11乘2,即11后面补个0;
如果是11 * 11?当然应该是11*10 +11*1,即11*(10 + 01)。
推广到任意比特的乘法:x * y = 2*multipy(x, y/2) + x 。这里看明白了吗?递归!
代码:
function multiply(a,b)
if b == 0:
return 0;
if b == 1:
return a;
if is_even(b): # the last bit of b is 0;
return 2*multiply(a, b/2);
else: # b is odd
return 2*multiply(a, b/2) + a;
这个乘法算法展示,计算机只要乘2和加法就可以做任何乘法,对吗?但是,我们怎么不讲除法和减法呢?下回分解。
练习:
用C语言编程实现is_even()和is_odd() 函数。
is_even(),如果输入为偶数,返回True,否则返回False。
is_odd判断输入是否奇数。
作业: 用C语言编程实现两个整数的乘法。
要求,不能用递归!
2019-09-24整理