Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
What is the definition of the XOR of two decimal numbers? –  Ricky Demer Sep 3 '11 at 11:11
    
@Rickey Demer: Thanks for bringing this question. My actual Question should be like this ? –  dungeon Hunter Sep 3 '11 at 13:14
    
@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. –  Henning Makholm Sep 3 '11 at 20:47
    
I believe the question actually concerns two numbers represented in binary, not decimal numbers as the title says. –  anon Sep 4 '11 at 5:42
    
i want the formula for xor of two decimal numbers using arthimetic operators made up of decimal numbers –  dungeon Hunter Sep 4 '11 at 7:07

3 Answers 3

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

share|improve this answer
    
If your interpretation is correct, then this question's a duplicate of this. –  J. M. Oct 4 '11 at 4:44
1  
@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? –  Dilip Sarwate Oct 4 '11 at 12:34
    
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. –  J. M. Oct 4 '11 at 12:48
    
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)$. –  Ilmari Karonen Oct 4 '11 at 12:59
    
@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. –  Dilip Sarwate Oct 4 '11 at 13:13

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

share|improve this answer
    
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). –  Henning Makholm Sep 3 '11 at 20:42
1  
You could write it as an infinite sum. –  Listing Sep 3 '11 at 22:01
    
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. –  Henning Makholm Sep 3 '11 at 22:04
    
I agree that it is not clear what the operator allows in this case. –  Listing Sep 3 '11 at 22:24
    
I sure wonder how Mathematica computes BitXor[]... –  J. M. Sep 4 '11 at 1:37

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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