51–60 of 69 posts
Earlier quoted context omitted.
You can do the same with addition/subtract. Perhaps there is a simpler way, but here is one way to do it: a = a + b b = b + a a = b - a b = b - 2*a
You have to take overflow into account. In most cases, that would make the algorithm not very useful compared to just doing the swap with a third variable.
Except that 2a, that might be trouble.
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…
However, the semantics differ from just using a temporary variable in that if a and b are in the same memory location then the result will be zero.
This was used in an entry for the underhanded C contest [1] if I remember correctly where for an implementation of RC4 the author defined the following macro.
#define SWAP(x, y) do { x^=y; y^=x; x^=y; }
"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.
Earlier quoted context omitted.
You have to take overflow into account. In most cases, that would make the algorithm not very useful compared to just doing the swap with a third variable.
Hm I don't think overflow will apply. Anything it does in an add will be undone by a subtract? Except that 2a, that might be trouble.
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…
You can do the same with addition/subtract. Perhaps there is a simpler way, but here is one way to do it: a = a + b b = b + a a = b - a b = b - 2*a
b = a - b
a = a - b
I think this works too, assuming a+b doesn't overflow.
Earlier quoted context omitted.
Hm I don't think overflow will apply. Anything it does in an add will be undone by a subtract? Except that 2a, that might be trouble.
Imagine you only had 4 bit numbers (range 0-15) and you tried to do swap 14, 15 (1110, 1111). You can do that with xor but not with the add method, because you can't store a + b without a wider variable.
14 - 15 gives 15
Earlier quoted context omitted.
Imagine you only had 4 bit numbers (range 0-15) and you tried to do swap 14, 15 (1110, 1111). You can do that with xor but not with the add method, because you can't store a + b without a wider variable.
15 + 15 gives 14 14 - 15 gives 15
Earlier quoted context omitted.
You can do the same with addition/subtract. Perhaps there is a simpler way, but here is one way to do it: a = a + b b = b + a a = b - a b = b - 2*a
a = a + b b = a - b a = a - b I think this works too, assuming a+b doesn't overflow.
> I think this works too, assuming a+b doesn't overflow.
Well, in two's complement arithmetic (as is used on most architectures), the intermediate overflow can be ignored, and it will work just fine.
Earlier quoted context omitted.
You can do the same with addition/subtract. Perhaps there is a simpler way, but here is one way to do it: a = a + b b = b + a a = b - a b = b - 2*a
You have to take overflow into account. In most cases, that would make the algorithm not very useful compared to just doing the swap with a third variable.
Another way to look at XOR - it's an adder (the sum, without the carry)
Yeah, surprised this wasn't mentioned; XOR as addition mod 2 (note that they're just talking about XOR here, not bitwise XOR) comes up way more often than it being the most complex binary boolean operation.