Jump to content
  • Advertisement
Sign in to follow this  
doynax

Contradicting definitions of XOR

This topic is 5059 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ahh.. My first thread =) The xor function is often explained as 'exactly one of' in school, however as a programmer I prefer to look at it as a conditional inversion. For less than three inputs this is just two views of the world but for three of more these two definitions yields different results. So exactly one of them ;) must be the real definition. A little searching reveals the following on Wikipedia.
Quote:
The operation yields the result TRUE when one, and only one, of its operands is TRUE
Quote:
For more than two inputs, xor can be applied to the first two inputs, and then the result can be xor'ed with each subsequent input
So now I'm more confused than when I started..

Share this post


Link to post
Share on other sites
Advertisement
Quote:
The operation yields the result TRUE when one, and only one, of its operands is TRUE


AFAIK XOR works on two inputs only (at a time). so that definition above is for two inputs on the XOR. For more than two inputs, xor can be applied to the first two inputs, and then the result can be xor'ed with each subsequent input.

Which bit are you confused with?

Share this post


Link to post
Share on other sites
I've never seen xor used with more than two arguments, so it may not be "officially" defined.

Share this post


Link to post
Share on other sites
Let's see here:


a b c (a^b) result (a^b)^c

0 0 0 0 0
1 0 0 1 1
0 1 0 1 1
1 1 0 0 0
0 0 1 0 1
1 0 1 1 0
0 1 1 1 0
1 1 1 0 1



...Then you can continue with a fourth operand, using the above result (3 operands) to get a new result :)

Share this post


Link to post
Share on other sites
XOR is a mathematical binary operator. That means that it works on two operands only. What the definition meant was, that if you want to use XOR on more than 2 operands, you have to do the XOR operation more than once.

--+
|XOR --+
--+ |XOR -
---------+

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by doynax
Ahh.. My first thread =)

The xor function is often explained as 'exactly one of' in school, however as a programmer I prefer to look at it as a conditional inversion.
For less than three inputs this is just two views of the world but for three of more these two definitions yields different results.
So exactly one of them ;) must be the real definition.

A little searching reveals the following on Wikipedia.
Quote:
The operation yields the result TRUE when one, and only one, of its operands is TRUE

Quote:
For more than two inputs, xor can be applied to the first two inputs, and then the result can be xor'ed with each subsequent input

So now I'm more confused than when I started..


you should not let multiple operations change anything. XOR is associative. an operation just needs an LHS and RHS. If looking at
A ^ B ^ C ^ D
is confusing, just break it in to
(A ^ B) ^ (C ^ D)
now it's just a plain old xor. XOR A with B, C with D, then the results of each.

This gives a general definition for XOR: It is true if there are an odd number of true values.

Share this post


Link to post
Share on other sites
The XOR Operator is mainly used as binary Operator, and therefore your definition applies only to the binary version of XOR.
If you want to use a XOR with more than two Operands then you would have to split it up.

e.g. XOR with three operands a, b, and c:

xor(a, b, c) = xor(xor(a, b), c)

It does not matter in which order you split up the XOR:

xor(xor(a, b), c) = xor(a, xor(b, c))

Surprisingly a much simpler definition of XOR, that works with as many Operands as you like would be:

XOR evaluates to 1 if an odd number of its operands evaluates to 1, otherwise it evaluates to 0.

I don't know why this definition is not the mathematical correct one, perhaps since it allows XORs with 1 or even 0 operands.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
In digital electronics there exists gates (such as xor) which have several inputs and one output. Often these are internally implemented as described before altough the information of the exact implementation is not necessary if you use the definition of xor for multiple inputs. (odd -> true, even -> false)

Share this post


Link to post
Share on other sites
I prefer to look at XOR as the sum in Z/(2). Z/(2) is the field formed by the numbers {0,1} with sum table
0+0=0
0+1=1
1+0=1
1+1=0

and multiplication table
0*0=0
0*1=0
1*0=0
1*1=1

XOR is the sum and AND is the product.

When talking about bitwise operators, we are just working in the vector space (Z/(2))^n, where n is your number of bits. XOR is still the sum.

Share this post


Link to post
Share on other sites
Exclusive OR.

usually an or returns true even if both operands are true. This only returns true if 1 operand OR the other is true. Not if both are true. So

0 xor 0 = 0
1 xor 1 = 0
1 xor 0 = 1
0 xor 1 = 1

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!