最近我读了一篇文章,向我展示了如何使用单个指针字段实现双向链表,即像单向链表那样。它涉及将XOR prev和next地址存储在单个字段中。我不明白这如何帮助我们遍历前面和后面?有人能解释一下吗?我在这里阅读了该文章。有人能更详细地解释一下吗?XOR与这些地址有什么关系。
|0|A|0x01|<->|0x01|B|0x02|<->|0x02|C|0|
|A|0x01|<->|B|0x03|<->|C|0x03|
A.link = 0^0x01 = 0x01
B.link = 0x01^0x02 = 0x03
C.link = 0x03^0x0 = 0x03.
p=head;
prev = 0;
while(p.link!=prev)
{
next = p.link^prev
prev=p
p=next
}
是这样的:
你正在某个节点。你需要前往下一个节点。但你只有一个变量,需要存储两个指针的值。这可能吗?
我们利用了这样一个事实:当我们遍历列表时,我们知道先前访问的节点的地址。但是如何做到呢?
所以,问题归结为:
我们需要在单个变量中存储两个值。在任何时候,我们都知道其中任意一个。我们需要找到另一个。这可能吗?
答案是肯定的。
v = a^b;
then v^b = a and v^a = b
A B C
01 10 11 --->>this 01,10,11 are addresses.
A XOR B
或01 XOR 10
,即
01
xor 10
=11 i.e by doing xor of 01 and 10 it will make you reach at 11 address that is C.
类似地,当你执行10异或11时,答案是01,即A。
据我所知,这取决于异或运算符的属性,例如:
A XOR A = 0
当使用双向链表时,您必须在结构中保存“下一个”和“上一个”地址。作者说为了节省空间,您可以只存储:
next XOR prev
并通过执行以下操作来浏览列表:
next = current XOR prev
next = (next XOR prev) XOR prev
next = next XOR (prev XOR prev)
但我真的不明白这一点,因为在这个例子中,您仍然需要知道“prev”才能进行计算...
if (ptr)
评估为false,如果指针值是不确定的或者并非来自“适当”的分配函数或&-运算符)。通常在汇编语言级别上是通过这种方式来节省宝贵的字节。如今很少需要这样做了(通常用于嵌入式系统),而且使代码难以阅读和维护。好技巧,好传说,现在就忘了它吧 =P。 - WhozCraig