## Section1.5Shifts

It is easy to multiply a bit string by $$2^k\text{:}$$ You just shift each digit $$k$$ positions to the left and fill the lower $$k$$ positions that have been freed with 0. Because we only consider bit strings of a fixed length $$n\text{,}$$ the most significant bit will be lost when shifting left by 1.

### Definition1.5.1.Left Shift.

\begin{equation*} x_{n-1} \bsll k \defeq x_{n-1-k}\dots x_0\,0^k \end{equation*}

Dividing by powers of 2 works similarly. Instead of shifting left, we have to shift right. Here, the most significant positions are filled with zeros.

### Definition1.5.2.Unsigned Right Shift.

\begin{equation*} x_{n-1} \bsrl k \defeq 0^k\,x_{n-1}\dots x_k \end{equation*}

However, this does not preserve the sign under the signed interpretation if the bit string denotes a negative number. Consider the following example and let the length of the bit string be 4:

Show that the shift definitions are sound modulo $$2^n\text{.}$$ For the left shift, this means proving $$\buintp{x}\cdot 2\equiv\buintp{x\bsll 1}\mod 2^n\text{.}$$ Formulate respective criteria for the two right shifts and prove them as well.