11
$\begingroup$

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

$\endgroup$
8
  • 4
    $\begingroup$ What is the definition of the XOR of two decimal numbers? $\endgroup$
    – user57159
    Sep 3, 2011 at 11:11
  • $\begingroup$ @Rickey Demer: Thanks for bringing this question. My actual Question should be like this ? $\endgroup$ Sep 3, 2011 at 13:14
  • $\begingroup$ @Ricky, every natural number is the sum of different powers of 2 in exactly one way; this establishes a bijection between $\mathbb N$ and the set of finite subsets of $\{1,2,4,8,...\}$. Then bitwise XOR is the binary operation on natural numbers that corresponds to the operation $(A,B) \mapsto (A\cup B)\setminus(A\cap B)$ on sets-of-powers-of-2. $\endgroup$ Sep 3, 2011 at 20:47
  • $\begingroup$ I believe the question actually concerns two numbers represented in binary, not decimal numbers as the title says. $\endgroup$
    – anon
    Sep 4, 2011 at 5:42
  • $\begingroup$ i want the formula for xor of two decimal numbers using arthimetic operators made up of decimal numbers $\endgroup$ Sep 4, 2011 at 7:07

6 Answers 6

4
$\begingroup$

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)

enter image description here

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
5
  • $\begingroup$ If your interpretation is correct, then this question's a duplicate of this. $\endgroup$ Oct 4, 2011 at 4:44
  • 1
    $\begingroup$ @J.M. There may be a small difference in that the previous question seemed to be concerned with twos-complement representation whereas my interpretation used natural binary representation. But since the OP insists on saying "decimal number", who knows what he means? $\endgroup$ Oct 4, 2011 at 12:34
  • $\begingroup$ Well, in my question, I wasn't necessarily assuming two's complement; I only gave the example of $-1-n$ as the equivalent "arithmetic function" for bitwise NOT. $\endgroup$ Oct 4, 2011 at 12:48
  • $\begingroup$ Your recursion trick is clever, but not really any easier than calculating $c$ directly from the definition. Indeed, we might as well define $g(a,b) := ((a + b) \operatorname{mod} 2) + 2g(\lfloor\frac a2\rfloor, \lfloor\frac b2\rfloor)$ (with $g(0,0) := 0$ to stop the recursion) and then just let $c = g(a,b)$. $\endgroup$ Oct 4, 2011 at 12:59
  • $\begingroup$ @IlmariKaronen I agree. The point really is that the bit-wise complement is easy to express: it is $2^{n+1} - 1 - a$ for natural representation and $-1 -a$ for twos-complement representation (as J.M. noted previously), but the AND, OR, and XOR operations are not easy to express. Once you have one of them, the others can be obtained with just a few more steps. $\endgroup$ Oct 4, 2011 at 13:13
0
$\begingroup$

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 :-)

$\endgroup$
7
  • $\begingroup$ This answer assumes that there is a fixed number of bits in the numbers. If we want to xor arbitrary natural numbers, then there is no huge ugly formula that is huge enough (except if you allow formulas that involve quantifiers or minimization operators). $\endgroup$ Sep 3, 2011 at 20:42
  • 1
    $\begingroup$ You could write it as an infinite sum. $\endgroup$
    – Listing
    Sep 3, 2011 at 22:01
  • $\begingroup$ Sure -- but from my perspective, an infinite sum goes beyond the simple arithmetic specified in the question -- suddenly an implicit limit appears. Also, the sum notation contains an implicit quantifier that binds the index variable in the sum. $\endgroup$ Sep 3, 2011 at 22:04
  • $\begingroup$ I agree that it is not clear what the operator allows in this case. $\endgroup$
    – Listing
    Sep 3, 2011 at 22:24
  • $\begingroup$ I sure wonder how Mathematica computes BitXor[]... $\endgroup$ Sep 4, 2011 at 1:37
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.