计算机组成原理学习笔记：进位计数制

概述

• 数据如何在计算机中表示?
• 运算器如何实现数据的算术、逻辑运算？

进位计数制

• 十进制、二进制、八进制、十六进制
• 其他进制 —转换–> 十进制
• 二进制、八进制、十六进制之间的相互转换
• 十进制 —转换–> 其他进制
• 真值和机器数

计数方法演进

古老的画线计数

• 画竖线或横线的方式，没法记录很多的情况

罗马数字

• 后来人们意识到，用不同的符号可以表示不同的数量, 也就是不同的符号反映不同的权重
  • 举例：罗马数字
    • 1: I
    • 2: II
    • 3: III
    • 4: IV
    • 5: V
    • 10: X
    • 13: XIII
    • 50: L
    • 100: C
    • 500: D
    • 1000: M
    • 1888: MDCCCLXXXVIII
  • 缺点：当数字继续增大，可用符号会越少, 会越不方便

阿拉伯数字与十进制

• 后来，古印度人发明了阿拉伯数字，并传入欧洲
  • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  • 这10种符号反映不同的权重，代表不同的实际数值
  • 后来发明了十进制的计数系统：不仅符号会反映权重，符号所在的位置也会反映权重
  • 975 = 9 * 100 + 7 * 10 + 5 * 1 = 9 * $10^2$ + 7 * $10^1$ + 5 * $10^0$
  • 可以看到引入了乘法的思想
• 对于十进制概况来说, 有这么一个公式
  • $K_n{K}_{n-1}...K_2{K}_1{K}_0$ = $K_n\ast 10^n+K_{n-1}\ast 10^{n-1}+...+K_2\ast 10^2+K_1\ast 10^1+K_0\ast 10^0$
• 扩展后的公式：
  • $K_n{K}_{n-1}...K_2{K}_1{K}_0{K}_{-1}{K}_{-2}...K_{-m}$ = $K_n\ast 10^n+K_{n-1}\ast 10^{n-1}+...+K_2\ast 10^2+K_1\ast 10^1+K_0\ast 10^0+K_{-1}\ast 10^{-1}+K_{-2}\ast 10^{-1}+...+K_{-m}\ast 10^{-m}$
• 十进制总结：
  • 十进制有 0 ~ 9 , 逢十进一

R进展推广

• 公式：$K_n{K}_{n-1}...K_2{K}_1{K}_0{K}_{-1}{K}_{-2}...K_{-m}$ = $K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0+K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m}$

• 引入基数的概念

  • 基数: 每个数码位所用到的不同符号的个数，r进制的基数为r
  • 对比十进制是有 0 ~ 9 这十种不同的符号, 那么r进制就有r个符号,其基数是r
  • 比如：古巴比伦的六十进制，和现今的时间上的六十进制

• 二进制：0,1

  • 101.1 -> 1 * $2^2$ + 0 * $2^1$ + 1 * $2^0$ + 1 * $2^{-1}$ = 5.5
  • 注意：如果是两个二进制进行加法运算, 怎样计算?
    • 101.1 + 11.1 = ?
    • 小数部分：0.1 + 0.1 = 1.0 (满2进1)
    • 101 + 11 = 1000 (满2进1)
    • 所以：101.1 + 11.1 = 1001.0 = 9 (十进制)
  • 二进制是最适合计算机存储和处理的一种计数方式
    • 可以使用两个稳定状态的物理器件就可以表示二进制的0和1, 也可以用高电平和低电平，还可以用正电荷和负电荷
    • 另外0和1也可以表示假和真, 可以很方便实现逻辑运算
    • 可以很方便地使用逻辑门电路实现算术运算

• 八进制：0,1,2,3,4,5,6,7

  • 5.4 -> 5 * $8^0$ + 4 * $8^{-1}$ = 5.5 (十进制)
  • 注意：如果是两个八进制进行加法运算, 怎样计算?
    • 比如：5.4 + 1.4 = ?
    • 这里 0.4 + 0.4 = 1.0，得8进一
    • 所以 5.4 + 1.4 = 7 (十进制)

• 十进制：0,1,2,3,4,5,6,7,8,9

  • 注意：如果是两个十进制进行加法运算，我们已经很熟悉了
  • 5.5 -> 5 * $10^0$ + 5 * $10^{-1}$ = 5.5 (十进制)
  • 是最符合人类记数习惯的一种方式

• 十六进制：0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

  • 5.8 -> 5 * $16^0$ + 8 * $16^{-1}$ = 5.5 (十进制)
  • 注意：如果是两个十六进制进行加法运算, 怎样计算?
    • 如：5.8 + 0.9 = ?
    • 这里0.8 + 0.9 = 1.1, (注意：8+9=17，满16进1，所以是1.1)
    • 所以：5.8 + 0.9 = 6.1 (十进制)

