How to represent XOR of two decimal Numbers with Arithmetic Operators

Question

Is there any way to represent XOR of two decimal Numbers using Arithmetic Operators (+,-,*,/,%).

Answer 1

This is a summary of a similar longer answer I gave on StackOverflow...

---

Basic Logical Operators

NOT = (1-x)

AND = x*y

From those operators we can get...

OR = (1-(1-a)(1-b)) = a + b - ab

OR = a + b, if we know that a*b = 0 for all values of a & b

---

2-Factor XOR

Deriving from set of all truth conditions...

XOR = 1 - (1 - a(1-b))(1 - b(1-a)) = a + b - ab(3 - a - b + ab)

Deriving from compliment of truth conditions...

XOR = (1 - abc)(1 - (1-a)(1-b)(1-c)) = a + b - ab(1 + a + b - ab)

Because we can write (a & !b) || (!a & b) with mutually exclusive terms we can simplify the OR translation as simply + and get...

XOR = a + b - 2ab

For binary values we can condense this expression to

XOR = (a-b)²

---

Multi-Factor XOR

XOR = (1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)

Excel VBA example...

Function ArithmeticXOR(R As Range, Optional EvaluateEquation = True)

Dim AndOfNots As String
Dim AndGate As String
For Each c In R
    AndOfNots = AndOfNots & "*(1-" & c.Address & ")"
    AndGate = AndGate & "*" & c.Address
Next
AndOfNots = Mid(AndOfNots, 2)
AndGate = Mid(AndGate, 2)

'Now all we want is (Not(AndGate) AND Not(AndOfNots))
ArithmeticXOR = "(1 - " & AndOfNots & ")*(1 - " & AndGate & ")"
If EvaluateEquation Then
    ArithmeticXOR = Application.Evaluate(xor2)
End If

End Function

---

Any n of k

These same methods can be extended to allow for any n number out of k conditions to qualify as true.

For instance, out of three variables a, b, and c, if you're willing to accept any two conditions, then you want a&b or a&c or b&c. This can be arithmetically modeled from the composite logic...

(a && b) || (a && c) || (b && c) ...

and applying our translations...

1 - (1-ab)(1-ac)(1-bc)...

This can be extended to any n number out of k conditions. There is a pattern of variable and exponent combinations, but this gets very long; however, you can simplify by ignoring powers for a binary context. The exact pattern is dependent on how n relates to k. For n = k-1, where k is the total number of conditions being tested, the result is as follows:

c1 + c2 + c3 ... ck - n*∏

Where c1 through ck are all n-variable combinations.

For instance, true if 3 of 4 conditions met would be

abc + abe + ace + bce - 3abce

This makes perfect logical sense since what we have is the additive OR of AND conditions minus the overlapping AND condition.

If you begin looking at n = k-2, k-3, etc. The pattern becomes more complicated because we have more overlaps to subtract out. If this is fully extended to the smallest value of n = 1, then we arrive at nothing more than a regular OR condition.

Answer 2

I think what Sanisetty Pavan means is that he has two non-negative integers $a$ and $b$ which we assume to be in the range $0 \leq a, b < 2^{n+1}$ and thus representable as $(n+1)$-bit vectors $(a_n, \cdots, a_0)$ and $(b_n, \cdots, b_0)$ where $$ a = \sum_{i=0}^n a_i 2^i, ~~ b = \sum_{i=0}^n b_i 2^i. $$ He wants an an arithmetic expression for the integer $c$ where $$c = \sum_{i=0}^n (a_i \oplus b_i) 2^i = \sum_{i=0}^n (a_i + b_i -2 a_ib_i) 2^i = a + b - 2 \sum_{i=0}^n a_ib_i 2^i$$ in terms of $a$ and $b$ and the arithmetic operators $+, -, *, /, \%$. Presumably integer constants are allowed in the expression. The expression for $c$ above shows a little progress but I don't think it is much easier to express $\sum_{i=0}^n a_ib_i 2^i$ than it is to express $\sum_{i=0}^n (a_i \oplus b_i) 2^i$ in terms of $a$ and $b$, but perhaps Listing's gigantic formula might be a tad easier to write out, though Henning Makholm's objections will still apply.

