二进制

创建时间:
2018-06-22 11:48
最近更新:
2018-08-12 17:19

涉及其他进制的内容整理在本站 《进制 (二进制、八进制、十进制、十六进制 等) - 转换、字面量》 中

二进制的 第0位 指 最低位

例如 一个 32bit 的整数,它的 最高位/最左端 是 第31位,最低位/最右端 是 第0位。

Vocabulary

  • one's complement: ?
  • two's complement: 二进制补码?

二进制的运算规则

加法 只有 4 种情况:

  • 0+0=0
  • 0+1=1
  • 1+0=1
  • 1+1=10 (进位: 逢二进一)

减法 只有 4 种情况:

  • 0-0=0
  • 1-1=0
  • 1-0=1
  • 0-1=1 (借位: 借一当二)

乘法 只有 4 种情况:

  • 0*0=0
  • 0*1=0
  • 1*0=0
  • 1*1=1

除法 只有 4 种情况,但是因为 0 作为除数没有意义,最终仅剩下 2 种情况:

  • 0/1=0
  • 1/1=1

负数的二进制 - 用二进制减法 -n = 0 - n 计算得出

以下通过 "借位" 计算 0 - 10 = -10:

  0000 0000 (  0 的二进制)
- 0000 1010 ( 10 的二进制)
--------------------------
= 1111 0110 (-10 的二进制)

负数的二进制 - 用二进制加减法推导规律

0111 =  7 (再 +1 就成了 1000 / -8)
0110 =  6
0101 =  5
0100 =  4
0011 =  3
0010 =  2
0001 =  1
0000 =  0 (再 -1 就成了 1111 / -1)
1111 = -1 (再 +1 就成了 10000,舍弃溢出之后为 0000 / 0)
1110 = -2
1101 = -3
1100 = -4
1011 = -5
1010 = -6
1001 = -7
1000 = -8 (再 -1 就成了 0111 / 7)

规律总结: -n = ~n +1

负数的二进制 - 用 上限/掩码 的二进制 得出

假设 字长 4bit,则:

  • -a = 1111 - a + 1
  • -a = 10000 - a

TonyRemark: 已进行个位数随机测试,未能证伪以上规律。截至 2018-06-24 未知以上规律的原理。

负数的二进制 - 用 上限/掩码 与 绝对值 得出

step 1: x = max - abs(aNegativeNumber) + 1
step 2: 将 x 的最高位设置为 1,即为 aNegativeNumber 的二进制。

aNegativeNumber 表示一个 小于0 的整数。不适用于 等于0 或者 大于 0 的情况。
max 表示这些 bits 能表示的 带符号整数 的 最大值。
abs(aNegativeNumber) 表示该负数的 absolute value (绝对值)。

常用 bits 能表示的 带符号整数 的 最大值 (即: 最高位为 0、其他位均为 1)

 4bits 能表示的 带符号整数 的 最大值 为 7
 8bits 能表示的 带符号整数 的 最大值 为 127
16bits 能表示的 带符号整数 的 最大值 为 32767
24bits 能表示的 带符号整数 的 最大值 为 8388607
32bits 能表示的 带符号整数 的 最大值 为 2147483647
64bits 能表示的 带符号整数 的 最大值 为 9223372036854775807

负数的二进制 的 加法 (进位、舍弃溢出)

    0001 0100 (20 的二进制)
+   1111 0110 (-10 的二进制)
----------------------------------------
= 1 0000 1010 (10 的二进制) (未舍弃溢出)
=   0000 1010 (10 的二进制) (已舍弃溢出)

以上测试代码假设 字长 8bit,第 9bit 因溢出被舍弃。

负数的二进制 的 加减法转换

假设有 二进制数 a、b、c,且 c 是 b 的负数 (c = -b),则:

  • a - b = a + c = a + (-b)
  • a + c = a - b = a + (-b)

如果 二进制 的实现 不是 补码 而是 原码,则上述 算法 不成立。

原码

网摘 (很可能是错的): 汇编、C 等其他高级语言中使用的都是原码。

原码的得来: 直接把 对应的正数 的最高位由 0 改为 1,即得到 负数的原码。原码能够直观的表示一个负数的真值。

正数的原码 (与正确的二进制相同):

