Notice that after every operation $x+y$ remains unchanged. Now we will define another operation on a pair $(x,a)$,with $x<a$, and $a\equiv1 \pmod2$, called a step, so that if, after applying the given operation to $(x,a-x)$ we get $(u,v)$, then we define the step of $(x,a)$ as $(u,u+v)$. Since $u+v=x+y$, we will get $(u,a)$ after applying the step to $(x,a)$. Notice that if $x$ is even $u=\frac{x}{2}$, and $u=\frac{a+x}{2}$ otherwise, hence $2u \equiv x \pmod a$. So after applying the step $k$ times we will have some pair $(r,a)$, so that $2^kr \equiv x \pmod a$. So we just need to pick a $b$, so that $b+n$ divides $2^k+1$, for some positive integer $k$, and we can always choose a number $b<n$ so that $n+b-1$ is a power of $2$, completing the proof.

Took me quite amount of time to realize that this is actually an NT problem. Let $k$ be a positive integer such that $2^{k-1}<n<2^k$. We claim that taking $b=2^k+1-n$ works. Consider this operation in modulo $2^k+1$, it's easy to see that this operation take $(x, 2^k+1-x)$ to $\left(\dfrac{x}{2}, \dfrac{2^k+1-x}{2}\right)$. Therefore the pair $(n, b)$ will be transformed to \begin{align*} (n, b) &\implies \left(\dfrac{n}{2}, \dfrac{b}{2}\right)\\ &\implies \left(\dfrac{n}{2^2}, \dfrac{b}{2^2}\right)\\ &\vdots \\ &\implies \left(\dfrac{n}{2^k},\dfrac{b}{2^k}\right)\end{align*} But $2^k\equiv -1\pmod{2^k+1}$, therefore after $k$ operation, $(n,b)$ will reach $(2^k+1-n, 2^k+1-b)=(b,n)$ as claimed.