1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ You should explain what a shift is since not everyone here has a programming background. $\endgroup$ – Toby Mak Dec 21 '18 at 5:55
  • $\begingroup$ You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$ $\endgroup$ – gammatester Dec 21 '18 at 9:11
  • $\begingroup$ Thanks, edited accordingly. $\endgroup$ – oddy Dec 22 '18 at 6:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1. $\endgroup$ – Peter Taylor Dec 22 '18 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.