1
$\begingroup$

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$.

Anyway, is anything known about this rather standard operation? I've tried to google but can't find anything, odd really.

$\endgroup$
1
$\begingroup$

Note: this does not answer the whole question, but it was rather lengthy for a comment.

$\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).

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Erik Vesterlund Jun 10 '16 at 20:12

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.