36 ms·

Swapping two variables without a temporary using xor.

by fegu 4y ago

Turing_Machine 4y ago
https://en.wikipedia.org/wiki/XOR_swap_algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm
nicklaf 4y ago
Also: zeroing a register by XORing it with itself.
- Am4TIfIsER0ppos 4y ago
  Setting a register to all ones by comparing with itself. Much less needed but I've done it a few times.
bob1029 4y ago
C# as of 7.0 makes this possible: (a, b) = (b, a);
- sicp-enjoyer 4y ago
  How is it implemented?
  - Ferrotin 4y ago
    Generally speaking it will get compiled to something like SSA form and the outcome depends on the overall dataflow and what optimizations happen.
    - valleyer 4y ago
      Aw, that's an unsatisfying answer! I'm a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick. https://godbolt.org/z/jhzqxEKzT https://godbolt.org/z/jhzqxEKzT Maybe I need some extra compiler flags or something.
      - moonchild 4y ago
        The xor trick has no practical value. Sorry.
        sicp-enjoyer 4y ago
        I agree it isn't normally helpful on a modern computer, but that's a strong statement. What if you need to swap large storage spaces with no extra memory? Isn't there still old hardware out there especially in aerospace that could benefit?
        lscharen 4y ago
        It was useful in single accumulator processor architectures since it could avoid one memory store.
      - Ferrotin 4y ago
        That would just load each global variable into registers and write them back to memory, swapping them. If the compiler had decided to put two locals located already in registers, and had the swap in a branch, like so: if (foo()) { bar(); (a, b) = (b, a); } Then the registers might get swapped with an xchg instruction or something, I don’t know. The compiler’s goal is to have pipelined execution be as fast as possible, so there’s no way it’s going to use bit-mangling operations that would get in the way of that.
      - Someone 4y ago
        > I’m a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick. It better not. The CLR trick introduces a data dependency that slows down the code on modern CPUs. Compilers sometimes also can compile this down to zero instructions. Nothing says the variable-to-register mapping has to be constant in a single function.
- throwamon 4y ago
  It's been possible in other languages for ages, and some of them don't even require parentheses or a semicolon!
djmips 4y ago
humble brag. I had that on an interview once and I'd never heard of the technique but somehow a inspiration from the heavens and I was able to invent it on the spot. Sometimes knowing something is possible is a great motivator (plus the time pressure of the interview) But I guess what really happened is that when you come up writing assembly code at a low level it's a lot more obvious when you've been neck deep in bits, shifts, and logic ops all day.

Swapping two variables without a temporary using xor.

by fegu 4y ago

Swapping two variables without a temporary using xor.

Turing_Machine 4y ago

https://en.wikipedia.org/wiki/XOR_swap_algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm

nicklaf 4y ago

Also: zeroing a register by XORing it with itself.

Am4TIfIsER0ppos 4y ago
Setting a register to all ones by comparing with itself. Much less needed but I've done it a few times.

bob1029 4y ago

C# as of 7.0 makes this possible: (a, b) = (b, a);

sicp-enjoyer 4y ago
How is it implemented?
- Ferrotin 4y ago
  Generally speaking it will get compiled to something like SSA form and the outcome depends on the overall dataflow and what optimizations happen.
  - valleyer 4y ago
    Aw, that's an unsatisfying answer! I'm a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick. https://godbolt.org/z/jhzqxEKzT https://godbolt.org/z/jhzqxEKzT Maybe I need some extra compiler flags or something.
    - moonchild 4y ago
      The xor trick has no practical value. Sorry.
      - sicp-enjoyer 4y ago
        I agree it isn't normally helpful on a modern computer, but that's a strong statement. What if you need to swap large storage spaces with no extra memory? Isn't there still old hardware out there especially in aerospace that could benefit?
      - lscharen 4y ago
        It was useful in single accumulator processor architectures since it could avoid one memory store.
    - Ferrotin 4y ago
      That would just load each global variable into registers and write them back to memory, swapping them. If the compiler had decided to put two locals located already in registers, and had the swap in a branch, like so: if (foo()) { bar(); (a, b) = (b, a); } Then the registers might get swapped with an xchg instruction or something, I don’t know. The compiler’s goal is to have pipelined execution be as fast as possible, so there’s no way it’s going to use bit-mangling operations that would get in the way of that.
    - Someone 4y ago
      > I’m a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick. It better not. The CLR trick introduces a data dependency that slows down the code on modern CPUs. Compilers sometimes also can compile this down to zero instructions. Nothing says the variable-to-register mapping has to be constant in a single function.
throwamon 4y ago
It's been possible in other languages for ages, and some of them don't even require parentheses or a semicolon!

djmips 4y ago

humble brag. I had that on an interview once and I'd never heard of the technique but somehow a inspiration from the heavens and I was able to invent it on the spot. Sometimes knowing something is possible is a great motivator (plus the time pressure of the interview) But I guess what really happened is that when you come up writing assembly code at a low level it's a lot more obvious when you've been neck deep in bits, shifts, and logic ops all day.