Live data from Hacker News

The Three Ways of XOR

horia141.com

11–20 of 69 posts

Re: The Three Ways of XOR

#11

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.

Re: The Three Ways of XOR

#12
post #5

Earlier quoted context omitted.

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

So your + operator implicitly casts booleans to an integer type, with false=0 and true=1?

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

#13
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

#14
post #2

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

> 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

#16

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…

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

#17
"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

#18
post #12

Earlier quoted context omitted.

So your + operator implicitly casts booleans to an integer type, with false=0 and true=1?

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.

> 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

#19
post #17

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

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

#20

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…

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.)
Post reply on HN