# A cute theorem involving xor

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

$x−y≤x⊕y≤x+y$

$x⊕y≤x+y$ is easy to see as $⊕$ is binary addition without carries. Assume $x⊕y<x−y$ for some $x$ and $y$, then $x=x⊕(y⊕y)=(x⊕y)⊕y<(x−y)⊕y≤(x−y)+y=x$ A contradiction. Therefore $x−y≤x⊕y$.

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

If $f:N→N$ a surjection such that $x−n≤f(x)≤x+m$, then

- $[a+m..b−n]⊆f([a..b])$
- $[0..b−n]⊆f([b])$

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

- If $y∈[a+m..b−n]$, $f_{−1}(y)∈[(a+m)−m..(b−n)+n]=[a..b]$.
- If $y∈[0..b−n]$, $f_{−1}(y)∈[max(0−m,0)..(b−n)+n]=[0..b]$.

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

- $[a+k..b−k]⊆k⊕[a..b]$.
- $[0..b−k]⊆k⊕[0..b]$.