Hacker News Reader

Comment by lmm | Hacker News Reader

> Instead of each node storing the next- and previous-pointers separately, store a single pointer which is the XOR of the two. Which is obviously an invalid pointer. But when iterating, XOR the previous node's pointer with the combined pointer to get the next node's pointer, and so on. You can iterate this way in both directions. Feels illegal. :)

Meh, it's not a pointer, it's not really any different from storing the difference between the two pointers, which obviously would let you iterate in both directions.

View on HN

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

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.

> 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.

One difference between XOR and difference is that because of the symmetry of XOR, you could use the same code for walking the list forwards and backwards.

Reply on news.ycombinator.com