Ask HN: History of XOR Swapping | Hacker News Reader

Ask HN: History of XOR Swapping

6 pointskilodeca8 comments

Do you know about the first documented use of XOR to swap values of two variables?

I took a look in the EDSAC manual ("The Preparation of Programs for an Electronic Digital Computer", 1951) at https://archive.org/details/programsforelect00wilk/page/154/... - linking to the earliest popcount description, Gillies-Miller.

I didn't see anything.

Then again, that hardware doesn't seem to support xor. Nor does the manual mention "Boolean" or "Booleian" (the latter was used in the older literature, see https://scholar.google.se/scholar?hl=sv&as_sdt=0%2C5&q=Boole... for examples ).

I looked for, but didn't find, a description of it in HAKMEM (1972).

Those two exhaust my knowledge of reference materials for that era.

The earliest I've found so far is in "Introduction to PL360 programming" Guertin, Richard L, 1977 at https://www.slac.stanford.edu/spires/explain/manuals/PL360TX...

  |010|   IF R5 = R6 THEN                      |       CR  5,6          |
  |020|   BEGIN  | outer block |               |       BNE T.2          |
  |030|      EXTERNAL DATA BLANKS BASE R9;     |       L   9,=V(BLANKS) |
  |040|      PROCEDURE SWAP (R7);              |       B   T.1          |
  |050|      BEGIN  B2 := B2 XOR B3;           | SWAP  XC  0(4,2),0(3)  |
  |060|             B3 := B3 XOR B2;           |       XC  0(4,3),0(2)  |
  |070|             B2 := B2 XOR B3;           |       XC  0(4,2),0(3)  |
  |080|      END;  | of procedure |            |       BR  7            |
  |090|      B3 := B3 OR B9;   | main code |   | T.1   OC  0(4,3),0(9)  |
  |100|      SWAP;  | local procedure call |   |       BAL 7,SWAP       |
  |110|   END;  | of outer block |             | T.2   EQU *            |

Try the Retrocomputing StackExchange, by the way.

Here is smoething useful. I just randomly picked the IBM 704 (famous for early Lisp work) and researched the architecture. I found this site:

https://sky-visions.com/ibm/

It has info the 704 and other higher model numbers after that. Whereas no exclusive OR instruction is listed for the 704, it looks like 709 got one: opcode ERA, exclusive OR to accumulator. The 709 was introduced in 1957.

OK, we have identified a machine. Next we head to the Software Preservation Group for any code for the 709.

E.g. here is some code that uses ERA, but not for swapping:

http://www.softwarepreservation.org/projects/FORTRAN/source/...

Looks like ERA was popular in 709 systems sources as a comparison operator: load a value into A, then XOR with some constant, and if it's zero, there is a match. I've spotted quite a few uses like that.

The XOR swapping trick is possible since the earliest machine languages with memory to memory XOR operations (or, less simply, any XOR operation), so it's unlikely to be seriously documented until someone began teaching it.

Seems like an old interest.

I will ask an older friend when he first learned of it.

He said it was in college in the 70's. It was taught as a method for having a doubly linked list, but only use the space for one link. He thinks it was in an data structures book by hororwitz (not sure of spelling obviously)

Perhaps it was this book:

Horowitz, E., & Sahni, S. (1976). Fundamentals of data structures. Woodland Hills, Calif.: Computer Science Press.

https://www.worldcat.org/title/fundamentals-of-data-structur...

Here’s an online copy http://www.icodeguru.com/vc/10book/books/book1/chap04.htm

Search for ⟬a space saving device⟭

Related, XOR Swap Algorithm, https://en.m.wikipedia.org/wiki/XOR_swap_algorithm

Reply on news.ycombinator.com