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*}
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.
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*}
