Rosetta Code talk:Village Pump/CS Pages Wanted

Swapping in a ring

XOR swap is limited to the modulus of 2ⁿ. A more general swap is based on addition and subtraction, or equivalently on addition and negative inverse in the ring. This one works for any modulus. Here is an example in Ada. Given <lang ada> type N is mod 5; -- Ring of 0,1,2,3,4 X, Y : N; </lang> Swap X and Y: <lang ada> X := X + Y; Y := X - Y; X := X - Y; </lang> 5 is not a power of two, yet it still works. --Dmitry-kazakov 09:14, 17 March 2009 (UTC)

Isn't the reason that the XOR swap works because integers are stored as binary and XOR will do a bitwise operation? I think the XOR one is better because not all languages have modulus types, but pretty much all languages (if not all) represent integers in binary (or can at least do bitwise operations on them as if they were binary). Maybe I'm missing the problem. --Mwn3d 18:54, 17 March 2009 (UTC)

There is no problem, except that they are two different mathematical structures. XOR works on a lattice. +/- does on a ring. When talking about numbers +/- is more general than XOR. Or better to say that XOR is illegal, because it is not an integer operation. XOR cannot be defined on integers. It can only be defined on modular rings of 2ⁿ. It is a language design hole which allows XOR for int in C. But it is OK for unsigned, because unsigned is not an integer, it is modular 2ⁿ. Furthermore, in a strongly typed language you might have no access to the representation of a number as an array of bits in order to be able to use it as a lattice. The could be no such. Consider X and Y represented by packed chain codes or character strings. They might have different length so that you simply won't be able to XOR their memory patterns. Yet +/- will perfectly work. --Dmitry-kazakov 21:48, 24 March 2009 (UTC)