0111 =  7
0110 =  6
0101 =  5
0100 =  4
0011 =  3
0010 =  2
0001 =  1
0000 =  0

负数的原码 (将 正数的原码 的 首位 改为 1):

1111 = -7
1110 = -6
1101 = -5
1100 = -4
1011 = -3
1010 = -2
1001 = -1
1000 = -0

原码加法测试:

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

以上展示了原码存在的部分问题:

  • 00001000 都表示 0,重复、浪费空间。
  • 加法运算大部分错误。

现实中,原码是错误方案,仅作为参照物用于解释 补码方案。

补码 (取反、加一)

  • 二进制补码 是一种数值的转换方法,由 "取反" 与 "加一" 两步组成。
  • Tony 的理解: -n = ~n + 1,其中 ~ 运算符 对 n 执行 "按位求补" 运算,其效果相当于 反转每一位; + 1 即 "补码"。
  • 网摘: 补码的得来 是为了 让负数变成能够加的正数,因此 负数的补码 = 模 - 负数的绝对值,即 -a = 1 0000 0000 - a
  • 网摘: n - 1 = n + 1111 1111
  • 网摘: 补码的设计目的有二: 1. 使 符号位 能与 有效值部分 一起参加运算,从而简化运算规则。2. 使减法运算转换为加法运算,进一步简化计算机中运算器的线路设计。
  • 网摘: 正数 的 原码、反码、补码 是一样的。负数 的 补码 就是 取反、加一。
  • 网摘: 随便一本 《计算机原理》 都会提到 "实际上,计算机内部 采用 二进制补码 表示负数"。

网摘 - 补码方案 versus 原码方案

首先,要明确一点: 计算机内部 用什么方式表示负数 其实是无所谓的,可以用任意方式表示负数,只要能够保持一一对应的关系就行。
然而,二进制补码 是最方便的方式,它的便利体现在,所有的加法运算,包括正数负数,都可以使用同一种电路完成。

对比测试如下:

原码方案:

    0001 0000 = 16
+   1000 1000 = -8 的原码
--------------------------
    1001 1000 = -24 的原码

以上测试中 正常的加法规则 得到了错误的答案。
也就是说,如采用原码方案,则 正常的加法规则不适用于正数与负数的加法,因此必须制定两套运算规则,一套用于正数加正数,还有一套用于正数加负数。从电路上说,就是必须为加法运算做两种电路。

补码方案:

    0001 0000 = 16
+   1111 1000 = -8 的补码
-------------------------
    0000 1000 = 8

以上测试中 正常的加法规则 得到了正确的答案。
这说明了,补码方案 可以将 加法运算规则 扩展到整个整数集,从而用一套电路就可以实现全部整数的加法。相比 原码表示法,补码表示法 在加法运算中更方便。

补码 取反、加一 算法的原理

要将 正数 转换成 对应的 负数,用 0 减去这个 正数 即可,即 -n = 0 - n。例如 -8 = 0 - 8:

    0000 0000 = 0
-   0000 1000 = 8
-----------------
            ?

以上竖式中,被减数 0 小于 减数 8,不够减。需要问上一位 "借 1"。于是竖式改写为:

  1 0000 0000 = 256
-   0000 1000 = 8
-----------------
    1111 1000 = -8

进一步观察,可以发现 1 0000 0000 = 1111 1111 + 1,所以竖式可以分拆成两步:

    1111 1111 = -1
-   0000 1000 = 8
-----------------
    1111 0111 = -9
+   0000 0001 = 1
-----------------
    1111 1000 = -8

二进制补码 的 两个转换步骤 就是这么来的。

为什么 正数 加法 适用于 二进制补码

实际上,我们要证明的是,X - YX + (-Y) 可以用 X 加上 Y 的二进制补码完成。

假设当前为 8bit 机器。

已知 Y 的二进制补码等于 1111 1111 - Y + 1。所以,X + Y 的二进制补码,就等于 X + (1111 1111 - Y + 1)。我们假定这个算式的结果等于 Z,即 Z = X + (1111 1111 - Y + 1)

接下来 分成两种情况讨论。

第一种情况:

如果 X 小于 Y,那么 Z 是一个负数。这时,我们就对 Z 采用 "二进制补码的逆运算",求出它对应的正数绝对值,再在前面加上负号就行了。

