19 votes

XOR Swap Explained Visually

5 comments

  1. teaearlgraycold
    Link
    A redditor pointed out that GCC will convert the XOR swap code shown in the article into a normal swap: https://godbolt.org/z/0OUjzS

    A redditor pointed out that GCC will convert the XOR swap code shown in the article into a normal swap: https://godbolt.org/z/0OUjzS

    7 votes
  2. [2]
    Comment deleted by author
    Link
    1. Naethure
      Link Parent
      Wikipedia has a few good reasons where it could be useful: But in practice, it's not really used often, at least directly. The next section on that page has a few good reasons why, including that...

      Wikipedia has a few good reasons where it could be useful:

      • on a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes
      • in a region with high register pressure, it may allow the register allocator to avoid spilling a register
      • in microcontrollers where available RAM is very limited.
      • in cryptographic applications which need constant time functions to prevent time-based side-channel attack

      But in practice, it's not really used often, at least directly. The next section on that page has a few good reasons why, including that it's harder to read, is often not more efficient (especially on modern processors), and that check has to be performed to make sure you aren't swapping two pointers pointing to the same location.

      6 votes
  3. [3]
    Emerald_Knight
    Link
    For some reason I had a lot of trouble understanding the visualization intuitively. I keep wanting to see the black as 1 and the white as 0, likely because I want to see a base shape itself as...

    For some reason I had a lot of trouble understanding the visualization intuitively. I keep wanting to see the black as 1 and the white as 0, likely because I want to see a base shape itself as representing 1 and the background as 0, as opposed to the shapes effectively being cutouts. This isn't necessarily a criticism, as it's still an effective visualization, but perhaps a consideration for the future. My brain could also just be a screwy edge case. Nice work in any case!


    As a complement to the visualization, for the more mathematically- or textually-minded, let's consider some important rules:

    1. Any x ^ y where x == y will result in 0.
    2. Any x ^ 0 will result in x.
    3. XOR is associative, i.e. the terms can be grouped in any order and the result will be the same.

    Then we can see the stages of the XOR swap as follows:

    A'  := A ^ B
    B'  := A' ^ B  = (A ^ B) ^ B   = A ^ (B ^ B) = A ^ 0 = A
    A'' := A' ^ B' = (A ^ B) ^ (A) = B ^ (A ^ A) = B ^ 0 = B
    
    4 votes
    1. [2]
      teaearlgraycold
      Link Parent
      A few people have said that. But I'd need to use XNOR to get what you're expecting from A ^ B. I'm trying to keep it as a literal operation on a bitmap, rather than an abstract explanation. Maybe...

      A few people have said that. But I'd need to use XNOR to get what you're expecting from A ^ B. I'm trying to keep it as a literal operation on a bitmap, rather than an abstract explanation. Maybe if I swapped out white and black for two colors it wouldn't be confusing.

      2 votes
      1. Emerald_Knight
        Link Parent
        It looks like you're just operating on #ffffff and #000000 values to achieve this effect, so odds are a simple color swap would work, assuming I'm interpreting your source code correctly :)

        It looks like you're just operating on #ffffff and #000000 values to achieve this effect, so odds are a simple color swap would work, assuming I'm interpreting your source code correctly :)

        1 vote