In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(x\ll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(x\gg 1)=\lfloor x/2 \rfloor$. My question: Is it possible to shift right using only addition, subtraction and multiplication? I suspect it is not possible.
I do not have direct access to the bits of the number. I know that the operation $(x\ll (n-1)) \pmod{2^{n+1}}$ effectively gives $(x\gg 1)$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.
By squaring the number a few times it is possible to calculate $(x\&1)=x\%2=(x \pmod 2)$, because all odd numbers give $1$ and all even give $0$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.
No, it's not possible for $n\geq 2$.
Suppose there is some polynomial $p(X) \in (\mathbb{Z}/2^n \mathbb{Z}) [X]$ such that $p(a) = \lfloor \frac{a}{2}\rfloor$ for all $a\in \mathbb{Z}/2^n \mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 \geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.