Skip to main content

## 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:

\begin{equation*} \bsintp{1000}=-8 \quad\text{but}\quad \bsintp{1000\bsrl 1}=\bsintp{0100}=4 \end{equation*}

To remedy this problem, we introduce another right shift. The signed right shift does not fill in zeroes but replicates the most significant bit:

### Definition1.5.3.Signed Right Shift.

\begin{equation*} x_{n-1} \bsra k \defeq x_{n-1}^k\,x_{n-1}\dots x_k \end{equation*}
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.