Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Three Ways of XOR

horia141.com

Post reply on HN
Print view View original

31–40 of 69 posts

Re: The Three Ways of XOR

#31

Post by cyberferret »

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR.

I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to disk or clobber other free RAM segments. It is simply:

  a = a xor b
  b = b xor a
  a = a xor b
Three steps, same as using a placeholder 'c' variable. I think he mentioned on most of the processors of the time, 3 XOR instructions actually worked faster than 3 MOV instructions.

Illustration for the non-believers:

  a = 10010110
  b = 01100011

  a = a xor b

  a = 11110101
  b = 01100011 (unchanged)

  b = b xor a

  a = 11110101 (unchanged)
  b = 10010110

  a = a xor b

  a = 01100011
  b = 10010110
Voila!

Re: The Three Ways of XOR

#32

Post by louthy »

cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

Yep, that's the 'classic' usage for me. Used to use this all the time if registers were short (and they always were).

Re: The Three Ways of XOR

#33

Post by di4na »

_0ffh wrote: post #17

"Sadly XOR doesn’t appear as an equivalent to NOT, AND and OR, as a logical operator on booleans, being relegated to just a bitewise operator in most programming languages." Well, in C there's just no need. The main raison d'etre for && and || over & and | is that you can exploit their short circuiting behaviour. A hypothetical ^^ operator wouldn't bring anything extra to the table.

The real problem is that you can not short circuit with XOR.

Re: The Three Ways of XOR

#34

Post by jonsen »

SonOfLilit wrote: post #29
makecheck wrote: post #23

The last statement in the article is technically a hardware decision (the article says: “As an extra treat, XOR can be considered an imparity function. When its input has an even number of zeros, the output is zero. Otherwise it is one.”). While 2-input XOR behaves as “one or the other but not both”, a many-input gate is generally implemented by chaining other XORs and the chaining causes even/odd parity instead of a…

It's not "just an implementation decision"[1], it's a reasonable mathematical definition: for a binary operator OP, we define it's n-parameter version whenever a OP (b OP c) == (a OP b) op c, which is true for XOR but not e.g. for XNOR (F == F) == T is F, but F == (F == T) is T. [1] and sorry if I'm falling victim to the difficulty of interpreting tone on the internet

By symmetry it must be true for XNOR also, and:

  (F == F) == T in fact is T

Re: The Three Ways of XOR

#35

Post by wolfgke »

cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

This also works with `sub` instead of xor. This code (xor swap, sub swap) should nevertheless better not be used on a modern CPU since it can badly be pipelined.

Re: The Three Ways of XOR

#36

Post by eutectic »

wolfgke wrote: post #35
cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

This also works with `sub` instead of xor. This code (xor swap, sub swap) should nevertheless better not be used on a modern CPU since it can badly be pipelined.

I think you mean a combination of sub and add (e.g. sub sub add). xor is somewhat special in that it is its own inverse.

Re: The Three Ways of XOR

#37

Post by eutectic »

cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

I like to think about this algebraically:

    a1 = a0 ^ b0
    b1 = b0 ^ a1 = b0 ^ (a0 ^ b0) = (a0 ^ b0) ^ b0 = a0
    a2 = a1 ^ b1 = (a0 ^ b0) ^ a0 = (b0 ^ a0) ^ a0 = b0
The xor-linked list (https://en.wikipedia.org/wiki/XOR_linked_list) is another neat idea along the same theme.

Re: The Three Ways of XOR

#38

Post by [deleted] »

di4na wrote: post #33
_0ffh wrote: post #17

"Sadly XOR doesn’t appear as an equivalent to NOT, AND and OR, as a logical operator on booleans, being relegated to just a bitewise operator in most programming languages." Well, in C there's just no need. The main raison d'etre for && and || over & and | is that you can exploit their short circuiting behaviour. A hypothetical ^^ operator wouldn't bring anything extra to the table.

The real problem is that you can not short circuit with XOR.

[deleted]

Re: The Three Ways of XOR

#39

Post by simias »

cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

I have a similar memory from my early days of coding.

I was implementing a toy rc4 cipher. One of the steps in the ciphers involves swapping entries in an arrays of 256 elements. I thought "hey, I'm a 1337 coder, I'm going to use the xor trick".

Except it doesn't work if you're trying to swap something with itself. If you do "a[i] ^= a[j]" and i == j then you're just clearing the entry.

Taught me the valuable lesson that I shouldn't try to be a smartass while writing code and the importance of unit tests.

Re: The Three Ways of XOR

#40

Post by cyberferret »

simias wrote: post #39
cyberferret wrote: post #31

Very early on in my computing career (nearly 40 years ago now), I remember being blown away when an older IBM Systems 360 programmer showed me how you can swap the values of two variables over WITHOUT using a third placeholder variable by using pure XOR. I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to di…

I have a similar memory from my early days of coding. I was implementing a toy rc4 cipher. One of the steps in the ciphers involves swapping entries in an arrays of 256 elements. I thought "hey, I'm a 1337 coder, I'm going to use the xor trick". Except it doesn't work if you're trying to swap something with itself. If you do "a[i] ^= a[j]" and i == j then you're just clearing the entry. Taught me the valuable lesson…

Nice catch - I hadn't though about in-place swap situations. I have always used this trick to switch two variables, but yes, I can see when you are talking about lists and matrix array manipulation, you can easily encounter an edge case which necessitates an 'in place' swap which would fail under these circumstances.
Post reply on HN