djones@megatest.UUCP (Dave Jones) (01/23/88)
SWARBRICK FRANCIS JOHN writes: > > #define swap(a,b) ((a) = ((b) = ((a) = (a) ^ (b)) ^ (b)) ^ (a)) > > Try that, and tell me what you think. A super-genius friend of mine figured > it out. He says it will work for anything (int, char *, etc.). But it > sure boggles my mind... > Of course, I can't be sure, but I rather suspect that your super-genius friend may have been just a little lax about attributing sources. I found out about the XOR trick in 1979, but it is much older. I don't know who, if anybody, is credited with having discovered it first. In lay-hacker's terms, the reason it works is that A ^ B works like a "diff" file. It sets a bit in each position where A and B differ. Thus if you have A and (A^B) sitting around, you can recover B. And guess what? The XOR also acts like "sed" in recovering the old value from the new value and the diff. Mathematically speaking, for all (A,B) in 0..1 X 0..1 (A^B)^A = B There are only four cases to verify. Check it out. PUZZLE for those lucky enough not to have seen it previously: How can you use the XOR trick to keep a doubly linked list, using only one field for in each record, to code for finding both the following and the previous record? (Please do not post solutions to the net. If you can't get it and want the spoiler, send me email directly, and I'll be happy to spoil it.) Have fun XORing. Dave Jones Megatest Corp. 880 Fox Lane San Jose, CA. 95131 (408) 437-9700 Ext 3227 UUCP: ucbvax!sun!megatest!djones ARPA: megatest!djones@riacs.ARPA
eichin@athena.mit.edu (Mark W. Eichin) (01/24/88)
In article <226@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >PUZZLE for those lucky enough not to have seen it previously: > >How can you use the XOR trick to keep a doubly linked list, using only >one field for in each record, to code for finding both the following and >the previous record? I recall seeing an article in BYTE about five years back on using this for a floppy disk file management technique... I think the suggestion was to keep it as an extra pointer to recover from, but from a given record you could always find the `next' record. Anybody recall the reference in more detail? Mark Eichin <eichin@athena.mit.edu> SIPB Member & Project Athena ``Watchmaker'' Mark Eichin <eichin@athena.mit.edu> SIPB Member & Project Athena ``Watchmaker''
bader+@andrew.cmu.edu (Miles Bader) (01/25/88)
> How can you use the XOR trick to keep a doubly linked list, using only > one field for in each record, to code for finding both the following and > the previous record? To make it a bit clearer, you have to be able to find the NEXT record given the current and previous records, and find the PREVIOUS record given the current and the next record.
pl@tut.fi (Pertti Lehtinen) (01/29/88)
There was articles about XOR-chaining on DDJ last year (actually two articles). Unfortunately I don't have those numbers now at hand, so it is impossible to actual volumes. Pertti Lehtinen pl@tut.fi -- pl@tut.fi ! All opinions expressed above Pertti Lehtinen ! are preliminary and in subject N 61 26' E 23 50' ! to change without any further notice.
clay@oravax.UUCP (McFarland) (01/30/88)
In article <cVyaqyy00jaBF6M0=4@andrew.cmu.edu> bader+@andrew.cmu.edu (Miles Bader) writes: >> How can you use the XOR trick to keep a doubly linked list, using only >> one field for in each record, to code for finding both the following and >> the previous record? > >To make it a bit clearer, you have to be able to find the NEXT record >given the current and previous records, and find the PREVIOUS record >given the current and the next record. To make it a bit clearer all you have to do is XOR it with itself :-} Of more interest, since you can store n things in a register and get any of them back given the other n-1 you can store NEXT ^ PREVIOUS ^ KEY and keep the KGB from deciphering your linked lists (Now where did I put that key...). Clay Brooke-McFarland Odyssey Research Associates --------------------------------------------------------------| "Wait! There's something we're all overlooking!" Chorus: "What| is it, Doctor?" "I don't know. I'm overlooking it myself." | --------------------------------------------------------------|