Added note: For fixed $n$, we can express $c$ as $c = a + b - 2f(a,b)$ where $f(a, b)$ is specified recursively as $$f(a, b) = (a\%2)*(b\%2) + 2f(a/2, b/2)$$ with $a\%2$ meaning the remainder when integer $a$ is divided by $2$ (that is, $a \bmod 2$) and $a/2$ meaning "integer division" which gives the integer quotient (that is, $a/2 = (a - (a\%2))/2$). Working out the recursion gives a formula with $n+1$ terms for $f(a, b)$.

Answer 3

The answer is yes. Let us assume the numbers $a,b$ have the form

$a = (a_1,a_2,\ldots,a_n)$

$b = (b_1,b_2,\ldots,b_n)$

where $a_i,b_i \in \{0,1\}$. We can extract the lowest bit ($a_n,b_n$) with

$a_n = a\%2$, $b_n = b\%2$.

Similar we have $a_{n-1}=[(a-a_n)/2]\%2$, $b_{n-1}=[(b-b_n)/2]\%2$

Now when $c = a\text{ XOR }b$ we know that $c_n = (a_n+b_n)\%2$ and so on and you can put that all together in a huge ugly formula :-)

Answer 4

Looking at p. 309 of Fuzzy Sets and Fuzzy Logic: Theory and Applications by George Klir and Bo Yuan, I notice Reichenbach implication as 1-a+ab, with "a" and "b" presumed as belonging to {0, 1}. XOR means the same thing basically as the negation of logical equivalence. Logical equivalence can get represented as "the conjunction of p implies q, and q implies p." Modeling "not a" as 1-a on {0, 1}, and conjunction as the product ab, then logical equivalence becomes (1-a+ab)(1-b+ab). So, it's negation becomes 1-(1-a+ab)(1-b+ab)=1-(1-b+ab-a+ab-aab+ab-abb+aabb)=b-ab+a-ab+aab-ab+abb-aabb=a+b-3ab+aab+abb-aabb, which behaves just like XOR on {0, 1}, as you might want to check for yourself.

The Klir and Yuan text also points out that 1-a+aab will work for implication, so a formula for XOR could get derived from that. Also, if you allow "max" and "min", the maximum and minimum of two numbers respectively, many other functions for logical implication can get written, and for logical conjunction which makes many more formulas not all too hard to write.

Answer 5

Using vector math: $$A \oplus B = (A - B)(A - B)$$

This assumes that $A$ and $B$ are vectors of equal length with binary elements--formally: $$A = (a_1, \cdots, a_n), B = (b_1, \cdots, b_n), a_i \in \{0,1\}, b_i \in \{0,1\}$$

Proof: $$x = x^{2i + 2} : i \in \mathbb{N}, x \in \{0, 1\}$$ $$x \oplus y = x + y - 2xy = x^2 + y^2 - 2xy = (x - y)^2 : x,y \in \{0,1\}$$ $$A \oplus B = (a_1 \oplus b_1, \cdots, a_n \oplus b_n) = ((a_1 - b_1)^2, \cdots, (a_n - b_n)^2) = (A - B)(A - B)$$

Other than converting to vectors or using looping/recursion as given in the other answers it's impossible to define bitwise XOR of two scalars. A comment in another question links to a page that's helpful for understanding why.

Answer 6

Improving on answer given by @Dilip Sarwate , XOR of two numbers a,b will be

f(a,b)=(a^b)%2+2f(a/2,b/2)

One way of simplifying (a^b) in the formula will be that if:-

• a and b are both even or both odd then (a^b) will be even , hence modulo 2 will be zero.
• And if one of a,b is even and the odd and vice-versa then (a^b) will be odd hence modulo 2 will be one.