1.5 Shifts

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

Definition 1.5.1: Left Shift

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

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:

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

Exercise 1.5.4

Show that the shift definitions are sound modulo . For the left shift, this means proving . Formulate respective criteria for the two right shifts and prove them as well.