• 总结

  • 在计算机世界里我们除了二进制，还会经常使用八进制和十六进制
  • 因为八进制和十六进制可以和二进制很好的对应

任意进制转十进制

• r进制：$K_n{K}_{n-1}...K_2{K}_1{K}_0{K}_{-1}{K}_{-2}...K_{-m}$ = $K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0+K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m}$
• 上述算法中，不同数码位在不同的位置有不同的位权，把每个数码位的值*它在这个位置的位权(比如：$r^0$), 再相加即可得到对应的十进制
• 二进制：10010010.110 = $1\ast 2^7+1\ast 2^4+1\ast 2^1+1\ast 2^{-1}\ast 1\ast 2^{-2}$ = 146.75
  • 其实上面是套用公式，针对二进制转换十进制是有一套特别的快速计算方案的，如下：
  • 10010010.110 这个作为基数, 我们可以对应上每一位的权值，然后让权值相加即可得到结果
  • 128, 64, 32, 16, 8, 4, 2, 1 . 0.5, 0.25, 0.125
  • 上面 第8位的1对应128，第5位的1对应16, 第2位的1对应2；小数第1位的1对应0.5, 小数第2位的1对应0.25
  • 把这些数字加起来：N = 128 + 16 + 2 + 0.5 + 0.25 = 146.75
  • 这种的优点是更加人性，更加好算
• 八进制
  • 251.5 = 2 * $8^2$ + 5 * $8^1$ + 1 * $8^0$ + 5 * $8^{-1}$ = 168.625
• 十六进制
  • AE86.1 = 10 * $16^3$ + 14 * 16^{2} + 8 * $16^1$ + 6 * $16^0$ + 1 * $16^{-1}$ = 44678.0625
    • A:10
    • E:14

二进制转化为八进制和十六进制以及逆向转化

1 ) 二进制转八进制

• 8进制的基数r是8，也就是每个数码位可能出现8种不一样的情况
• 2进制的基数是2，每个数码位可能出现 0,1 两种情况
• 如果把三个二进制位进行组合，那么有可能出现的情况：N = 2 * 2 * 2 = 8 这样就能够对应上八进制的八种情况了
• 如果2进制转化为8进制，只需要三位一组，每组转换成对应的八进制符号
• 例如：1111000010.01101 二进制
  • 二进制：001 111 000 010 . 011 010
  • 八进制： 1 7 0 2 . 3 2
  • 所以，这样转化为八进制后就是：1702.32

2 ) 二进制转十六进制

• 4位一组，每组转换成对应的十六进制符号
• 例如：1111000010.01101 二进制
  • 二进制： 0011 1100 0010 . 0110 1000
  • 十六进制： 3 C 2 . 6 8
  • 所以，这样转化为十六进制后就是：3c2.68

3 ) 八进制转二进制

• 每位八进制对应的三位二进制
• $(251.5{)}_8$ -> $(010101001.101{)}_2$

4 ) 十六进制 转 二进制

• 每位十六进制对应的4位二进制

• $(AE86.1{)}_{16}$ -> $(101011100110.0001{)}_2$

• 总结：

  • 同样，我们可以思考，八进制和十六进制的相互转化
    • 可以借助二进制和十进制来转化
    • 最好的方式是通过二进制来转化

各种进制的常见书写方式

• 二进制 – $(1010001010010{)}_2$ 或 $1010001010010B$
• 八进制 – $(1652{)}_8$
• 十六进制 – $(1652{)}_{16}$ 或 1652H 或 0x1652
• 十进制 – $(1652{)}_{10}$ 或 1652D

十进制转换成任意进制

• r进制：$K_n{K}_{n-1}...K_2{K}_1{K}_0{K}_{-1}{K}_{-2}...K_{-m}$ = $K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0+K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m}$
• 我们想要转换的数字是 75.3

1 ）整数部分处理

• 由上式r进制和十进制的对应关系可知，r进制的整数部分是：$K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0$ 其值是 75
• 我们同时除上一个r, 如下
  • $\frac{K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0}{r}=K_n\ast r^{n-1}+K_{n-1}\ast r^{n-2}+...+K_2\ast r^1+K_1\ast r^0...K_0$
  • 这个化简，$K_n\ast r^{n-1}+K_{n-1}\ast r^{n-2}+...+K_2\ast r^1+K_1\ast r^0$是除法的商，而 K_0 是余数
  • 前面的商可设成x, 则分子可简化为：$r\ast x+K_0$, 则整个除式等价于 $\frac{r\ast x+K_0}{r}$
  • 对r进制来说，任何一个数码位的值应该在 0 ~ r-1 的范围，同样 $k_0$也在这个范围内, 即任意一个数码位都有: $k_i<r$
  • 这样，我们可以得知，用r进制表示75的时候，最低的整数位是K_0，同理，我们用这个商再除r, 可以得到K_1的值，以此类推
