[关闭]
@bintou 2019-09-24T04:08:52.000000Z 字数 3764 阅读 366

CSI讲义1--二进制及其相关操作

CSI 二进制


本文为非常规的《计算机科学导论》课程讲义,适用于大一新生。初学者可能会觉得有点难。最好是不要畏难,跟上思路。相信没有那么难。--斌头老师

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整理

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注