I consider a bit-reversal permutation of interval $[0, 2^k)$. That is, x is mapped to rev(x) (let's assume that binary representation uses k bits, not more). That is, $x = \sum 2^i$ and $rev(x) = \sum 2^{k-i}$.
I would like to prove something like that if $x\not=y$ and $|x-y| < 2^i$ then $|rev(x)-rev(y)| >= O(2^f(i))$ where $f$ is some function . So far I was able to prove that if $x$ and $y$ share $k$ most significant bits, then $|rev(x)-rev(y)| >= 2^k$.
Thank you.
