A cute theorem involving xor

Define $[a .. b] = {x ∣ a \leq x \leq b, x \in N}$ , and $k \oplus [a .. b] = {k \oplus x ∣ x \in [a .. b]}$ , where $\oplus$ is the bitwise xor function. We want to know something about $k \oplus [a .. b]$ .

Lemma1

$x - y \leq x \oplus y \leq x + y$

Proof

$x \oplus y \leq x + y$ is easy to see as $\oplus$ is binary addition without carries. Assume $x \oplus y < x - y$ for some $x$ and $y$ , then $x = x \oplus (y \oplus y) = (x \oplus y) \oplus y < (x - y) \oplus y \leq (x - y) + y = x$ A contradiction. Therefore $x - y \leq x \oplus y$ .

Remark

$\oplus$ , binary addition without carries, and binary subtraction without borrows are the same operation. The lemma is trivial by notice that equivalence.

Theorem2

If $f : N \to N$ a surjection such that $x - n \leq f (x) \leq x + m$ , then

$[a + m .. b - n] \subseteq f ([a .. b])$
$[0.. b - n] \subseteq f ([b])$

Proof

$f$ is a surjection implies all values in any integer interval gets taken. $f^{- 1} (y) = min ({x ∣ f (x) = y})$ $x - n \leq f (x) \leq x + m ⟹ y + m \leq f^{- 1} (y) \leq y - n .$

If $y \in [a + m .. b - n]$ , $f^{- 1} (y) \in [(a + m) - m .. (b - n) + n] = [a .. b]$ .
If $y \in [0.. b - n]$ , $f^{- 1} (y) \in [max (0 - m, 0) .. (b - n) + n] = [0.. b]$ .

Let $f_{k} (x) = k \oplus x$ , noting that $f_{k}$ is a bijection, we derive the result we want for xor.

Corollary3

$[a + k .. b - k] \subseteq k \oplus [a .. b]$ .
$[0.. b - k] \subseteq k \oplus [0.. b]$ .

Posted by Chao Xu on 2012-06-19.

Tags: math.