<story><title>That XOR Trick (2020)</title><url>https://florian.github.io/xor-trick</url></story><parent_chain><item><author>hyperman1</author><text>A fun party trick not mentioned here is reducing storage in a doubly linked-ish list:  Normally each node stores 2 pointers:  struct Node {void * prev;void * next}&lt;p&gt;The trick is to use only 1 &amp;#x27;pointer&amp;#x27;, storing prev XOR next:  struct Node {void* xored;}&lt;p&gt;While traversing, you remember not only the current position, but also where you came from.  So forward traversal goes: next= current.xored XOR previous.  Backwards also works: Node 
 * previous=(Node * )current.xored XOR (Node * ) next.&lt;p&gt;The first and last node can use 0 as previous or next node, or you make a circular list.  You do have to store a pointer to the first and last node, as usual.&lt;p&gt;I&amp;#x27;ve never seen this used in the real world, which is probably a good thing.  It also plays hell with garbage collectors like Boehm, as they can&amp;#x27;t derive the 2 used adresses.&lt;p&gt;UPDATE: And of course wikipedia knows everything: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;XOR_linked_list&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;XOR_linked_list&lt;/a&gt;</text></item></parent_chain><comment><author>svat</author><text>I looked up TAOCP (&lt;i&gt;The Art of Computer Programming&lt;/i&gt; by Knuth), and (unsurprisingly) this trick is mentioned there, and already by the time of the first edition this trick was folklore, with its origins lost to antiquity: the last exercise in section 2.2.4:&lt;p&gt;&amp;gt; &lt;i&gt;18. [25] Devise a way to represent circular lists inside a computer in such a way that the list can be traversed efficiently in both directions, yet only one link field is used per node. [&lt;/i&gt;Hint: &lt;i&gt;If we are given two pointers, to two successive nodes x_{i-1} and x_i, it should be possible to locate both x_{i+1} and x_{i-2}.]&lt;/i&gt;&lt;p&gt;Answer (in 1st edition [1968], second printing [1969]):&lt;p&gt;&amp;gt; &lt;i&gt;18. Let the link field of node x_i contain LOC{x_{i+1}) ⊕ LOC{x_{i-1}), where &amp;quot;⊕&amp;quot; denotes either subtraction or &amp;quot;exclusive or.&amp;quot; Two adjacent list heads are included in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)&lt;/i&gt;&lt;p&gt;The &amp;quot;either&amp;quot; is modified to &amp;quot;e.g.&amp;quot; in the 2nd edition [1973], and further slightly modified in 3rd edition ([1997], first digital release [December 2013]):&lt;p&gt;&amp;gt; &lt;i&gt;18. Let the link field of node x_i contain LOC(x_{i+1}) ⊕ LOC(x_{i−1}), where “⊕” denotes “exclusive or.” Other invertible operations, such as addition or subtraction modulo the pointer field size, could also be used. It is convenient to include two adjacent list heads in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)&lt;/i&gt;&lt;p&gt;With modern languages and compilers, even if doing these operations on your language&amp;#x27;s pointer type is implementation-defined&amp;#x2F;undefined behaviour as mentioned in some of the other comments, you can still use this trick with your own &amp;quot;pointers&amp;quot; (indexes in an array, as Knuth does in many of his programs: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;w&amp;#x2F;index.php?title=Pointer_(computer_programming)&amp;amp;oldid=990952393#Simulation_using_an_array_index&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;w&amp;#x2F;index.php?title=Pointer_(computer...&lt;/a&gt;), I guess.&lt;p&gt;Anyway, this gives me another point of appreciation about why the TAOCP series of books were so highly regarded: they were (are) encyclopedic and gathered&amp;#x2F;organized much of what was known at the time, in a highly compressed way (packed into exercises etc).</text></comment>
<story><title>That XOR Trick (2020)</title><url>https://florian.github.io/xor-trick</url></story><parent_chain><item><author>hyperman1</author><text>A fun party trick not mentioned here is reducing storage in a doubly linked-ish list:  Normally each node stores 2 pointers:  struct Node {void * prev;void * next}&lt;p&gt;The trick is to use only 1 &amp;#x27;pointer&amp;#x27;, storing prev XOR next:  struct Node {void* xored;}&lt;p&gt;While traversing, you remember not only the current position, but also where you came from.  So forward traversal goes: next= current.xored XOR previous.  Backwards also works: Node 
 * previous=(Node * )current.xored XOR (Node * ) next.&lt;p&gt;The first and last node can use 0 as previous or next node, or you make a circular list.  You do have to store a pointer to the first and last node, as usual.&lt;p&gt;I&amp;#x27;ve never seen this used in the real world, which is probably a good thing.  It also plays hell with garbage collectors like Boehm, as they can&amp;#x27;t derive the 2 used adresses.&lt;p&gt;UPDATE: And of course wikipedia knows everything: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;XOR_linked_list&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;XOR_linked_list&lt;/a&gt;</text></item></parent_chain><comment><author>surajrmal</author><text>The bigger problem with this approach is that you can&amp;#x27;t remove&amp;#x2F;erase something from the list just by knowing it&amp;#x27;s address. This is a key mechanism for most use cases. However, if you&amp;#x27;re fine with limiting yourself to erasing only during iteration, it&amp;#x27;s pretty nifty.&lt;p&gt;I&amp;#x27;ve also done some benchmarks in the past and found it interior iteration performance due to what I&amp;#x27;m assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it&amp;#x27;s not a big downside.</text></comment>