• 举例：
  • 十进制 -> 二进制 r = 2
    • 75 ÷ 2 = 37 … 1 这个余数1是$K_0$
    • 37 ÷ 2 = 18 … 1 这个余数1是$K_1$
    • 18 ÷ 2 = 9 … 0
    • 9 ÷ 2 = 4 … 1
    • 4 ÷ 2 = 2 … 0
    • 2 ÷ 2 = 1 … 0
    • 1 ÷ 2 = 0 … 1
    • 由上面得到：
      • 75D = 1001011B
      • $(75{)}_{10}$ = $(1001011{)}_2$
      • 这是除基取余法
    • 或者直接用短除法来做, 最后得到的余数是最高位，第一次得到的余数是最低位，然后把这些余数拼起来就是转换后的结果
• 同理，可以把 十进制的 75 转化成八进制
  • 可以用除基取余法，也可以用短除法

2 ) 小数部分处理

• 小数部分是0.3, 可以表示为：$K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m}$
• 上面乘上基数r，即：$(K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m})\ast r$ = $K_{-1}\ast r^0+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-(m-1)}$
• 这样，整数部分变为了 $K_{-1}\ast r^0$ 也就是 $K_{-1}$, 同理，剩下的小数部分也可同样处理
• 这个过程，如下表示
  • 0.3 * 2 = 0.6 = 0 + 0.6
  • 0.6 * 2 = 1.2 = 1 + 0.2
  • 0.2 * 2 = 0.4 = 0 + 0.4
  • 0.4 * 2 = 0.8 = 0 + 0.8
  • 0.8 * 2 = 1.6 = 1 + 0.6
  • 0.6 * 2 = 1.2 = 1 + 0.2
  • …
  • 可以看到上述出现了循环，也就是说十进制的0.3转化为二进制是没法精确的表示的
  • 0.3D = 0.01001… B 这里是无限循环
• 同理，也可以用短乘法，但因为是小数部分，第一次得到的是高位，后面是低位

拼凑法解决十进制转换二进制的问题

• 我们下面有一个速记表
  • $2^{-3}$ = 0.125
  • $2^{-2}$ = 0.25
  • $2^{-1}$ = 0.5
  • $2^0$ = 1
  • $2^1$ = 2
  • $2^2$ = 4
  • $2^3$ = 8
  • $2^4$ = 16
  • $2^5$ = 32
  • $2^6$ = 64
  • $2^7$ = 128
  • $2^8$ = 256
  • $2^9$ = 512
  • $2^{10}$ = 1024
  • $2^{11}$ = 2048
  • $2^{12}$ = 4096
• 基于上述速记表我们来拼凑解决问题
  • 260.75 = 256 + 4 + 0.5 + 0.25 = $2^8+2^2+2^{-1}+2^{-2}$ = 100000100.11
  • 533.125 = 521 + 16 + 4 + 1 = $2^9+2^4+2^2+2^0+2^{-3}$ = 1000010101.0001

真值和机器数

• 十进制转化为二进制是可以很方便的保存在计算机里，如果这个十进制数带正负，我们会增加一个标志位，用一个二进制的0或1来表示正或负
• 后续我们会用原码，反码，补码，移码来表示带有正负的数
• 真值
  • 符合人类习惯的数字
• 机器数
  • 数字实际存到机器里的形式，正负号需要被"数字化"

总结

• 进位计数制
  • r进制
    • 基数=r, 每个数码位可能出现r种字符，逢r进1
  • r进制数 -> 十进制
    • $K_n{K}_{n-1}...K_2{K}_1{K}_0{K}_{-1}{K}_{-2}...K_{-m}$ = $K_n\ast r^n+K_{n-1}\ast r^{n-1}+...+K_2\ast r^2+K_1\ast r^1+K_0\ast r^0+K_{-1}\ast r^{-1}+K_{-2}\ast r^{-1}+...+K_{-m}\ast r^{-m}$
    • r进制数的数值 = 各数码位与位权的乘积之和
  • 二进制数 <–> 八进制
    • 每3个二进制位对应一个八进制位 (注意补位)
  • 二进制 <–> 十六进制
    • 每4个二进制位对应一个十六进制位 (注意补位)
  • 十进制 -> r进制
    • 整数部分：除基取余法，先取得的"余"是整数的低位
    • 小数部分：乘基取整法，先取得的"整"是小数的高位
    • 注意：有的十进制小数无法用二进制精确表示，如0.3
    • 注意：乘基取整法，如果乘上几次发现小数部分变成了0.0, 则可以用二进制精确表示
  • 真值和机器数
    • 真值：实际的带正负号的数值(人类习惯的样子)
    • 机器数: 把正负号数字化的数(存到机器里的样子)