# Mathematical Properties of Logical Shift

Many programming languages feature a logical shift operator, such as $(x >> n)$, where the bits of $x$ are shifted $n$ steps to the right (or left, $<<$), and the "vacated" bit positions are filled with zeros.

What are some properties of the logical shift? Left shift seems to be just $(x << n) = x 2^n \mod 2^\ell$, where $\ell$ is bit length. As for right shift, $(x >> 1) = \lfloor x/2 \rfloor$, but is $(x >> 2) = \lfloor x/2^2 \rfloor$, or $= \lfloor \lfloor x/2 \rfloor /2 \rfloor$ and so on for larger shifts? I can't think of a way of representing bit strings to work on. E.g. if $x = \sum b_i 2^i$ and $y = \sum c_i 2^i$, summing them modulo $2^\ell$ isn't as simple as just writing $x +y = \sum (b_i+c_i) 2^i$.

$\lfloor x/2^2 \rfloor$ and $\lfloor \lfloor x/2 \rfloor /2 \rfloor$ give the same result. If $x/2$ is even, this is obvious. If it's odd, then $x = 2y +1$, then $\lfloor \lfloor x/2 \rfloor /2 \rfloor = \lfloor \lfloor y+1/2 \rfloor /2 \rfloor = \lfloor y/2 \rfloor$ and $\lfloor x/2^2 \rfloor=\lfloor y/2 + 1/4 \rfloor$. Since fractional part of $y/2$ is at most $1/2$, you have that the two give the same result. This can easily be generalized to the shift by $n$ bits (the key argument being that $1/2+1/4+1/8+\ldots +1/2^n$ is always less than 1).
• Very nice, thanks. I saw that on wikipedia just now as well. Now, would you agree with my characterization of left shift, i.e $(x << n) = 2^n x \mod 2^\ell$? If so, left shift is linear while right shift is not, do you agree? – Erik Vesterlund Jun 10 '16 at 20:12