# A cute theorem involving xor

Define $[a..b] = \set{x|a\leq x\leq b, x\in \mathbb{N} }$, and $k\oplus [a..b] = \set{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 $\displaystyle 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:\mathbb{N}\to \mathbb{N}$ a surjection such that $x-n\leq f(x)\leq x+m$, then

1. $[a+m..b-n] \subseteq f([a..b])$
2. $[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\})$ $\displaystyle x-n\leq f(x)\leq x+m \implies y+m\leq f^{-1}(y)\leq y-n.$

1. If $y\in [a+m..b-n]$, $f^{-1}(y) \in [(a+m)-m.. (b-n)+n] = [a..b]$.
2. 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
1. $[a+k..b-k] \subseteq k\oplus [a..b]$.
2. $[0..b-k] \subseteq k\oplus [0..b]$.
Posted by Chao Xu on .
Tags: math.