Skip to main content

Section 1.5 Shifts

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.

Definition 1.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.

Definition 1.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:

Definition 1.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.