Sign in to follow this  

Contradicting definitions of XOR

This topic is 4841 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
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
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
Quote:
Original post by Oluseyi
Interesting how many people thing XOR is only a binary operator.


It is. Just as And and Or are. To use them on multiple inputs you can stack them. Chips that simulate the XOR function in Digital Systems but have multiple inputs are usually sequentially stacked XOR's or they use a completely different method. The fact is XOR was designed to be used in a binary system.

Just like you say 1 and 2 and 3. Not 1-2-3 AND. Operators such as these are comparisons between two inputs.

You can say 1 AND 2 AND 3 is an AND function with 3 inputs, but in reality its 2 AND functions each with 2 inputs, stacked.

Share this post


Link to post
Share on other sites
Quote:
Original post by healeyx76
Quote:
Original post by Oluseyi
Interesting how many people thing XOR is only a binary operator.


It is. Just as And and Or are.
Any operation that is both commutative and associative and has an identity element is implicitly defined for any nonnegative number of operands. You can think of it as "stacking" if you like, but that's really just semantics, since the "stacking order" is irrelevant.

Share this post


Link to post
Share on other sites
XOR is a binary operator by definition. It could be (and some times it is) redefined to be something like XOR(x1,x2,x3,...). But mostly you see x1+x2. (Where the "+" is circle with plus inside) Thus the usual definition of xor is _binary_.

Share this post


Link to post
Share on other sites

This topic is 4841 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this