News for hackers. Stuff that matters.
Re:The Three Ways of XOR by ambrop7 on Sunday February 12, 2017 @05:13PM (#13631305)
> most programming languages don’t have an explicit “logical operator” for it

I guess the author never taught of <boolean> != <boolean>. The only thing to be careful with is that it doesn't implicitly convert arguments to boolean, so expressions like "<boolean> != (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've more than once seen code like "(a && b) || (!a && !b)".

A similar interesting pattern many don't think of is "bool(a1) + ... + bool(aN) == M" (particularly with M==1) and instead we see unreadable monstrosities :)

Re:The Three Ways of XOR by im3w1l on Monday February 13, 2017 @12:49AM (#13633385)
If you only want to convert the second argument you can use the ==! operator ;)
Re:The Three Ways of XOR by wruza on Monday February 13, 2017 @11:27AM (#13636474)
C has so many wonderful operators, why don't people use them?

  while (x --> 0) x goes to zero;
  while (0 <---- x) goes much faster on some compilers (ymmv);
Re:The Three Ways of XOR by andreareina on Monday February 13, 2017 @02:38AM (#13633721)
!!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(); }
Re:The Three Ways of XOR by caf on Monday February 13, 2017 @08:06AM (#13634916)
You don't need to double-negate,

  !a != !b
is sufficient.
Re:The Three Ways of XOR by TazeTSchnitzel on Sunday February 12, 2017 @07:22PM (#13632097)
> The only thing to be careful with is that it doesn't implicitly convert arguments to boolean

Well, you could also use bitwise XOR in that case.

Re:The Three Ways of XOR by kevinwang on Sunday February 12, 2017 @05:30PM (#13631413)
Is "bool(a1) + ... + bool(aN) == M" not just "a1 || a2...||an"?
Re:The Three Ways of XOR by kmill on Sunday February 12, 2017 @05:35PM (#13631446)
No, it's true when exactly M are true. "a1 || a2 || ... || an" is true when at least one is true.

The latter is the same as "a1 + ... + an == 1 || a1 + ... + an == 2 || ... || a1 + ... + an == n".

Re:The Three Ways of XOR by Ded7xSEoPKYNsDd on Sunday February 12, 2017 @06:01PM (#13631649)
So your + operator implicitly casts booleans to an integer type, with false=0 and true=1?
Re:The Three Ways of XOR by kmill on Sunday February 12, 2017 @06:26PM (#13631811)
What you are saying is the only way I can imagine to interpret what I wrote, if one assumes I was intending to make any sense.

By the way, in Python, bool is a subtype of int (i.e., instanceof(True,int) == True), and True + True == 2. C is the same, and in Javascript booleans are converted to integers for arithmetic operations.

Re:The Three Ways of XOR by OJFord on Sunday February 12, 2017 @07:52PM (#13632253)
> What you are saying is the only way I can imagine to interpret what I wrote

One might imagine it (without experience, or not thinking, of any particular programming language) as being a logical OR on Booleans - which in EE at least is frequently written '+'.

Re:The Three Ways of XOR by simcop2387 on Sunday February 12, 2017 @06:18PM (#13631765)
In c++, yes. Not every language will do that though.
Re:The Three Ways of XOR by ambrop7 on Sunday February 12, 2017 @05:33PM (#13631435)
Obviously no, the first (for M==1) means exactly one is true, the latter at least one is true. But a1||...||aN is equivalent to bool(a1)+...+bool(aN)>0 (assuming no integer overflow :).
Re:The Three Ways of XOR by Existenceblinks on Sunday February 12, 2017 @09:48PM (#13632782)
> "(a && b) || (!a && !b)"

It is XNOR, not XOR (no pun intended)

Boolean algebra laws excellently help if there are many input aN. I used to use it to simplify legacy ruby codes written by c-style programmer (you can imagine how the conditions look like)

Re:The Three Ways of XOR by cyberferret on Monday February 13, 2017 @04:15AM (#13634065)
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 disk or clobber other free RAM segments. It is simply:

  a = a xor b
  b = b xor a
  a = a xor b
Three steps, same as using a placeholder 'c' variable. I think he mentioned on most of the processors of the time, 3 XOR instructions actually worked faster than 3 MOV instructions.

Illustration for the non-believers:

  a = 10010110
  b = 01100011

  a = a xor b

  a = 11110101
  b = 01100011 (unchanged)

  b = b xor a

  a = 11110101 (unchanged)
  b = 10010110

  a = a xor b

  a = 01100011
  b = 10010110
Voila!
Re:The Three Ways of XOR by onlydnaq on Monday February 13, 2017 @08:39AM (#13635066)
This is a classic trick, and as you write could be used for performance benefits in the old day.

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; }
And used it for swapping the values in the substitution table for the cipher, e.g. SWAP(S[i], S[j]). The weakness was that since sometimes the indices are the same in RC4 the substitution table would be gradually replaced with zeroes.

[1] http://www.underhanded-c.org/_page_id_16.html

Re:The Three Ways of XOR by eutectic on Monday February 13, 2017 @05:39AM (#13634356)
I like to think about this algebraically:

    a1 = a0 ^ b0
    b1 = b0 ^ a1 = b0 ^ (a0 ^ b0) = (a0 ^ b0) ^ b0 = a0
    a2 = a1 ^ b1 = (a0 ^ b0) ^ a0 = (b0 ^ a0) ^ a0 = b0
The xor-linked list (https://en.wikipedia.org/wiki/XOR_linked_list) is another neat idea along the same theme.
Re:The Three Ways of XOR by simias on Monday February 13, 2017 @06:22AM (#13634509)
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 that I shouldn't try to be a smartass while writing code and the importance of unit tests.

Re:The Three Ways of XOR by taejo on Monday February 13, 2017 @07:43AM (#13634818)
This was the basis of an excellent entry [0] in the 2007 Underhanded C Contest. It had a correct implementation of the RC4 encryption algorithm, except it used the XOR swap, so on average one byte of the pseudorandom state was zeroed every 256 iterations. Eventually, the state is all zeroes, and the encryption just outputs pure plaintext. Best of all, the first few kilobytes of output looks random at first glance.

[0] http://www.underhanded-c.org/_page_id_16.html

Re:The Three Ways of XOR by cyberferret on Monday February 13, 2017 @06:44AM (#13634582)
Nice catch - I hadn't though about in-place swap situations. I have always used this trick to switch two variables, but yes, I can see when you are talking about lists and matrix array manipulation, you can easily encounter an edge case which necessitates an 'in place' swap which would fail under these circumstances.
Re:The Three Ways of XOR by amelius on Monday February 13, 2017 @08:01AM (#13634897)
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
Re:The Three Ways of XOR by mcintyre1994 on Monday February 13, 2017 @09:07AM (#13635250)
a = a + b

b = a - b

a = a - b

I think this works too, assuming a+b doesn't overflow.

Re:The Three Ways of XOR by amelius on Monday February 13, 2017 @09:28AM (#13635396)
Good one.

> 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.

Re:The Three Ways of XOR by Sacho on Monday February 13, 2017 @08:19AM (#13634973)
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.
Re:The Three Ways of XOR by amelius on Monday February 13, 2017 @09:31AM (#13635420)
In two's complement arithmetic, you are basically computing modulo N (N = 2 to the power of the number of bits). So overflow will not interfere with the swap operation.
Re:The Three Ways of XOR by JoeAltmaier on Monday February 13, 2017 @08:24AM (#13634993)
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.

Re:The Three Ways of XOR by mcintyre1994 on Monday February 13, 2017 @09:05AM (#13635231)
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.
Re:The Three Ways of XOR by jonsen on Monday February 13, 2017 @09:22AM (#13635353)
15 + 15 gives 14

14 - 15 gives 15

Re:The Three Ways of XOR by mcintyre1994 on Monday February 13, 2017 @09:27AM (#13635382)
The way I wrote this was rubbish, edited. I was trying to get at if you have 1110, 1111 then 1110 + 1111 will overflow, but you could xor them.
Re:The Three Ways of XOR by jonsen on Monday February 13, 2017 @09:47AM (#13635571)

  1110 + 1111 = 1101
  1101 - 1110 = 1111
  1101 - 1111 = 1110
Overflow doesn't matter if you just want to swap.
Re:The Three Ways of XOR by Sacho on Monday February 13, 2017 @11:27AM (#13636476)
(Assuming two's complement arithmetic, as amelius pointed out - I don't know if all programming languages and platforms use it)
Re:The Three Ways of XOR by mcintyre1994 on Monday February 13, 2017 @04:18PM (#13638860)
That's a really smart observation I hadn't made, thanks for explaining!
Re:The Three Ways of XOR by wolfgke on Monday February 13, 2017 @05:26AM (#13634317)
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.
Re:The Three Ways of XOR by Khoth on Monday February 13, 2017 @07:45AM (#13634826)
Yes, in fact compilers these days are smart enough to convert people's xor swaps into mov swaps: https://godbolt.org/g/FYv7xQ
Re:The Three Ways of XOR by wolfgke on Monday February 13, 2017 @08:17AM (#13634960)
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?
Re:The Three Ways of XOR by Someone on Monday February 13, 2017 @12:13PM (#13636872)
When used to swap with data in memory, the reason is that it is faster. xchg is atomic. To do that, it implicitly locks its target address. That makes it slower than the series of moves. http://www.agner.org/optimize/instruction_tables.pdf:

"Instructions with a LOCK prefix have a long latency that depends on cache organization and possibly RAM speed. If there are multiple processors or cores or direct memory access (DMA) devices then all locked instructions will lock a cache line for exclusive access, which may involve RAM access. A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand."

Re:The Three Ways of XOR by wolfgke on Monday February 13, 2017 @01:11PM (#13637380)
I know that. But this is only relevant if you exchange registers with memory and is not of relevance if you exchange two registers. I accept that this is a good point if some variables are moved to the stack because of register spilling or because you want to use the address of the variable (which is not the case here).

So I still stand by my point: What is the reason why the compiler uses `mov` for exchanging two registers here instead of `xchg`?

Re:The Three Ways of XOR by Someone on Monday February 13, 2017 @03:20PM (#13638384)
I think that's because (at least on some CPUs) it takes three macro-operations. http://www.agner.org/optimize/microarchitecture.pdf (section 17.4, page 188):

"Vector path instructions are less efficient than single or double instructions because they require exclusive access to the decoders and pipelines and do not always reorder optimally. For example:

    ; Example 17.1. AMD instruction breakdown
    xchg  eax, ebx   ; Vector path, 3 ops
    nop              ; Direct path, 1 op
    xchg  ecx, edx   ; Vector path, 3 ops
    nop              ; Direct path, 1 op
This sequence takes 4 clock cycles to decode because the vector path instructions must decode alone."
Re:The Three Ways of XOR by wolfgke on Monday February 13, 2017 @03:38PM (#13638545)
This is indeed a good explanation - I admit I was not aware of this detail of the K8/K10 processors.
Re:The Three Ways of XOR by JoeAltmaier on Monday February 13, 2017 @08:22AM (#13634987)
Some of that is weird placeholders for the debugger, for inserting hook instructions or whatnot?
Re:The Three Ways of XOR by eutectic on Monday February 13, 2017 @05:37AM (#13634345)
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.
Re:The Three Ways of XOR by wolfgke on Monday February 13, 2017 @06:48AM (#13634602)
Yes, you are right - I was a little abentminded.
Re:The Three Ways of XOR by louthy on Monday February 13, 2017 @05:14AM (#13634267)
Yep, that's the 'classic' usage for me. Used to use this all the time if registers were short (and they always were).
Re:The Three Ways of XOR by StringyBob on Sunday February 12, 2017 @05:50PM (#13631562)
Another way to look at XOR - it's an adder (the sum, without the carry)
Re:The Three Ways of XOR by Sniffnoy on Sunday February 12, 2017 @06:20PM (#13631780)
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.
Re:The Three Ways of XOR by bogomipz on Monday February 13, 2017 @09:34AM (#13635449)
The post states at the beginning of the 6th paragraph:

"Some extra treats: XOR can be considered an imparity function. When the number of inputs is even, it outputs zero, while when it is odd, it outputs one. It is also the sum part of an adder, that is, without the carry part. "

Re:The Three Ways of XOR by macawfish on Sunday February 12, 2017 @06:37PM (#13631871)
One 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 xor 0011 = 0101.

wx^yz = wxyz ↔ 1100 xor 0011 = 1111.

and so on.

If anyone has more information about this, I'd be really interested in seeing it!

Re:The Three Ways of XOR by taneq on Sunday February 12, 2017 @07:43PM (#13632198)
I had a similar 'aha' moment a few years ago about inner product (aka dot product) and the choice of '.' as an operator to access elements of a structure.

    struct Example {
      int elem1;
      int elem2;
      ...
    };
    
    Example ex1 = { 1, 2, ... };
    int a = ex1.elem1;
    int b = ex1.elem2;
    ...
If we think of ex1 as a vector, and elem1 as a constant vector [1, 0, 0...] (and elem2 as a constant vector [0, 1, 0, ...] and so on) then ex1.elem1 is literally the inner product of ex1 and the constant elem1.

I have no idea if that was the original thinking behind dot notation but it's neat and I like it.

Re:The Three Ways of XOR by halma on Monday February 13, 2017 @08:03AM (#13634906)
I remember this and other tricks are implemented in Gaigen (a code generator for geometric algebra).

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
We have to take care of the signs though:

- 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.

Re:The Three Ways of XOR by knappa on Sunday February 12, 2017 @08:17PM (#13632372)
Unless you mean something different from the usual multilinear algebra meaning of "exterior algebra", xy^yz is zero. (It contains two y's.) I think that you must actually mean Clifford algebras. (But there are also signs when in characteristic ≠ 2.)
Re:The Three Ways of XOR by macawfish on Sunday February 12, 2017 @09:15PM (#13632671)
Yeah, I do mean Clifford algebras. Thanks for the catch. I'll have to study up on the distinction between "outer products" in Clifford algebras and exterior algebras.
Re:The Three Ways of XOR by johncolanduoni on Monday February 13, 2017 @03:36AM (#13633931)
They are isomorphic as vector spaces (again with characteristic != 2), but their products are not preserved by the isomorphism (unless the Clifford algebra is trivial).
Re:The Three Ways of XOR by _0ffh on Sunday February 12, 2017 @07:44PM (#13632202)
"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.

Re:The Three Ways of XOR by to3m on Sunday February 12, 2017 @08:05PM (#13632312)
It might at least coerce its operands to bool. As things are, 2&&1 is true, and 2&1 is false; hypothetically, 2^^1 could be false while 2^1 would be (as now) true.
Re:The Three Ways of XOR by di4na on Monday February 13, 2017 @05:20AM (#13634287)
The real problem is that you can not short circuit with XOR.
Re:The Three Ways of XOR by delian66 on Monday February 13, 2017 @08:56AM (#13635170)
You have to evaluate both arguments to a XOR op to know its result. Short circuiting it has no natural meaning.
Re:The Three Ways of XOR by Aardwolf on Monday February 13, 2017 @06:57AM (#13634640)
Also, 3 XOR gates allows a wire crossing in 2D (where you cannot make a wire crossing with a bridge as that would be 3D)
Re:The Three Ways of XOR by FabHK on Sunday February 12, 2017 @05:47PM (#13631539)
Lovely article, in particular the small but deep excursion into AI history and the AI winter after the publication of Minsky/Papert's "Perceptrons" (though it was 70's, not 80's).

Wonder when the current AI summer will come to an end...

Re:The Three Ways of XOR by gumby on Sunday February 12, 2017 @11:20PM (#13633106)
I posted this on his site but it needed to be approved. Also, there's actually a comment in the book (I just borrowed my gf's copy) in which they speculate that multilayer networks could be built, but since they only computers they had were .15 MIPS KA-10s (and all the figures in the book were hand drawn) they didn't pursue it.

My guess is it's still early days on the AI boom.

My comment on AI Winter:

Minor correction: Marvin and Seymour's Perceptrons book was published around 1969 and nuked neural nets around there. AI winter set in in the 80s as expert systems and similar crude symbolic systems proved not to be scalable (I was at that AAAI in 1984 and remember that panel well).

Moore's law rescued NNs and is about to rescue symbolic AI as well.

Re:The Three Ways of XOR by wz1000 on Monday February 13, 2017 @02:51AM (#13633767)
> Wonder when the current AI summer will come to an end...

Are we really closer to AI in a significant way today? Chomsky makes an interesting argument to the contrary. He points out that any physical system, say the motion of falling bodies, can be closely modeled statistically given enough data points. However, this modeling gives us very little insight into why the system behaves in that manner, i.e. gravity.

Of course, this presumes that the human brain isn't just an advanced statistical model trained by billions of years of evolution.

Re:The Three Ways of XOR by makecheck on Sunday February 12, 2017 @10:55PM (#13633005)
The last statement in the article is technically a hardware decision (the article says: “As an extra treat, XOR can be considered an imparity function. When its input has an even number of zeros, the output is zero. Otherwise it is one.”).

While 2-input XOR behaves as “one or the other but not both”, a many-input gate is generally implemented by chaining other XORs and the chaining causes even/odd parity instead of a “must be only one” behavior [1].

[1] https://en.wikipedia.org/wiki/XOR_gate

Re:The Three Ways of XOR by SonOfLilit on Monday February 13, 2017 @03:36AM (#13633928)
It's not "just an implementation decision"[1], it's a reasonable mathematical definition: for a binary operator OP, we define it's n-parameter version whenever a OP (b OP c) == (a OP b) op c, which is true for XOR but not e.g. for XNOR (F == F) == T is F, but F == (F == T) is T.

[1] and sorry if I'm falling victim to the difficulty of interpreting tone on the internet

Re:The Three Ways of XOR by jonsen on Monday February 13, 2017 @05:24AM (#13634302)
By symmetry it must be true for XNOR also, and:

  (F == F) == T in fact is T
Re:The Three Ways of XOR by vvanders on Sunday February 12, 2017 @11:48PM (#13633194)
The analog xor is also the basis for CDMA. Fascinating stuff if you dig into it.
Re:The Three Ways of XOR by chillaxtian on Sunday February 12, 2017 @06:11PM (#13631726)
it can also be used to generate simple parity.

https://en.wikipedia.org/wiki/Parity_bit#RAID

Re:The Three Ways of XOR by caf on Sunday February 12, 2017 @07:31PM (#13632138)
That is mentioned in the penultimate paragraph.