Lately I was trying to figure out some mathematical properties of XOR. So for equalities with XOR we can do $\oplus\ x$ on both sides of it and still get the right equality. Example:

$a \oplus b = c$

$a \oplus b \oplus b = c \oplus b$

$a = c \oplus b$

Will this work in inequalities? I mean, is it true that for any integers $a$, $b$, $c \geq 0$, if:

$a \oplus b < c$


$a > c \oplus b$

If not, what properties are there for inequalities with XOR?

  • $\begingroup$ Ok I'm sorry, I've found a counter-example fast enough: a = 2, b = 4, c = 5. But still, are there any properties for XOR inequalities? $\endgroup$ – Trounee Mar 20 at 11:40
  • $\begingroup$ "xor" is just addition in $\mathbb Z_2$. It will behave like any abelian group operation. $\endgroup$ – Brian Mar 20 at 11:45
  • $\begingroup$ The bitwise xor isn't monotonic in its arguments, there are no useful inequalities. $\endgroup$ – Yves Daoust Mar 20 at 11:47
  • $\begingroup$ @Brian: what is the relevance of this comment ? The question concerns $\mathbb Z$. $\endgroup$ – Yves Daoust Mar 20 at 11:47
  • $\begingroup$ @YvesDaoust $\mathbb Z_{2^n}$ is isomorphic to $\mathbb Z_2^n$ over xor. Consider what it means to represent an integer in base 2. This is roughly equivalent to working with an $n$-tuples over $\mathbb Z_2$. Please let me know if I am mistaken. $\endgroup$ – Brian Mar 20 at 12:29

Your Answer

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

Browse other questions tagged or ask your own question.