码厩技术博客

#2 小数的表达 [编辑中]

:) 本文正在编辑中，暂时不提供浏览...

#1 二进制计算

二进制是计算机内部最基础的数据表示形式。对于 CPU 而言，所有数据最终都会以二进制位（bit）的形式参与运算。

在现代计算机中，一个 bit 只有两种状态：

• 0：低电平、假、关闭
• 1：高电平、真、开启

多个 bit 组合在一起，就可以表示数字、字符、颜色、图片、声音等各种数据。

通常我们使用 8 位（1 Byte）来表示一个整数：

其中最高位通常作为符号位：

• 0 表示正数
• 1 表示负数

原码、反码、补码

为了让 CPU 更容易进行加减法运算，计算机内部引入了原码、反码、补码三种表示方式。

原码

原码就是最直观的表示方法：

• 最高位表示符号
• 其余位表示数值大小

例如在 4 位二进制中：

• 0001 表示 +1
• 1001 表示 -1

但是原码有一个很大的问题：加法器无法直接处理负数。

例如：

1 + (-1)

按照原码计算：

[0001]原 + [1001]原 = [1010]原 = -2

显然结果错误。

反码

为了解决符号位参与运算的问题，引入了反码：

1. 正数的原码、反码、补码相同
2. 负数的反码：符号位不变，其余位取反

例如：

• -1 的原码：1001
• -1 的反码：1110

此时：

[0001]反 + [1110]反 = [1111]反

1111 反码对应原码 1000，即 -0。

这说明反码已经可以让加法器正确处理正负数，但又引入了新的问题：

• 存在 +0
• 也存在 -0

也就是说，0 被表示了两次，浪费了一个编码空间。

补码

于是，补码被发明出来。

负数的补码定义为：

• 负数补码 = 反码 + 1

例如：

• -1 的反码：1110
• -1 的补码：1111

补码解决了两个问题：

1. 消除了 -0
2. 可以直接使用同一套加法器完成加法和减法

所以现代 CPU 内部整数计算几乎全部基于补码。

四位二进制下的原码、反码、补码

为了方便说明，下面以 4 位二进制为例：

可以看到：

• 原码和反码的范围是 [-7, 7]
• 补码的范围变成了 [-8, 7]

补码多出来的 1000，刚好可以用来表示 -8。

例如：

(-1) + (-7) = [1111]补 + [1001]补 = [1000]补

(-2) + (-6) = [1110]补 + [1010]补 = [1000]补

所以：

1000 在补码体系中就是 -8。

再看最经典的例子：

1 + (-1)

[0001]补 + [1111]补 = [0000]补 = 0

因此，CPU 可以只保留加法器，通过补码来实现减法。

减法的实现

CPU 内部通常没有专门的减法器。

减法会被转换成加法：

$A - B = A + (-B)$

例如：

5 - 3

先把 3 转换成 -3 的补码：

• 3：0011
• -3：1101

于是：

  0101
+ 1101
------
  0010

结果为 2。

最高位产生的进位会被丢弃。

乘法的实现

乘法本质上是多次加法。

例如：

3 × 5

可以理解为：

3 + 3 + 3 + 3 + 3

二进制乘法与十进制乘法非常类似。

例如：

    0011    (3)
×   0101    (5)
--------
    0011    (3 × 1)
   0000     (3 × 0，左移一位)
  0011      (3 × 1，左移两位)
--------
  1111      (15)

其中左移一位，相当于乘以 2。

因此：

• a << 1 等于 a × 2
• a << 2 等于 a × 4
• a << n 等于 a × 2^n

很多性能敏感的代码中，会使用位移来替代乘法。

例如：

x * 8

可以写成：

x << 3

除法的实现

除法本质上是多次减法。

例如：

13 ÷ 3

可以理解为：

13 - 3 = 10
10 - 3 = 7
 7 - 3 = 4
 4 - 3 = 1

一共减去了 4 次，所以商为 4，余数为 1。

CPU 内部的除法器通常采用：

• 移位
• 减法
• 比较

来逐位求出结果。

例如：

• 8 >> 1 = 4
• 8 >> 2 = 2

因此：

• a >> 1 等于 a ÷ 2
• a >> 2 等于 a ÷ 4
• a >> n 等于 a ÷ 2^n

对于正整数，右移通常可以替代除法。

取余的实现

取余本质上就是除法之后剩余的部分。

例如：

13 % 3 = 1

因为：

13 = 3 × 4 + 1

对于 2 的幂次取余，可以直接使用位运算。

例如：

x % 8

等价于：

x & 7

因为：

• 8 = 2^3
• 7 = 111

举例：

13      = 1101
7       = 0111
13 & 7  = 0101 = 5

因此：

13 % 8 = 5

这是很多哈希表、环形队列、内存对齐代码中常见的优化手段。

溢出

二进制位数有限，因此整数有最大值和最小值。

例如 8 位有符号整数范围：

• 最小值：-128
• 最大值：127

如果继续加法，就会发生溢出：

  01111111   (127)
+ 00000001   (1)
-----------
  10000000   (-128)

这就是为什么程序中经常需要注意整数溢出问题。

逻辑运算

与（AND）

只有两个 bit 都为 1，结果才为 1。

常见用途：

• 掩码
• 权限控制
• 判断奇偶

例如：

x & 1

用于判断一个数字是否为奇数。

或（OR）

只要有一个 bit 为 1，结果就为 1。

异或（XOR）

两个 bit 不同则为 1，相同则为 0。

异或有几个非常重要的性质：

• a ^ a = 0
• a ^ 0 = a
• a ^ b ^ b = a

因此常用于：

• 简单加密
• 数据校验
• 交换变量

例如：

a = a ^ b;
b = a ^ b;
a = a ^ b;

可以在不使用临时变量的情况下交换两个值。