从零构造一台计算机——二进制

从零构造一台计算机——二进制

二进制的定义

人类发明0,1,2,3,4,5,6,7,8,9这10个数字,大概率是因为我们有十个手指。假如我们把这种计数方式称为十进制计数法,然后我们来到了一个世界,那里面的人只有2个手指。我们该如何用十进制的思想去用创造出二进制呢。

简单约定一下,后面用下标表示进制,比如\(10_2\)表示二进制,而\(10_{10}\)表示十进制。

首先,我们能用的数字只有0,1这2个,忘掉十进制中其余的数字。那么我们如何计数呢?以数苹果为例,在十进制中,我们数到第\(9_{10}\)个苹果的时候,我们需要做一个操作就是进位,然后低位置为0。现在来到二进制,我们如何表示下面苹果的数量:

%title插图%num

 

需要注意的是,二进制中只有0,1,当我们数到第\(1_2\)个苹果的时候,我们需要做的也是进位。类似地,我们会得到\(10_2\),继续数下去,就是\(11_2\),所以答案就是这里有\(11_2\)个苹果。

对于一个十进制数,我们知道它有个位十位百位千位万位……,其实这些代表的就是\(10^n\)。比如个位是\(10^0\),十位是\(10^1\),百位是\(10^2\),对于一个数\(123_{10}\),我们可以说它的个位是3,十位是2,百位是1,那么我们可以通过这样计算来得到:

\[123_{10} = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0 \]

于是,对于十进制,我们可以抽象出下面的公式:

\[x_{n}x_{n-1}x_{n-2}…x_{0}=\sum_{i=0}^{n}{10^i \cdot x_i} \]

那么,对于二进制,我们自然而然可以得到下面的公式(需要注意的是,下面公式右边的10其实是\(10_2\)):

\[x_{n}x_{n-1}x_{n-2}…x_{0}=\sum_{i=0}^{n}{10^i \cdot x_i} \]

公式右边的10我们称之为基底,十进制的基低是\(10_{10}\),二进制的基低是\(10_{2}\)。

二进制转十进制

对于二进制,我们已经得到这样的公式:

\[x_{n}x_{n-1}x_{n-2}…x_{0}=\sum_{i=0}^{n}{\left(10_2\right)^i \cdot x_i} \]

由于二进制中的0,1和十进制中的0,1的含义是一样的,并且二进制中的\(10_2\)等价于十进制中的\(2_{10}\),而\(x_i\)(公式右侧)在二进制中只有可能是0,1,所以我们可以作如下推导:

\[\sum_{i=0}^{n}{\left(10_2\right)^i \cdot x_i} \Rightarrow \sum_{i=0}^{n}{\left(2_{10}\right)^i \cdot x_i} \]

于是我们可以用十进制的方式去表达二进制:

\[\left(x_{n}x_{n-1}x_{n-2}…x_{0}\right)_{2}=\sum_{i=0}^{n}{\left(2_{10}\right)^i \cdot x_i} \]

我们可以验证一下:

\[11_2=1\cdot2^1+1\cdot2^0=3 \]

所以二进制的\(11_2\)等价于十进制的\(3_{10}\),他们都表示上图中苹果的数量。

二进制的加法运算

二进制的加减法运算,也可以用十进制的思想来做,首先通过上面例子我们知道\(1_2\)个苹果加上\(1_2\)个苹果等于\(10_2\)个苹果,也就是说在二进制中1+1=10。基于这个条件,我们分别来计算1001+01011011+0111

首先看1001+0101,我们列出下面的式子,然后用十进制加法的思想去做,可以得到结果是1110

\[\begin{split} \left(进位\right)0\quad&0\quad0\quad1\\ &1\quad0\quad0\quad1\\ +&\underline{0\quad1\quad0\quad1}\\ 0\quad&1\quad1\quad1\quad0\\ \end{split} \]

然后来看1011+0111,我们也可以列出下面的式子,用同样的方法去做,但是这边最后发生了进位,所以结果是10010

\[\begin{split} \left(进位\right)1\quad&1\quad1\quad1\\ &1\quad0\quad1\quad1\\ +&\underline{0\quad1\quad1\quad1}\\ 1\quad&0\quad0\quad1\quad0\\ \end{split} \]

我们可以转成十进制来验算一下,结果是没问题的。那么减法也可以用类似的思想来做。

计算机中二进制的表示

由于二进制只能由0,1组成,那么对于\(n\)位的二进制数,我们有\(2^n\)中组合:从\(000…0\)到\(111…1\)。所以一个\(n\)位二进制数的表示范围是\(0 \to 2^n\)(这里的\(2^n\)是十进制)。

那么如何表示负数呢?可能有人会说前面加个-号,和我们平时表示的方式一样。

其实通过前面的课程我们知道,我们用电路的通断来表示1或者0,电路连通的时候为1,断开的时候为0,只有这两种状态,没有第三种。所以-号其实是无法在计算机中表示出来的。

为此,前辈们想出了有符号数,即把二进制的第一位拿出来作为符号位,1表示负数,0表示正数,剩下的来表示具体的数值。

但是如果负数仅仅用第一位符号位来指示,可能还会遇到很多麻烦:比我们知道十进制中\((-3)+3=0\),这时候我们转化为4位的二进制(第一位为符号位)可以得到\(1011_2+0011_2\),结果是\(1011_2+0011_2=1110_2\),如果\(1110_2\)我们仍然把第一位解释成符号位,那么转换成十进制,就得到了\((-3)+3=-6\),这显然是不对的。

