8 ms·
The Three Ways of XOR
- ambrop7 10y ago> 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 :)
- kevinwang 10y agoIs "bool(a1) + ... + bool(aN) == M" not just "a1 || a2...||an"?
- ambrop7 10y agoObviously 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 :).
- kmill 10y agoNo, 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".
- Ded7xSEoPKYNsDd 10y agoSo your + operator implicitly casts booleans to an integer type, with false=0 and true=1?
- simcop2387 10y agoIn c++, yes. Not every language will do that though.
- kmill 10y agoWhat 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.
- OJFord 10y ago> 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 '+'.
- TazeTSchnitzel 10y ago> 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.
- Existenceblinks 10y ago> "(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)
- im3w1l 10y agoIf you only want to convert the second argument you can use the ==! operator ;)
- wruza 10y agoC 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);
- andreareina 10y ago!!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(); }
- caf 10y agoYou don't need to double-negate, !a != !b is sufficient.
- FabHK 10y agoLovely 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...
- wz1000 10y ago> 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.
- gumby 10y agoI 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.
- StringyBob 10y agoAnother way to look at XOR - it's an adder (the sum, without the carry)
- Sniffnoy 10y agoYeah, 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.
- deleted 10y ago[deleted]
- bogomipz 10y agoThe 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. "
- chillaxtian 10y agoit can also be used to generate simple parity. https://en.wikipedia.org/wiki/Parity_bit#RAID https://en.wikipedia.org/wiki/Parity_bit#RAID
- caf 10y agoThat is mentioned in the penultimate paragraph.
- macawfish 10y agoOne 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!
- taneq 10y agoI 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.
- knappa 10y agoUnless 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.)
- macawfish 10y agoYeah, 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.
- johncolanduoni 10y agoThey are isomorphic as vector spaces (again with characteristic != 2), but their products are not preserved by the isomorphism (unless the Clifford algebra is trivial).
- _0ffh 10y ago"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.
- to3m 10y agoIt 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.
- di4na 10y agoThe real problem is that you can not short circuit with XOR.
- deleted 10y ago[deleted]
- delian66 10y agoYou have to evaluate both arguments to a XOR op to know its result. Short circuiting it has no natural meaning.
- makecheck 10y agoThe 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 https://en.wikipedia.org/wiki/XOR_gate
- SonOfLilit 10y agoIt'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
- jonsen 10y agoBy symmetry it must be true for XNOR also, and: (F == F) == T in fact is T
- vvanders 10y agoThe analog xor is also the basis for CDMA. Fascinating stuff if you dig into it.
- cyberferret 10y agoVery 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!
- louthy 10y agoYep, that's the 'classic' usage for me. Used to use this all the time if registers were short (and they always were).
- wolfgke 10y agoThis 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.
- eutectic 10y agoI 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.
- wolfgke 10y agoYes, you are right - I was a little abentminded.
- Khoth 10y agoYes, in fact compilers these days are smart enough to convert people's xor swaps into mov swaps: https://godbolt.org/g/FYv7xQ https://godbolt.org/g/FYv7xQ
- Aardwolf 10y agoAlso, 3 XOR gates allows a wire crossing in 2D (where you cannot make a wire crossing with a bridge as that would be 3D)