Gui*_*ern 2 pointers data-structures
我假设一种语言的实现允许您将指针视为整数,包括对它们执行标准算术.如果由于硬件限制这是不现实的,请告诉我.如果编程语言通常没有这样强大的指针算法,但在实践中是可行的,那么我仍然想知道这种实现BigInt的方法是否可行.
我没有任何低级别的经验 - 例如,使用指针编程 - 编程,因此我在下面的许多假设可能都是错误的.
问:据我所知,实现BigInt - 任意精度/大小整数 - 可能是由动态的整数数组完成的,它会根据需要增长.然后,数据结构可以表示为指向整数数组的指针.但是,假设指针是一个整数,就像数组中的那个,并且可以对该指针进行指针运算,那么通过简单地使用该指针来表示BigInt的值是否可行？然后可以避免小值整数的间接.
由于指针可能是指向整数数组的内存地址的实际指针,因此您必须知道应将其视为指针或整数值.特别是因为它的作用是通过BigInt的生命周期.假设如果指针实际上是指针则将最高有效位设置为1来执行此操作,否则为0.就整数而言,这看起来很简单:在对它做任何事情之前检查是否设置为1.如果不是,那就特别做一些算法,看它是否有溢出,如果有的话,做适当的事情.
但这有一个问题:指针是否使用其全范围指向内存地址？如果是这样,那么似乎没有任何方法可以使用任何位模式来区分整数和指针:每个位模式都是潜在的存储器地址.将指针表示为有符号整数似乎是合理的,但在我看来,如果使得实现更简单,它们也可以表示为无符号整数.
所以,如果指针是签名的; 那么你似乎无法使用指针是整数,为此目的.如果是这样,将BigInt表示为具有两个成员的结构(或记录,如果需要),是否可行(即:与备选方案相比有效); 指向数组的指针和BigInt的值很小时使用的整数？如果指向数组的指针为null,则使用整数.如果没有,请使用指向数组的指针并忽略结构中的int.这使得一个更"膨胀"的数据结构,但它有时可能有助于避免间接,假设您不需要指向此结构的指针并可以将其作为值传递.
另一个问题:这是否在实践中完成？
在32位机器上,指针的低两位几乎总是0,因为地址是32位对齐的.同样,在64位机器上,低三位将为0.
你可以使用这个事实来使用指针中最不显着的位来标记它是否是数字.一个简单的选择是将LSB设置为1(如果它是数字),如果它是指针则设置为0.执行算术计算时,首先检查LSB以查看是否有指针或整数.如果它为1,则算术右移数字超过一位以获得实数整数值,然后在计算中使用该值.如果它为0,则只需按指向表示的指针即可.
您可以想象使用2或3位空间来编码更多可能的表示.例如,您可以将数字设置为整数,指向固定大小缓冲区的指针,或指向可变大小缓冲区的指针,使用空闲指针位来编码您碰巧遇到的情况.
希望这可以帮助!