那么如何让\(1011_2+0011_2=0000_2\)呢?在上面加法的例子中,我们还记得\(1011+0111=10010\),这里发生了进位,也就是2个四位数的二进制相加,得到一个五位数的二进制数。那么在计算机中,假如我们设计的计算机只能表示4位的二进制数,那么最终的结果也只能有4位,也就是在该计算机中,我们会得到\(1011+0111=0010\)(最高位1丢弃了)。

基于这个特性,我们可以这样设计负的二进制数,假设这里计算机只能表示4位二进制数,并且\(0011_2\)的负数设为\(x\),我们需要得到\(0011_2+x=0000_2\),又因为该计算机只能表示4位数,所以在该计算机中,\(0000_2=10000_2\),注意后面是一个5位二进制数。所以,我们可以这样去设计\(x\),使得\(0011_2+x=10000_2\),得到\(x=1101\)。我们再来验算一下:\(0011_2+1101_2=10000_2 \Rightarrow 0000_2\),于是我们可以说,在该计算机中\(0011_2+1101_2=0000_2\)是成立的。

补码

上面这种二进制的表示法,我们就称之为补码表示法。

总结一下,可以得到如下的定义(假设计算机能表示的二进制数为\(n\)位):

\[x_补=\left\{ \begin{aligned} x & & (x\ge0) \\ 2^n & – x & (x<0) \end{aligned} \right. \]

最高位的含义

我们现在知道了补码的定义,那么在补码中,任何符号位为0的整数都能得到符号位为1的负数吗?我们可以简单证明一下:

假设有\(n\)位的二进制数\(x_nx_{n-1}x_{n-2}x_{n-3}…x_2x_1\),且最高位为符号位,所以其数值部分为\(x_{n-1}x_{n-2}x_{n-3}…x_2x_1\)。我们设\(x_{n-1}x_{n-2}x_{n-3}…x_2x_1\)为\(t\),那么\(-t\)可以表示为\(2^n-t\),而\(2^n \Rightarrow 100…0\left(n个0\right)\),所以我们可以列出下面的式子:

\[\begin{split} &1_{n+1}\quad0_{n}\quad0_{n-1}\quad0_{n-2}\quad…\quad0_3\quad0_2\quad0_1\\ -&\underline{ 0_{n+1}\quad0_{n}\quad x_{n-1} \quad x_{n-2} \quad… \quad x_{3}\quad x_2\quad x_1}\\ &r_{n+1}\quad r_{n}\quad r_{n-1} \quad r_{n-2} \quad… \quad r_{3}\quad r_2\quad r_1\\ \end{split} \]

我们设结果为\(r_{n+1}r_nr_{n-1}r_{n-2}r_{n-3}…r_2r_1\),当\(t\)不为0的时候,不管是哪一位不为0,我们做减法的时候肯定会向前借位,但是因为\(2^n\)只有第\(n+1\)位为1,所以只能向前传递,借第\(n+1\)位的1。但是因为\(t\)中的\(n+1\)位恒为0,所以我们可以得到\(r_{n+1}=0\),同理\(r_{n}=1\)。所以对于任意的符号位为0的正数,其补码都是符号位为1的负数。

这里面有个特殊情况,对于0来说,是不分正负的,而且\(0+0=0\),那么0到底是+0还是-0呢,也就是说0的最高位应该是什么?

我们先来看+0,由于+0所有位都是0,所以\((+0)+(+0)=(+0)\),是没有问题的。但是对于-0来说就不是这样了,由于-0的最高位为1,所以当\((-0)+(-0)\)之后,最高位变成了0,并且发生了进位,并且进位被丢弃(前面讲过),于是我们得到\((-0)+(-0)=(+0)\),这显然不太对,直觉告诉我们应该用+0来表示0

那么当最高位为1,其余位都是0的时候,这个数字代表什么呢?

还记得我们得出补码的过程吗,我们是用\(2^n-x\)算出来的。那么对于最高位为1的\(n位\)二进制数来说,其我们可以用十进制数\(2^{n-1}\)来表示他的值,通过计算\(2^n-2^{n-1}\)我们可以得到他的正数表示也是\(2^{n-1}\),所以当一个\(n\)位二进制数的最高位为1,其余位全是0的时候,他的值就是\(\left(-2^{n-1}\right)\)。

以一个4位二进制数为例:

正数 负数
0   0000
1   0001 1111   -1
2   0010 1110   -2
3   0011 1101   -3
4   0100 1100   -4
5   0101 1011   -5
6   0110 1010   -6
7   0111 1001   -7
1000   -8

用加法代替减法

前面补码的定义可知,一个\(n\)位的二进制正数\(x\)的负数我们可以用\(x_补 \Rightarrow 2^n – x\)来表示。假如我们要计算\(t-x\),我们可以作如下推断:

\[\begin{split} & t-x \\ \Rightarrow & t+(-x) \\ \Rightarrow & t+x_补 \end{split} \]

那么当\(x\)是负数的时候呢?类似地,我们可以得到:

\[\begin{split} & t-x \\ \Rightarrow & t+|x| \\ \Rightarrow & t+x_补 \end{split} \]

这里的\(|x|\)表示\(x\)的绝对值,我们知道,当\(x\)为负数的时候,其绝对值就是他的补码。

综上所述,不论\(x\)是正的还是负的,我们都可以用其补码来实现用加法代替减法的操作。

总结

最高位作为符号位是一个很巧妙的设计,对于\(n\)位的二进制数\(x_nx_{n-1}x_{n-2}x_{n-3}…x_1x_0\)来说,他们的数值部分都是\(x_{n-1}x_{n-2}x_{n-2}…x_1x_0\),相当于正好把取值范围一分为二,一半给了正数,一半给了负数。

补码的引入也非常合理,最高位不仅可以作为符号位表示数字的正负,并且也可以参与计算、实现用加法代替减法。

分享到 :
相关推荐