pointers - BigInt 和间接 : is it feasible to implement BigInt with pointer-arithmetic on the pointer, 对于小值？

Question

我假设一种语言的实现允许您将指针视为整数，包括对它们进行标准算术。如果由于硬件限制这是不现实的，请告诉我。如果编程语言通常没有这么强大的指针运算，但是在实践中是可行的，那么我仍然想知道这种实现BigInt的方法是否可行。

我确实没有任何低级编程经验 - 例如使用指针编程 - 编程，因此下面的许多假设可能是错误的。

---

问题: 据我所知，实现 BigInt(任意精度/大小整数)可以通过动态整数数组来完成，该数组根据需要而增长。那么数据结构可以表示为指向整数数组的指针。但是，假设指针是一个整数，就像数组中的整数一样，并且可以对该指针进行指针运算，那么简单地使用该指针来表示 BigInt 的值是否可行？这样就可以避免小整数值的间接寻址。

由于指针可以是指向整数数组的内存地址的真实指针，因此您必须有某种方式知道应该将其视为指针还是整数值。特别是因为它在 BigInt 的生命周期中发挥着作用。假设您通过将最高有效位设置为 1(如果指针确实是指针)来实现这一点，否则设置为 0。就它是一个整数而言，这似乎很简单:在对其进行任何操作之前检查是否设置为 1。如果不是，请对其进行任何算术，看看它是否溢出，如果溢出，则执行适当的操作。

但这有一个问题:指针是否使用其完整范围来指向内存地址？如果是这样，那么似乎没有任何方法可以使用任何位模式来区分整数和指针:每个位模式都是一个潜在的内存地址。将指针表示为有符号整数似乎是合理的，但在我看来，如果这使实现更简单，它们也可以表示为无符号整数。

所以，如果指针有符号；那么您似乎无法为此目的使用整数指针。如果是这样，将 BigInt 表示为具有两个成员的结构(或记录，如果需要)是否可行(即:与替代方案相比有效)；当 BigInt 的值很小时使用的指向数组和整数的指针？如果指向数组的指针为空，则使用整数。如果不是，则使用指向数组的指针并忽略结构中的 int。这会导致数据结构更加“臃肿”，但有时它可能有助于避免间接寻址，假设您不需要指向该结构的指针并且可以将其作为值传递。

另一个问题:实践中这样做了吗？

Answer 1

在 32 位机器上，指针的低两位几乎总是 0，因为地址是 32 位对齐的。同样，在 64 位机器上，低三位将为 0。

您可以利用这一事实来使用指针的最低有效位来标记它是否是数字。一种简单的选择是，如果 LSB 是数字，则将其设置为 1；如果是指针，则将 LSB 设置为 0。执行算术计算时，首先检查 LSB 以查看是否有指针或整数。如果它是 1，您可以将数字右移一位以获得真正的整数值，然后在计算中使用该值。如果它是 0，您只需沿着指针指向表示形式即可。

可以想象，您可以利用拥有 2 或 3 位空间的事实来编码更多可能的表示。例如，您可以让数字为整数、指向固定大小缓冲区的指针或指向可变大小缓冲区的指针，使用空闲指针位来编码您碰巧所处的情况。

希望这有帮助!