由 二进制补码的运算 -n = 1111 1111 - n + 1 可推导出 二进制补码的逆运算 n = -(1111 1111 - n + 1)

所以,Z = -[1111 1111 - Z + 1] = -[1111 1111 - (X + (1111 1111 - Y + 1)) + 1] = X - Y

第二种情况:

如果 X 大于 Y,这意味着 Z 肯定大于 1111 1111,由于当前是 8bit 机器,最高的第 9bit 必须被舍弃溢出,这相当于减去 1 0000 0000。所以 Z = Z - 1 0000 0000 = [X + (1111 1111 - Y + 1)] - 1 0000 0000 = X - Y

上述两种情况证明了 在正常的加法规则下,可以利用二进制补码得到正数与负数相加的正确结果。换言之,计算机只要部署加法电路和补码电路,就可以完成所有整数的加法。

还有一种证明方法: Z = X + (1111 1111 - Y + 1) 式子可以写为 Z = X - Y + 1 0000 0000,这在硬件上可以理解为两部分电路来实现,第一部分是前面的 X - Y (这里姑且不管计算的结果是正还是负),第二部分是 X - Y 计算的结果再和 1 0000 0000 相加,最终得到计算的结果 Z。而在 8bit 的机器上 1 0000 0000 是不能出现的,其实这时 1 0000 0000 就相当于 0000 0000 (舍去了最高位),计算过程如下:

Z
= X + (1111 1111 - Y + 1)
= X - Y + 1 0000 0000
= X - Y +   0000 0000
= X - Y

证毕。

这样我们就证明了 X - YX + (-Y) 可以用 X 加上 Y 的二进制补码完成,而不必分两种情况来证明。

为什么一个字节的范围是 -128~127

网摘 (不一定正确): sbyte 类型的数值 (8bit 有符号整型),那么理应不存在 -128,但是恰好 -128 的补码是 -0,并且计算机中负数有对应的补码就可以进行运算,表示 0 的有 +0 就够了,所以 -0 被拿来表示 -128 的补码,因此,负数有 -128,而正数只有 127

周易/易经/八卦

☰,111=1×2²+1×2¹+1×2º=7
☱,110=1×2²+1×2¹+0×2º=6
☲,101=1×2²+0×2¹+1×2º=5
☳,100=1×2²+0×2¹+0×2º=4
☴,011=0×2²+1×2¹+1×2º=3
☵,010=0×2²+1×2¹+0×2º=2
☶,001=0×2²+0×2¹+1×2º=1
☷,000=0×2²+0×2¹+0×2º=0
  1. 易经与二进制

Resource

  1. 原码, 反码, 补码 详解 - 博客园 张子秋 - Tony Praise
  2. 整数二进制补码的数学原理 (two's complement)
  3. 计算机二进制以及原码、反码、补码入门详解
  4. 原码、反码、补码 - 并没有讲明白
  5. 负数的二进制如何转化为十进制
  6. 理解计算机减法
  1. 计算机是怎么识别二进制的 或者应该说问处理器是怎么识别 1 和 0 的
  2. 程序最终编译为机器代码,里面全部都是 0 和 1,那么计算机是怎么截断这些 01 的,截断后怎么区分每组的意义 - 一段内存到底表示什么,依赖于你如何解释它,而不仅仅是看里面每一位的状态。比如在 C 语言里,有一段内存是连续 32 个 1,你把它按照一个 int 来解读就是 -1,按照 unsigned int 来解读就是 4294967295,甚至你还可以把它当成一个指针、一条指令来解读,全凭你的喜好。
  3. 十进制小数如何转换为二进制小数
  1. 数制
  2. 二进制基础
  3. 二进制有什么好处,为何电脑都采用二进制
  4. 二进制/八进制/十进制/十六进制
  1. 三进制计算机 Сетунь
  2. 前苏联 的 平衡三进制/对称三进制 计算机
  1. 如何用最简短的二进制代码表示一张 19*19 的围棋棋盘的情况
  2. 1000 瓶药水,1 瓶有毒药,几只小白鼠能够找出?
  3. 怎样暴力读取二进制数据文件
  4. 二进制文件格式设计
  1. Binary Challenge 二进制&十六进制 学习 游戏
  2. 用十根手指表达二进制数

1