The Art Gallery Guardian

A cute theorem involving xor


Define [a..b]={xaxb,xN}[a..b] = \set{x|a\leq x\leq b, x\in \mathbb{N} }, and k[a..b]={kxx[a..b]}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[a..b]k\oplus [a..b].

Lemma1

xyxyx+yx-y \leq x\oplus y \leq x+y

Proof

xyx+yx\oplus y \leq x+y is easy to see as \oplus is binary addition without carries. Assume xy<xyx\oplus y < x-y for some xx and yy, then x=x(yy)=(xy)y<(xy)y(xy)+y=x x = x\oplus(y\oplus y) = (x\oplus y) \oplus y < (x-y)\oplus y\leq (x-y)+y = x A contradiction. Therefore xyxyx-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:NNf:\mathbb{N}\to \mathbb{N} a surjection such that xnf(x)x+mx-n\leq f(x)\leq x+m, then

  1. [a+m..bn]f([a..b])[a+m..b-n] \subseteq f([a..b])
  2. [0..bn]f([b])[0..b-n] \subseteq f([b])
Proof

ff is a surjection implies all values in any integer interval gets taken. f1(y)=min({xf(x)=y})f^{-1}(y)=\min(\{x|f(x)=y\}) xnf(x)x+m    y+mf1(y)yn. x-n\leq f(x)\leq x+m \implies y+m\leq f^{-1}(y)\leq y-n.

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

Let fk(x)=kxf_k(x) = k\oplus x, noting that fkf_k is a bijection, we derive the result we want for xor.

Corollary3
  1. [a+k..bk]k[a..b][a+k..b-k] \subseteq k\oplus [a..b].
  2. [0..bk]k[0..b][0..b-k] \subseteq k\oplus [0..b].
Posted by Chao Xu on .
Tags: math.