Hacker News Reader

Comment by timerol | Hacker News Reader

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

View on HN

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

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.

Reply on news.ycombinator.com