Is there any way to represent XOR of two decimal Numbers using Arithmetic Operators (+,-,*,/,%).
Tell me more
×
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.
|
|
|||||||||||||
|
|
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)$. |
|||||||||||||
|
|
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 :-) |
|||||||||||||
|
|
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. |
|||
|
|
