> 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.
No it wouldn’t. Just let wraparound happen normally and things will work out.
Effectively what you need are functions
Setting all three to XOR is one possibility. But 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.