41–50 of 69 posts
Earlier quoted context omitted.
This also works with `sub` instead of xor. This code (xor swap, sub swap) should nevertheless better not be used on a modern CPU since it can badly be pipelined.
I think you mean a combination of sub and add (e.g. sub sub add). xor is somewhat special in that it is its own inverse.
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…
I have a similar memory from my early days of coding. I was implementing a toy rc4 cipher. One of the steps in the ciphers involves swapping entries in an arrays of 256 elements. I thought "hey, I'm a 1337 coder, I'm going to use the xor trick". Except it doesn't work if you're trying to swap something with itself. If you do "a[i] ^= a[j]" and i == j then you're just clearing the entry. Taught me the valuable lesson…
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…
This also works with `sub` instead of xor. This code (xor swap, sub swap) should nevertheless better not be used on a modern CPU since it can badly be pipelined.
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…
a = a + b
b = b + a
a = b - a
b = b - 2*aOne thing I love about xor is an interesting correspondence between bitwise xor and the outer product of the exterior algebra. Say we have an N=4 dimensional vector space, and we use binary place values to represent units vector in a basis, like this: w = 1000 x = 0100 y = 0010 z = 0001 Then a multivector basis could be represented e.g.: xyz = 0111 xy = 0110 wz = 1001 Now, if ^ is the outer product: xy^yz = xz ↔ 0110…
https://sourceforge.net/projects/g25/?source=directory
The XOR trick is close to slide 16 of http://www.science.uva.nl/research/ias/ga/gaigen/files/20020...
...
How to compute the geometric product of unit orthogonal basis blades (3/3) If we represent each basis vector with a specific bit in a binary number (e1 = 001b, e2 = 010b, e3 = 100b), computing the geometric product of basis blades is exactly the xor operation on binary numbers!
(e1^e2)(e2^e3) = e1^e3
011b xor 110b = 101b
- basis vectors have to be rearranged into a specific order before they can annihilate each other (this rearranging causes a sign change in the result). This can also be computed binary. - signature of annihilated basis vectors can change the sign as well.
> most programming languages don’t have an explicit “logical operator” for it I guess the author never taught of != . The only thing to be careful with is that it doesn't implicitly convert arguments to boolean, so expressions like " != (flags & Flag)" will go wrong without an explicit conversion "bool(flags & Flag)" or equivalent expression like "((flags & Flag) != 0)". And let's not forget about the friend, ==. I'v…
!!a != !!b also works, but that's unwieldy. I think maybe part of the reason is that usually you're also doing something with the value of the lhs or rhs, so you end up having to separate the cases anyway: if (a && !b) { frob(a); } else if (b && !a) { twiddle(b); } else { panic(); }
!a != !b
Earlier quoted context omitted.
This also works with `sub` instead of xor. This code (xor swap, sub swap) should nevertheless better not be used on a modern CPU since it can badly be pipelined.
Yes, in fact compilers these days are smart enough to convert people's xor swaps into mov swaps: https://godbolt.org/g/FYv7xQ
mov eax, edi
mov edi, esi
mov esi, eax
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
Earlier quoted context omitted.
Yes, in fact compilers these days are smart enough to convert people's xor swaps into mov swaps: https://godbolt.org/g/FYv7xQ
When I look at the generated code that multiple of the compilers (gcc,clang,icc) generate mov eax, edi mov edi, esi mov esi, eax I would intuitively use the `xchg` instruction that x86-32/x86-64 provides instead. Is there a specific reason why the compiler(s) decide to generate the mentioned code instead?