c - 大整数算术

Question

我想知道用于在 C 中对非常大的整数执行算术运算的不同技术。我知道的一种技术是使用字符串来保存一个数字并为其定义操作加法、减法等。我对使用图书馆不感兴趣，这个问题纯粹是为了知识。请建议使用的任何其他此类方法/技术。

Answer 1

您可以像将整数表示为字节数组一样低级，并像 CPU 一样在字级别执行所有操作（如加法、减法、乘法、除法或比较）。

最简单的算法是加法和减法，您只需按顺序添加或减去数字，并根据需要携带。

负数可以用 2 的补码表示。

为了比较，您只需比较高位数字，直到发现差异。

对于乘法，您可以实现的最直接的算法（也是最慢的）是重复加法。

对于除法，事情比乘法复杂一点，请参阅：http ://en.wikipedia.org/wiki/Division_algorithm

一个常见的应用是公钥密码学，其算法通常使用具有数百位数字的整数的算术运算。

为此检查 OpenSSL BIGNUM 文档：https ://www.openssl.org/docs/crypto/bn.html

Answer 2

您可以使用 3 个链表，一个用于数字 A，一个用于数字 B，一个用于结果。

然后，您将读取每个数字作为用户输入的字符，将其设为整数并将其保存到列表中的新节点，与您当前读取的数字相对应。

最后，您只需将加法、减法等操作编写为函数。在每种方法中，您都将遵循您在学校学习的各自算法，从 LSB 节点开始，一直到 MSB 节点，始终牢记每个数字（1 个节点 * 10^0, 2 个节点 * 10^1, 3 个节点 * 10^2, ...,n 个节点 * 10^n）。