4 ms·
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], n
by timerol 2y ago
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
- atq2119 2y agoUh, 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.
- mananaysiempre 2y ago> 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.