[timerol]

Yes, but as mentioned in TFA, storing the difference would require an extra bit. The difference between two 32 bit numbers is in the range [-2^32 -1, 2^32-1], needing 33 bits to store. The XOR is the same size as the original pointer, simplifying data flow.

But even so, storing a doubly linked list with only pointer differences and no absolute pointers (other than head and tail) feels illegal too

[mananaysiempre]

> storing the difference [of prev and next pointers] would require an extra [sign] bit [relative to XOR]

No it wouldn’t. Just let wraparound happen normally and things will work out.

Effectively what you need are functions

  pair  : ptr × ptr → uintptr
  left  : uintptr × ptr → ptr
  right : ptr × uintptr → ptr
  
  left(pair(x, y), y) ≡ x
  right(x, pair(x, y)) ≡ y

Setting all three to XOR is one possibility. But

  pair(x, y)  = (x + y) mod 2^(width of ptr)
  left(p, y)  = (p - y) mod 2^(width of ptr)
  right(x, p) = (p - x) mod 2^(width of ptr)

is an equally valid one, because addition and subtraction modulo any fixed value are related in exactly the same way as normal addition and subtraction.

[atq2119]

Uh, no. Assuming 32-bit pointers, you'd add or subtract them using normal unsigned arithmetic which is modulo 2^32. Essentially the same trick definitely works because all these operations (adding/subtracting/xoring a number) are invertible.

The neat thing about xoring with a number is simply that that operation is its own inverse.