1

I am studying bitwise XOR.

If a, b, c are integers ranging from 0 to 18,446,744,073,709,551,615, I belive the following work for both $=$ and $\neq$:

$1.\forall a,b,c(a=b\to a \oplus c=b \oplus c)$

$2.\forall a,b,c(a \oplus c=b \oplus c\to a=b)$

$3.\forall a,b,c(a\neq b\to a \oplus c\neq b \oplus c)$

$4.\forall a,b,c(a\oplus c\neq b\oplus c\to a\neq b)$

But the above will not work for $<, \le, >, \ge$.

Is that correct?

alancc
  • 21
  • What are $a, b, c$? What operations or relations denote "$^$" and "$!=$"? – Alex Ravsky May 23 '20 at 03:14
  • 2
    yes, (1)-(4) are correct and above doesn't work for inequalities. @AlexRavsky In some compute languages (eg. C), ^ and != stands for bitwise XOR and numerical not-equal. – achille hui May 23 '20 at 03:53
  • 1
    Since $a,b,c$ are integers, when you say "XOR" do you actually mean bitwise exclusive OR? In Mathematica (the tag on this question), that would be BitXor rather than Xor. On the other hand, your use of the symbol ^ in the original version of the question suggests you were thinking of C or some other language that is not Mathematica--so it's unclear what the purpose of the Mathematica tag is. – David K May 23 '20 at 16:20
  • @DavidK, sorry for the confusion. Yes, it is bitwise XOR. What is the difference between bitwise XOR and XOR? I think they are the same? – alancc May 23 '20 at 23:08
  • XOR naturally works with logical values, not integers. You have to make some interpretation of what an integer means as input to XOR. In Excel, for example, 1+XOR(8,7) will give the result $1$, whereas if it were a bitwise XOR the result should be $16.$ What makes the difference is that $8$ and $7$ are both treated as "true" logical values by the (non-bitwise) XOR function, so you get the same result from XOR(8,7) as from XOR(1,1). – David K May 23 '20 at 23:50
  • @DavidK, Thank you for your explanation. I understand now. For XOR, there is only two kinds of logic values, zero(FALSE) and non-zero(TRUE). But for bitwise XOR, the XOR is performed on each bit one by one. – alancc May 24 '20 at 00:08
  • More briefly you just have one equation: $\forall {a,b,c} \left(a=b \iff a\oplus c = b\oplus c\right)$. – mjqxxxx May 28 '20 at 00:30

1 Answers1

1

For equality:

Statement $(1)$ is true.

Statement $(2)$ is true since if $a\oplus c = b \oplus c$ then we have $(a \oplus c)\oplus c = (b \oplus c) \oplus c$, using the associative property, we have

$$a \oplus (c \oplus c) = b \oplus (c \oplus c)$$

$$a = b$$

$(3)$ is true since $(2)$ an $(3)$ are equivalent.

$(1)$ and $(4)$ are equivalent, hence $(4)$ is correct as well.

It doesn't work on inequalities. To see counterexamples, choose $0$ to be the smaller element and pick $1$ to be the bigger element, picking $c=0$ would preserve the inequalities but picking $c=1$ would switch the direction of the inequalities.

For example.

  • Conjecture: if $\forall a, b, c , a < b$ then $a \oplus c < b \oplus c $.

This is false since $0 < 1$, but $0 \oplus 1 = 1$ and $1 \oplus 1 = 0$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149