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

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