-4

Consider you have a processor with AND, OR, XOR, NOT and 2 registers X & Y. What is the smartest way to swap the values of the 2 registers?

Ted at ORCL.Pro
  • 1,602
  • 1
  • 7
  • 10
  • 1
    Not a relevant question because real CPUs always have MOV instructions as well as boolean. There may be rare cases where xor-swap is useful, but the fact that you had to invent a hypothetical CPU to make it the right answer kinda says something about how relevant it is in practice. – Peter Cordes Sep 27 '17 at 00:00
  • 1
    Modified versions of xor-swap where you AND with a mask mid-way through are interesting. You can swap some of the bits while leaving others in their original registers. – Peter Cordes Sep 27 '17 at 00:03
  • 1
    @peter - well in principle the "trick" could be useful on conventional CPUs even in the presence of MOV since you avoid using a temporary register. An example would be in a loop body where a pair of registers swap places every iteration. If there is a lot of register pressure, there might not be a free register for a MOV-swap. You can't just swap the roles in the assembly without unrolling the loop, which might be prohibitive if it is large. A generalization is register "rotation" where more than 2 registers swap places, and xor is useful here too. – BeeOnRope Sep 27 '17 at 00:32
  • 1
    @BeeOnRope: That's one of the "rare cases" I had in mind, yeah. Not really relevant on x86 where `xchg reg,reg` is better in almost every way than a xor-swap (and [always at least as good as 3 `mov`s with a hidden temporary](https://stackoverflow.com/questions/45766444/why-is-xchg-reg-reg-a-3-micro-op-instruction-on-modern-intel-architectures), except for lack of mo-elimination). (Maybe some odd case on some CPUs where a 3-uop instruction is worse than multiple insns.) Could be useful for XMM regs I guess, but yuck. May be better to spill/reload. – Peter Cordes Sep 27 '17 at 00:44
  • 1
    Could also be useful on ARM or something, especially in 16-bit-instruction mode (like ARM Thumb or MIPS16) where only a limited set of registers are general-purpose. I think with 16 or 32 GP regs available, it's unlikely to be better than just spilling something else. – Peter Cordes Sep 27 '17 at 00:47
  • 1
    Yes, I ran out of characters to mention xchg, but safe to say it's not available in most common instruction sets which are all more RISCy. I had thought that in the rotate case it might be useful even on x86, but [probably not](https://stackoverflow.com/q/27688797/149138). @pe – BeeOnRope Sep 27 '17 at 00:48
  • 1
    @BeeOnRope: I suppose xor-swap is still relevant on microcontrollers where there's no difference between an ALU instruction and a move, and it's all just instruction throughput (latency and dependency chains are only possibly relevant for memory). re: rotation with more than 2 vars: yeah that's what I thought. The more variables you have, the bigger a win it is to just spill/reload something and use independent move instructions. – Peter Cordes Sep 27 '17 at 02:53
  • Thank you all for your comments, I was just trying to get my student badge here at stack overflow since I am niewbie. the 3 xor solution is one of my favourite tricky exam questions back in the 80s – Ted at ORCL.Pro Sep 27 '17 at 04:24
  • 2
    @TedatORCL.Pro While your pursuit is noble, nobody really profits from having duplicates of existing questions posted. A good way to answer your own question is to post a Q&A for a problem you recently solved. – fuz Sep 27 '17 at 08:26
  • @fuz sorry for the disruption, I am new to stack overflow and trying to find my feet. Hope the learning curve will be less steep in the coming days and weeks. Thanks! – Ted at ORCL.Pro Sep 27 '17 at 18:33
  • 2
    @TedatORCL.Pro A good way to get started is to find a tag you are interested in, open the page `http://stackoverflow.com/questions/tagged/` and start to answer questions. This way, you can learn how this site works while helping other people with your answers. – fuz Sep 27 '17 at 19:13
  • @fuz I do that for #oracle and #sql thanks. A quick glance at my profile will answer all your questions. As mentioned all I wanted to get my student badge – Ted at ORCL.Pro Sep 27 '17 at 19:23

1 Answers1

1
X := X XOR Y
Y := Y XOR X
X := X XOR Y
Ted at ORCL.Pro
  • 1,602
  • 1
  • 7
  • 10