@TOC

前言

在计算机科学中，处理大整数（BigInt）是一项重要的任务，尤其是在密码学、科学计算和金融应用中。标准的整数类型在某些情况下可能不够用。例如，C语言中的 int 类型通常是 32 位的，可以表示的最大整数约为 2^31 - 1（2147483647）；long long 类型通常是 64 位的，可以表示的最大整数约为 2^63 - 1（9223372036854775807）。然而，这些范围对某些应用来说仍然不够。因此，我们需要自定义一种数据结构和算法来处理任意大小的整数，这就是 BigInt 的实现。

需要知道的是

在 C 语言中，最大的标准整数类型是 unsigned long long，它通常是 64 位的，可以表示的最大整数值为 2^64 - 1（18446744073709551615）。对于需要处理更大整数的应用，我们需要依赖自定义的 BigInt 实现或使用第三方库（如 GNU MP Library，GMP）。

在计算机中，负数通常使用一种叫做“二进制补码”（Two’s Complement）的方法来存储和表示。这种表示方法有几个优点，其中最主要的是它使得加法和减法操作在硬件电路中更加简便和统一。以下是二进制补码表示法的详细解释：

正负数在二进制中的表达

二进制补码表示法

正数表示

对于正数，二进制补码表示法与原始的二进制表示法是相同的。例如，8位二进制中：

• 5 的二进制表示是：0000 0101

负数表示

要表示一个负数，需要按照以下步骤进行：

1. 取反：将该数的正数形式的每一位取反，即0变为1，1变为0。
2. 加1：在取反的结果上加1。

以 -5 为例，展示如何使用 8 位二进制补码表示：

1. 正数形式：5 的二进制表示是：0000 0101
2. 取反：将 0000 0101 每一位取反，得到：1111 1010
3. 加1：在 1111 1010 上加 1，得到：1111 1011

所以，-5 的 8 位二进制补码表示是：1111 1011。

二进制补码的优点

1. 统一加法和减法运算：二进制补码的一个主要优点是加法和减法操作可以使用相同的硬件电路。例如，计算 A - B 可以转换为 A + (-B)，其中 -B 使用补码表示。
2. 唯一的零表示：二进制补码表示法避免了正零和负零两种表示，零的表示唯一且为全零（例如，8 位表示为 0000 0000）。
3. 简单的符号判断：最高位（最左边的一位）可以作为符号位，0 表示正数，1 表示负数。

举例说明

正数加负数

例如，计算 5 + (-3)：

1. 正数表示：5 的二进制表示为 0000 0101。
2. 负数表示：-3 的二进制补码表示为 1111 1101。
3. 相加：

  0000 0101
+ 1111 1101
-----------
  0000 0010

结果为 0000 0010，即 2，正确。

溢出问题

需要注意的是，使用固定位数（如 8 位、16 位等）时，可能会出现溢出问题。例如：

• 若使用 8 位存储，127 的二进制为 0111 1111，再加 1 会变为 1000 0000，表示 -128（溢出）。

总结而言，二进制补码表示法通过简单的位操作和统一的运算规则，使得负数的存储和运算在计算机硬件中高效且方便。

小数的二进制表示方法与整数的二进制表示类似，但需要注意小数点的位置。以下是小数在二进制中表示的一般步骤：

小数二进制

整数部分的二进制表示

1. 将整数部分除以2，记录商和余数。
2. 将商继续除以2，记录新的商和余数，直到商为0。
3. 将所有余数按逆序排列，即为整数部分的二进制表示。

小数部分的二进制表示

1. 将小数部分乘以2，记录结果的整数部分（0或1），作为二进制表示的小数部分的一位。
2. 将得到的新小数部分（忽略整数部分）继续乘以2，重复此过程。
3. 当小数部分变为0或达到所需的精度时，停止。

例子

整数部分：

以小数 (10.625) 为例，其整数部分是10。

• 10 ÷ 2 = 5，余数 0
• 5 ÷ 2 = 2，余数 1
• 2 ÷ 2 = 1，余数 0
• 1 ÷ 2 = 0，余数 1

所以，10的二进制表示是：(1010)。

小数部分：

其小数部分是0.625。

• 0.625 × 2 = 1.25，记录整数部分1
• 0.25 × 2 = 0.5，记录整数部分0
• 0.5 × 2 = 1.0，记录整数部分1

所以，0.625的二进制表示是：(0.101)。

综合

将整数部分和小数部分结合，得到 (10.625) 的二进制表示为：(1010.101)。

小数二进制表示注意事项

1. 有些小数在二进制中不能精确表示，可能会出现无限循环小数。例如，十进制的小数 0.1 的二进制表示是无限循环的 (0.00011001100110011…)。
2. 由于计算机存储限制，对于无限循环小数，只能取有限位数进行近似表示。

通过上述方法，可以将任意十进制小数转换为二进制表示。

总结

BigInt 的实现展示了如何在 C 语言中处理任意大小的整数。通过创建一个动态数组来存储整数的每一部分，并使用进位机制处理加法、减法、乘法和除法等基本运算，我们可以突破标准整数类型的限制。这种方法在高精度计算、加密算法和需要大数处理的领域中非常有用。尽管实现复杂且性能可能不如硬件支持的固定大小整数类型，但其灵活性和无限扩展性使得 BigInt 成为解决大数问题的有效工具。