Truth table for XOR function for non binary bases

Question

I know that the XOR operator in base 2 for two bits A and B is (A+B)%2. In others words, it's addition modulo 2.

If I want to compute the truth table for XOR operation in a ternary system (base 3), is it same as addition modulo 3? Eg: In a base 3 system, does 2 XOR 2 = 1 (since (2+2)%3 = 1)?

I read this link which indicated that 2 XOR 2 in a base 3 system is 2 and I can't understand the formula behind that?

In general, for any base 'x', is the XOR operation for that base - addition modulo x?

Crispy

No it's the other way around, there are many algebraic structures with addition, and addition in GF(2) is XOR. – Chanellechaney

Answer 1

Well, XOR stands for eXclusive OR and it is a logical operation. And this operation is only defined in binary logic. In your link author defines completely different operator which works the same as XOR for binary base. You may call it an "extension" of XOR operation for bases greater than 2. But as you mentioned in your question, there are multiple ways to do this extension. And each way would preserve some properties of "original" XOR and loose some other. For example, you can stick to observation that

a ⊕ b = (a + b) mod 2

In this case your "extended XOR" for base 3 would produce output of 1 for inputs 2, 2. But this XOR3 will no longer satisfy other equations that work for standard XOR, e.g. these ones:

a ⊕ b ⊕ b = a

a ⊕ b ⊕ a = b

If you choose to "save" those, you will get the operation from your link. You can also preserve some different property of XOR, say

a ⊕ a = 0

and get another operation that is different from the former two.

So the short answer is: the phrase "XOR function for non binary bases" doesn't make any sense. XOR operator is only defined in binary logic. If you want to extend it for non-binary bases or non-integer number or complex numbers or whatever, you can do it and define some extension function with whatever behavior and whatever "truth table" you want. But this extension won't be a XOR function anymore.

Tigges

As a point of curiosity, if XOR is defined as the absolute difference, then what properties are lost in bases higher than two? – Fiberboard

For example, associativity. For base 2 XOR: a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c. For higher bases it's no longer the case. E.g. for base 10: 3 ⊕ (6 ⊕ 7) = 3 ⊕ 1 = 2 vs (3 ⊕ 6) ⊕ 7 = 3 ⊕ 7 = 6 – Tigges

Yes, well demonstrated (except I think that final 6 should be a 4). It's interesting to notice that certain algebraic properties depend on the base being employed, and that distinct operations in higher bases converge in lower bases. – Fiberboard

Answer 2

While I don't know that XOR has technically been defined in higher bases, the properties of XOR can be maintained in higher bases such that:

a ⊕ b ⊕ b = a

a ⊕ b ⊕ a = b

As the blog post shows, using (base - (a + b) % base) % base works. The part you were missing is the first instance of base. In the example of 2 ⊕ 2 in base 3, we get (3 - (2 + 2) % 3) % 3) which does give 2. This formula only works with single digit numbers. If you want to extend to multiple digits, you would use the same formula with each pair of digits just as standard XOR in binary does it bitwise.

For example, 185 ⊕ 42 in base 10 when run for each pair of digits (i.e. hundreds, tens, ones) gives us:

(10 - (1 + 0) % 10) % 10 => 9

(10 - (8 + 4) % 10) % 10 => 8

(10 - (5 + 2) % 10) % 10 => 3

Or 983 when put together. If you run 983 ⊕ 145, you'll find it comes out to 85.

Vestiary